mardi 14 juin 2016

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?

Aucun commentaire:

Enregistrer un commentaire