quicksort cas spécial – semble être un algorithme défectueux de K & R

J’ai un problème de compréhension de l’algorithme Quicksort (version simplifiée sans pointeurs) de K & R. Dave Gamble a déjà fourni une explication détaillée . Cependant, j’ai remarqué qu’en commençant par une chaîne légèrement modifiée, nous ne pouvons obtenir aucun échange pendant plusieurs boucles de la boucle for. Tout d’abord le code:

void qsort(int v[], int left, int right) { int i, last; void swap(int v[], int i, int j); if (left >= right) /* do nothing if array contains */ return; /* fewer than two elements */ swap(v, left, (left + right)/2); /* move partition elem */ last = left; /* to v[0] */ for (i = left + 1; i <= right; i++) /* partition */ if (v[i] < v[left]) swap(v, ++last, i); swap(v, left, last); /* restore partition elem */ qsort(v, left, last-1); qsort(v, last+1, right); } 

Procédure pas à pas à mon avis:

nous commençons par CADBE; gauche = 0; à droite = 4; D est le pivot donc selon l’algorithme nous échangeons D avec C pour obtenir DACBE

dernier = gauche = 0

i = 1 if (v 1 <v [0]) il est vrai, nous échangeons donc v 1 (car last est incrémenté avant l'opération) avec v 1, donc rien ne change, last = 1, toujours avec DACBE;

maintenant i = 2 if (v [2] true, nous échangeons donc v [2] avec v [2] rien n’a encore changé; dernier = 2

maintenant i = 3 si (v [3] vrai, nous échangeons v [3] avec v [3] rien n’a changé de nouveau (!), dernier = 3

Donc, apparemment, quelque chose ne va pas, l’algorithme ne fait rien. Vos avis ont beaucoup apprécié. Je dois me tromper, les auteurs sont meilleurs que moi; D Merci d’avance!

La boucle va de left + 1 à right inclus . Lorsque i=4 , le test échoue et le last n’est pas incrémenté.

Ensuite, les appels récursifs sortingent BACDE avec left=0,right=2 et left=4,right=4 . (Ce qui est correct quand D est le pivot.)

Eh bien, il se trouve que votre sous-tableau d’entrée ACBE est déjà partitionné par D ( ACB est inférieur à D et E supérieur à D ). Il n’est donc pas surprenant que le cycle de partitionnement n’échange aucune valeur physiquement.

En réalité, il n’est pas correct de dire qu’il “ne fait rien”. Il ne réorganise rien dans le cycle, car vos données d’entrée n’ont pas besoin d’être réorganisées. Mais il fait toujours une chose: il trouve la valeur de last qui indique où se terminent les petits éléments et commence par les plus grands, c’est-à-dire qu’il sépare ACBE en parties ACB et E Le cycle se termine par last == 3 , qui est le sharepoint partitionnement des étapes récursives ultérieures.