Qu'est-ce qui fait un mauvais dossier pour un tri rapide?

10

J'apprends sur le tri rapide et je veux illustrer différents tableaux sur lesquels le tri rapide aurait du mal. Le tri rapide que j'ai en tête n'a pas de mélange aléatoire initial, fait 2 partitions et ne calcule pas la médiane.

Jusqu'à présent, j'ai pensé à trois exemples:

[1,2,3,4,5,6,7,8,9,10] - when the array is sorted
[10,9,8,7,6,5,4,3,2,1] - when the array is reversed
[1,1,1,1,1,1,1,1,1,1] - when the array is the same values
[1,1,1,2,2,2,3,3,3,3] - when there are few and unique keys

Par exemple, je ne suis pas trop sûr de celui-ci:

[1,3,5,7,9,10,8,6,4,2]

Alors, qu'est-ce qui rend un tableau avec lequel le tri rapide a du mal par rapport à celui où il est (presque) idéal?

mrQWERTY
la source
2
Comment le pivot est-il sélectionné? Vous avez indiqué deux façons de ne pas le sélectionner, mais pas comment il a été sélectionné.
Winston Ewert
Veuillez donner le pire cas pour QuickSort - quand cela peut-il se produire? sur StackOverflow une lecture. Je trouve également que sorting.at est une belle visualisation des algorithmes de tri.
@WinstonEwert Pivot est sélectionné par le premier élément.
mrQWERTY
@ Renren29 J'ai un peu modifié la question en essayant de la déplacer pour se concentrer sur la raison pour laquelle le tri rapide aurait des difficultés avec un tableau donné plutôt que de chercher des exemples de tableaux (je ne veux pas que les gens vous donnent des réponses [2,1,2,1,2,1,2,1]et que ce soit l'ensemble réponse). Le but de la question serait, idéalement, celui où d'autres personnes pourraient venir et en savoir plus sur le pourquoi (qui a une réponse) plutôt que des exemples (dont il existe d'innombrables).
Vous exécutez le tri rapide en morceaux de 2 éléments? Parce que les implémentations réelles ont tendance à utiliser des tris plus simples pour les petits morceaux. Par exemple, comparer et échanger est beaucoup plus simple que le tri rapide pour N = 2.
MSalters

Réponses:

9

Chaque algorithme de tri a un pire cas, et dans de nombreux cas, le pire des cas est vraiment mauvais, il vaut donc la peine de le tester. Le problème est qu'il n'y a pas de pire des cas uniquement parce que vous connaissez l'algorithme de base.

Les pires cas courants comprennent: déjà triés; triés en sens inverse; presque trié, un élément hors service; toutes les valeurs sont les mêmes; tout de même sauf premier (ou dernier) est supérieur (ou inférieur). Nous avions autrefois une sorte où le pire des cas était un motif en dents de scie particulier, qui était très difficile à prévoir mais assez courant dans la pratique.

Le pire des cas pour le tri rapide est celui qui lui permet de toujours choisir le pire pivot possible, de sorte que l'une des partitions ne comporte qu'un seul élément. Si le pivot est le premier élément (mauvais choix), les données déjà triées ou triées inversement sont le pire des cas. Pour un pivot de médiane de trois données qui sont toutes identiques ou tout simplement le premier ou le dernier est différent fait l'affaire.


Pour le tri rapide, la complexité moyenne est nlogn et le pire des cas est n ^ 2. La raison pour laquelle il vaut la peine de déclencher le comportement du pire des cas est que c'est également le cas qui produit la plus grande profondeur de récursivité. Pour une implémentation naïve, la profondeur de récursivité peut être n, ce qui peut déclencher un débordement de pile. Tester d'autres situations extrêmes (y compris le meilleur des cas) peut être utile pour des raisons similaires.

david.pfx
la source
Je vois, donc l'écart-type de la moyenne détermine vraiment le résultat du partitionnement.
mrQWERTY
"... et dans presque tous les cas, le pire des cas est vraiment mauvais alors ça vaut le coup de le tester." . C'est discutable. Lorsque je regarde ce tableau: en.wikipedia.org/wiki/… je conclus que pour la plupart des "bons" algorithmes de tri (c'est-à-dire avec des O(NlogN)performances moyennes ou meilleures), les cas les plus mauvais et moyens ont la même complexité. Cela suggère que cela ne vaut généralement PAS la peine d'être testé pour le (s) pire (s) cas. (Étant donné que le test est probablement O(N)... ou pire.)
Stephen C
@ Renren29: la médiane de 3 pivots ne sera la première ou la dernière que si 2 ou 3 des valeurs sont identiques. SD n'y entre pas.
david.pfx
@StephenC: De nombreux «bons» algorithmes, y compris le tri rapide, ont n ^ 2 la complexité du pire des cas. Mais voir modifier.
david.pfx
@ david.pfx - "Certains" ... OUI. "Presque tous les" ... NON.
Stephen C
0

Un algorithme s'échappe de la plupart des mauvais cas en utilisant un pivot aléatoire, excluant les éléments continus équivaut à un pivot du partitionnement et une recherche asymétrique. Il recherche en avant un élément supérieur ou égal à un pivot et recherche en arrière un élément inférieur à un pivot.
Je remercie MichaelT, la recherche asymétrique est conçue pour résoudre [2,1,2,1,2,1,2,1].

Le résultat suivant est généré par ma fonction qsort_random (). N = 100 000

usec    call   compare   copy    pattern
80132   62946  1971278   877143  random
47326   57578  1606067   215155  sorted : 0,1,2,3,...,n-1
49927   63578  1628883   338715  sorted in reverse : n-1,n-2,...,2,1,0
55619   63781  1596934   377330  nearly reverse : n-2,n-1,n-4,n-3,...,2,3,0,1
54714   66667  1611454   290392  median-3-killer : n-1,0,1,2,...,n-2
1491    1      99999     4       all values the same : n,n,n,...
1577    1      99999     4       first is higher : n,1,1,1,...
2778    2      156159    10      last is lower : n,n,n,...,n,1
2994    3      199996    100009  a few data : n,...,n,1,...,1
3196    3      199996    50012   zigzag : n,1,n,1,...,n,1
917796  56284  67721985  673356  valley(sawtooth?) : n-1,n-3,...,0,...,n-4,n-2

La plupart des cas sont plus rapides qu'un modèle aléatoire. Le modèle de vallée est un mauvais cas pour la plupart des sélections de pivot.

qsort(3)       usec = 14523   call = 0      compare = 884463    copy = 0
qsort_head()   usec = 138609  call = 99999  compare = 8120991   copy = 1214397
qsort_middle() usec = 664325  call = 99999  compare = 52928111  copy = 1036047
qsort_trad()   usec = 118122  call = 99999  compare = 6476025   copy = 1337523
qsort_random() usec = 295699  call = 58806  compare = 19439952  copy = 732962
qsort_log2()   usec = 66411   call = 63987  compare = 1597455   copy = 944821

qsort_log2 () échappe au mauvais cas en sélectionnant un pivot dans les éléments log2 (N).
qsort (3) utilise la bibliothèque GNU qui est une sorte de fusion de tri d'index.
qsort_trad () sélectionne un pivot dans les premier, milieu et dernier éléments.
qsort_random () et qsort_log2 () n'utilisent pas l'échange.
Les programmes et scripts Source C sont publiés dans github .

Leorge Takeuchi
la source