Impasse logique dans une insertion simple Trier

Question

Je m'apprends Python et j'ai des difficultés avec un concept relativement simple. Le but est de trier une liste dans l'ordre croissant en utilisant le tri par insertion. Voici le 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] # this is the not understood point 
      i = i - 1 
     A[i+1] = key 
    print A 

Je ne comprends pas comment fonctionne l'étape en gras. Par exemple, si j'avais une liste de [6,5,4,3,1] et que j'arrivais à la deuxième itération, ma liste ne serait-elle pas maintenant [6,6,4,3,1]? J'affecte A [i + 1] (dans le tout premier cas ce serait 5) la valeur de A [i] (6 dans le premier cas). Qu'est-il arrivé à mon 5? Ma première tentative le code était:

def InsertionSort(A): 
    for j in range(1, len(A)): 
     key = A[j] 
     i = j - 1 
     while (i >=0) and (A[i] > key): 
      temp = A[i+1] 
      A [i+1] = A[i] 
      A[i] = temp 
      i = i - 1 
     A[i+1] = key 
    print A 

Cette méthode fonctionne aussi. Je ne comprends pas pourquoi le premier fait aussi bien. Quelqu'un veut-il prendre un coup de couteau?

Answer 1

Si vous commencez avec [6,5,4,3,1] les itérations seront les suivantes:

Première étape:

[6,5,4,3,1] 
    ## first number sorted` 

Deuxième étape (j=2):

key <- 5 

A <- [6,6,4,3,1], i <- -1 
    ## the 5 will be overridden but is still save in the key variable 

A <- [5,6,4,3,1]   
    ## A[i+1] = key will restore the 5 

La seule valeur qui peut obtenir " perdu "est celui contenu dans A[j]. Mais cette valeur est toujours enregistrée dans la variable key et peut donc être restaurée à la toute dernière étape.

Answer 2

Je pense que c'est juste à cause de la ligne A[i+1]=key.

Le premier algorithme effectue les opérations suivantes: Considérez la liste [1,2,4,5,3], supposons que nous sommes dans l'itération où j=4, à savoir que nous considérons élément de la liste 3. Le algorighm stocke l'élément 3 dans key et vérifie les éléments suivants:

[1,2,4,5,3] 
    ^ 5>3 (key) => move 5 forward by 1 => [1,2,4,5,5] 
[1,2,4,5,5] 
    ^ 4>3 (key) => move 4 forward by 1 => [1,2,4,4,5] 
[1,2,4,4,5] 
^  2<3 => stop inner while loop 
now, make A[i+1]=key (remember: key is 3): 
[1,2,3,4,5] 

Contrairement à ce qui précède, le deuxième algorithme en fait swaps les éléments de chaque itération:

[1,2,4,5,3] 
    ^ 5>3 (key) => swap 5 and 3 => [1,2,4,3,5] 
[1,2,4,3,5] 
    ^ 4>3 (key) => swap 4 and 3 => [1,2,3,4,5] 
[1,2,3,4,5] 
^  2<3 => stop while loop 
now, make A[i+1]=key (remember: key is 3): (this is unnecessary!) 
[1,2,3,4,5]