Lorenzo Vannucchi - 1 year ago 40

Python Question

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.

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.

Source (Stackoverflow)