Lorenzo Vannucchi -5 years ago 220
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?

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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download