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?
Aucun commentaire:
Enregistrer un commentaire