Lorenzo Vannucchi Lorenzo Vannucchi - 5 months ago 9
Python Question

Insertion_Sort() implementation (Error), Python

I have two version of the implementation of INSERTION SORT; I think that are equivalent, but the second one returns a sorted list wrong.
This is the first one:

def insertionSort(A):
for j in range(1,len(A)):

key = A[j]
i = j

while i>0 and A[i-1]>key:
A[i] = A[i-1]
i -= 1

A[i] = key


this is the second one:

def insertionSort(A):
for j in range(1,len(A)):

key = A[j]
i = j-1

while i>0 and A[i]>key:
A[i+1] = A[i]
i -= 1

A[i+1] = key


I've tested these two algorithm with this C array

C = [54,26,93,17,77,31,44,55,20]
insertionSort(C)
print(C)


In the first case my array is correctly sorted; in the second case my result is:


[54, 17, 20, 26, 31, 44, 55, 77, 93]


The second case comes from the pseudo code on my school book. Why doesn't it work correctly?

Answer

Here's a correction of your second code:

def insertionSort(A):
    for j in range(1,len(A)):

        key = A[j]
        i = j-1

        while i>=0 and A[i]>key:
            A[i+1] = A[i]
            i -= 1

        A[i+1] = key

The difference lies in the >= towards > in the while loop. To understand, let's refer to the behaviour of the insertion sort. That sorting algorithm assumes that the array [0, j-1] is sorted and then places the element at the right place.

Now, lets assume that we wan't to sort [4,3,2,0,5,6,7] and we're now in that state:

A = [2, 3, 4, 0, 5,6,7]

The first three elements are in the right place and we need to put 0 in its right position (index 0). From i = 2 to i= 0, the condition A[i] > key is always true. So, we will do: A[3] = A[2], A[2] = A[1], A[1] = A[0].

Then we will leave the loop with i = -1 and set A[i+1] = A[0] = 0.

In your previous version, the loop would stop at i = 0 and the last instruction would do A[0+1] = A[1] = 0. It's why when you give [2, 3, 4, 0, 5,6,7] in the algorithm, it gives a bad result.

Comments