insertion sort decriminalized (i hope)

[Søren Kyale]

Insertion sort works like a zombie librarian reordering a shelf of books 

where all books on the self belong on the shelf. 

Look at the first book on the shelf. 

See if the call number of the next book is higher. 

If it is go to the next book and repeat the process until you find a book that has that has a lower call number than the properly sequenced books before it.

Take that book out off the self and hold it in one hand.

Then move the book before it into the empty space.

See if book before the new empty space has a lower call number.

Repeat until you get to the end of the shelf 

or the book to before the space 

has a lower call number than the book in your hand.

Then go back to the position after the place where you found the unordered book and repeat until you get to the end of the shelf.

Lowman's method is almost the same except that it has you place the in your hand back on the shelf each time you create a new space. I'll endeavor to provide pseudo code for the more reasonable approach.

Here it goes:

Let insertion be a function that 

takes in 

a list, 

a beginning index,* 

and an ending index.*

*[the start and end indexes make the function much more useful because it can sort partial lists

or be combined with quick sort to handle shorter list fragments].

Let list be the list to be sorted.

Let a be the index for the first element to be sorted in list.

Let b be the index of the last element to be sorted in list.

Let progress be a pointer to the last sorted position in list.

Let seek be a pointer to the position where we're looking to place the unsorted element.

Let temp be an address outside of the list where we'll hold the unsorted element until we find a place for it.

Let @n be a reference to the nth element of list.

for progress, [a,b) # progress will take the values from a to b in order

#starting with a and including a, but excluding b.

if @progress+1 > @progress  #check to see if the book is unsorted

then

temp = @progress+1 #take the unsorted book in hand

             

for seek, [progress, a) # take values from progress to a in descending order. 

#Include progress, exclude a.

overwrite @seek+1 with @seek # in python: list[seek+1] = list[seek]

 if seek-1 < temp #you found a place to put the book.

 then

break out of this loop so you can put the book away

and find the next item to sort. 

 

 overwrite @seek with temp

And with that it should all be sorted.

[Jeremy Kun]

My favorite general sorting algorithm is mergesort, and its description is simple:

split the list in half

recursively call mergesort on each piece

merge the two results to preserve the sorting

if a "piece" has length 1, then it's already sorted and mergesort just returns it.

In untested python:

def merge(L1, L2):

   i = 0

   L = [0 for i in range(max(len(L1), len(L2)))]

   while len(L1) != 0 and len(L2) != 0:

      if L1[0] < L2[0]:

         L[i] = L1.popleft()

      else:

         L[i] = L2.popleft()

      i += 1

   L.extend(L1)

   L.extend(L2)

   return L

def mergesort(L):

   if len(L) == 1:

      return L

   else:

      mid = len(L)/2

      left, right = mergesort(L[:mid]), mergesort(L[mid:])

      return merge(left, right)

Jeremy Kun

Mathematics Graduate Student

University of Illinois at Chicago

--
You received this message because you are subscribed to the Google Groups "uic-mcs260-s13" group.
To unsubscribe from this group and stop receiving emails from it, send an email to uic-mcs260-s1...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[S.F. Kyale]

Thank you. That is pretty. I will take me some time piece the idea together. Yet I like the way it completely separates the elements before reordering them. It looks like it leaves itself open to unproved techniques for finding a most ordered state of n things in <<O(n) time. Say maybe with a large quantum computer if such is ever shown to be possible (I'm assuming it has not yet been shown to be possible or impossible, though I'm not at all aware of the current state of quantum computing.

Can merge sort make use of hash tables to sort faster?

[Søren Kyale]

I think your code had some bugs it it. Though I didn't try so hard to get it to run. Instead I made a much uglier version. But it worked. And even though I am not happy with my version. I think if my assembler function was turned into a generator it might run much faster.

Still, I'm very happy with the way it is impervious to worst case scenarios (or that it's worst cases or rather it handles its worst cases well).

I think this is pretty much the same thing you coded except I didn't understand the extend method.

# assembler: list, list -> list

def assembler(list1, list2):

   inList1,inList2, len1, len2 = 0,  0, len(list1), len(list2)

   outList = list(xrange(len1+len2))

   for i in outList:

      if inList1 < len1:

         if inList2 >= len2:

            outList[i], inList1 = list1[inList1], inList1+1

            continue

         if list1[inList1] <= list2[inList2]:

            outList[i], inList1 = list1[inList1], inList1+1

            continue

      outList[i], inList2 = list2[inList2], inList2+1

   return outList

# mergesort: list -> none

def mergesort(IOList):

   aList = [[i] for i in IOList]

   while len(aList) > 1:

      count, cmax = 0, len(aList)-1

      while count < cmax:

         aList[count>>1] = assembler(aList[count], aList[count+1])

         count += 2

      if count == cmax:

         aList[(count>>1)] = aList[cmax]

         aList = aList[:(count>>1)+1]

      else: aList = aList[:(count>>1)]

   for i, val in enumerate(aList[0]):

      IOList[i] = val

To unsubscribe from this group and stop receiving emails from it, send an email to uic-mcs260-s13+unsubscribe@googlegroups.com.