insertion Trier - problèmes de lecture MIT Intro à Algos

Question

L'introduction MIT aux algorithmes décrit tri par insertion comme:

j'ai écrit cela en Python:

def sort(A): 
    for j in range(1, len(A)): 
     key = A[j]; 
     i = j - 1; 

     # i > 0 should be i >= 0 
     while i > 0 and A[i] > key: 
      A[i + 1] = A[i] 
      i = i - 1; 
     A[i + 1] = key 

    return A 

Cependant la ligne while i > 0 introduit un bug - les deux premières touches sont dans les mauvaises positions. Changer cela pour while i >= 0 résout ce problème. Pourquoi cela ne figure-t-il pas dans le livre MIT Intro? Est-ce que je le lis mal?

Answer 1

L'algorithme dans le livre suppose une indexation de 1 à A.length, inclusivement, ce qui explique pourquoi il commence à un indice de 2. Python a l'indexation de tableau de 0 à len(A) - 1. Vous avez corrigé cela dans votre range, mais vous avez négligé de le corriger dans le test de boucle. Cela résout le problème.

Answer 2

@pjs est exactement exact. J'ajouterai qu'un moyen méthodique de convertir un algorithme écrit pour des tableaux 1-based en 0 sans aucune erreur off-by-1 consiste à utiliser l'algorithme tel quel, sauf soustraire 1 à chaque référence du tableau, puis utiliser l'algèbre pour simplifier. Ici, vous finiriez avec:

def sort(A): 
    for j in range(2, len(A) + 1): # +1 is because Python ranges exclude high limit 
    key = A[j - 1] 
    i = j - 1 
    while i > 0 and A[i - 1] > key: 
     A[i + 1 - 1] = A[i - 1] 
     i = i - 1 
    A[i + 1 - 1] = key 
    return A 

Bien sûr, il est facile de simplifier en supprimant + 1 - 1, puisque c'est l'ajout de zéro! Le résultat fonctionne bien.

Si vous voulez faire le plus joli de code avec la plage extérieure à partir de 1 au lieu de 2, faire la substitution jj = j - 1, qui (en ajoutant 1 aux deux côtés) signifie j = jj + 1:

def sort(A): 
    for jj in range(1, len(A)): 
    key = A[jj + 1 - 1] 
    i = jj + 1 - 1 
    while i > 0 and A[i - 1] > key: 
     A[i] = A[i - 1] 
     i = i - 1 
    A[i] = key 
    return A 

Encore une fois la suppression + 1 - 1 s , nous avons

def sort(A): 
    for jj in range(1, len(A)): 
    key = A[jj] 
    i = jj 
    while i > 0 and A[i - 1] > key: 
     A[i] = A[i - 1] 
     i = i - 1 
    A[i] = key 
    return A 

Cela semble très bien, et je m'arrêterais ici. Mais encore une autre variation est possible avec la substitution ii = i - 1 ou i = ii + 1.

def sort(A): 
    for jj in range(1, len(A)): 
    key = A[jj] 
    ii + 1 = jj 
    while ii + 1 > 0 and A[ii + 1 - 1] > key: 
     A[ii + 1] = A[ii + 1 - 1] 
     ii + 1 = ii + 1 - 1 
    A[ii + 1] = key 
    return A 

Hmmm ... Ces missions à ii air étrange. Mais nous pouvons encore tout redresser avec l'algèbre.

def sort(A): 
    for jj in range(1, len(A)): 
    key = A[jj] 
    ii = jj - 1 # Subtracted 1 from both sides 
    while ii >= 0 and A[ii] > key: # x + 1 > 0 iff x >= 0 
     A[ii + 1] = A[ii] 
     ii = ii - 1 # Subtracted 1 from both sides and simplified 
    A[ii + 1] = key 
    return A 

Et voilà, nous avons le code que vous avez proposé. Fonctionne à chaque fois.