Search code examples
algorithminsertion-sortclrs

CLRS Insertion Sort Implmentation

I was going through Insertion Sort algo in CLRS. I am not sure which is the right implementation -

Algo from CLRS - CLRS pseudocode

Implementation 1 :

def Insertion_sort():
list = [3,5,1,7,2,4]
for j in xrange(1,len(list)):
    i = j-1
    while i>=0 and list[i] > list[j]:
        swap(list, i, j)
        j = i
        i = i-1

Implementation 2:

def Insertion_sort2():
list = [3,5,1,7,2,4]
for j in range(1,len(list)):
    i = j-1;
    while i>=0 and list[i]>list[j]:
        i = i-1;
    swap(list, i+1, j)

Thanks

Solution

  • Neither of the proposed functions actually reproduces the algorithm as presented in CLRS.

    The code in lines 5 through 8 in the CLRS algorithm do a rotation of a subsequence of the list ending at index j. That will insert the value at index j in the correct point in the prefix of the list.

    Your first function does the same thing, but instead of doing a rotation it does a series of swaps. The rotation is much more efficient, since it only modifies each list item once instead of twice.

    Your second function just does a single swap, which moves the value at element j into the right spot, but does not preserve the order of the rest of the prefix of the list. So it is a lot faster, but produces an incorrect result. (The fact that it happened to produce a sorted output with your test vector is amusing, but if you look at the successive prefixes at each insertion point, you'll see that it doesn't really work. Try sorting just [2, 3, 1], for example.)