Insertion_Sort() Implementierung (Fehler), Python

Question

Ich habe zwei Version der Implementierung von INSERTION SORT; Ich denke, , die gleichwertig sind, aber der zweite gibt eine sortierte Liste falsch zurück. Dies ist der erste:

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 

dies der zweite ist:

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 

ich diese beiden Algorithmus mit diesem C-Array

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

Im ersten Fall getestete Mein Array ist korrekt sortiert. im zweiten Fall meines Ergebnis ist:

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

Der zweite Fall aus dem Pseudo-Code kommt auf meiner Schule Buch. Warum funktioniert es nicht richtig?

Answer 1

Hier ist eine Korrektur des zweiten 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 

Der Unterschied liegt in der >= Richtung > in der while-Schleife. Um zu verstehen, beziehen wir uns auf das Verhalten der Einfügesortierung. Dieser Sortieralgorithmus geht davon aus, dass das Array [0, j-1] sortiert ist und platziert das Element dann an der richtigen Stelle.

Nun lässt vermuten, dass wir wan't [4,3,2,0,5,6,7] zu sortieren, und wir sind jetzt in diesem Zustand:

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

Die ersten drei Elemente in der richtigen Stelle sind und wir brauchen 0 in ihr Recht setzen Position (Index 0). Von i = 2 bis i = 0 ist die Bedingung A[i] > key immer wahr. Also werden wir tun: A [3] = A [2], A [2] = A [1], A [1] = A [0].

Dann verlassen wir die Schleife mit i = -1 und setzen A[i+1] = A[0] = 0.

In Ihrer vorherigen Version würde die Schleife bei 10 stoppen und die letzte Anweisung würde A[0+1] = A[1] = 0 tun. Wenn Sie im Algorithmus [2, 3, 4, 0, 5,6,7] eingeben, ist das ein schlechtes Ergebnis.