sorte d'insertion dans Introduction à l'algorithme

Question

dans une introduction à l'algorithme 2e édition, j'ai trouvé le tri par insertion code pseudo

INSERTION-SORT(A) 
1 for j <- 2 to length[A] 
2  do key <- A[j] 
3   //Insert A[j] into the sorted sequence A[1 □ j - 1]. 
4   i <- j - 1 
5   while i > 0 and A[i] > key 
6   do A[i+1] <- A[i] 
7    i <- i -1 
8   A[i + 1] <- key 

, mais je ne peux pas comprendre comment fonctionne ici échange.

Je pense qu'il a besoin d'une opération d'échange comme celui-ci

INSERTION-SORT(A) 
1 for j <- 2 to length[A] 
2  do key <- A[j] 
3   //Insert A[j] into the sorted sequence A[1 □ j - 1]. 
4   i <- j - 1 
5   while i > 0 and A[i] > key 
6   do temp <- A[i+1] 
7    A[i+1] <- A[i] 
8    A[i] <- temp 
9    i <- i -1 
10   A[i + 1] <- key 

ai-je reçu quelque chose de mal? aidez s'il vous plaît

Answer 1

Ce qui se passe dans le tri par insertion n'est pas un échange.

Il déplace chaque élément supérieur à celui que vous souhaitez insérer par un index descendant de la fin de la section actuellement triée, puis insère le nouvel enregistrement au bon endroit après le déplacement de l'ancienne valeur.

Answer 2

mais je ne peux pas comprendre comment fonctionne l'échange ici.

Non, ce n'est pas le cas.

La valeur est déjà enregistrée au début.

Il sauve j puis se déplace tous les autres éléments jusqu'à ce qu'il trouve la place

Answer 3

j'éprouve le même problème. Ci-dessous le code en C qui implémente correctement le pseudo-code ci-dessus. La partie délicate à ce sujet était que le pseudo-code utilisait des notations de matrice basées sur 1 contrairement à la plupart des langages de programmation!

#include <stdio.h> 

int main(void) 
{ 
    int A[] = { 50, 20, 10, 40, 60, 30 }; 
    int j, key, len, i; 
    len = (sizeof(A))/(sizeof(A[0])); 

    for (j = 1; j < 6; j++) { <-- Change here 
     key = A[j]; 
     // Insert key into the sorted sequence A[1 .. j - 1]. 
     i = j - 1; 
     while (i >= 0 && A[i] > key) { <-- Change here 
      A[i + 1] = A[i]; 
      i--; 
     } 
     A[i + 1] = key; 
    } 

    for (int z = 0; z < len; z++) { 
     printf("%d ", A[z]); 
    } 
    printf("\n"); 
} 

Answer 4

Le code effectue un «échange multiple», plus précisément une rotation de k éléments par une position, en place. Cela prend une seule variable auxiliaire key, comme le fait un échange.