Le tri rapide
Le pivot, la partition de Lomuto, la récursion sur les deux côtés, le cas moyen en n log n, le pire cas quadratique et les choix de pivot qui l'évitent, le tri en place et non stable.
- 25 cartes
- 4 thèmes
- Gratuit
Le programme, thème par thème
Le poids de chaque thème suit celui que lui donne l'examen.
- Notions
- Questions
- Ranger et relier
- Les chiffres
Quelques cartes du deck
Tri rapide : de quoi s'agit-il ?
Voir la réponse
Tri qui range les éléments autour d'une valeur choisie, plus petits d'un côté et plus grands de l'autre, puis recommence sur chaque côté.
Le travail se fait à l'aller, dans la partition : une fois le pivot à sa place définitive, il n'y a plus rien à réunir au retour de la récursion.
Quel tableau obtient-on après la partition de Lomuto de
[7, 2, 9, 4, 5](pivot en dernière case), et à quel indice se trouve le pivot ?[2, 4, 5, 7, 9], pivot à l'indice 2[2, 4, 5, 7, 9], pivot à l'indice 4[2, 7, 9, 4, 5], pivot à l'indice 1[7, 2, 4, 5, 9], pivot à l'indice 3
Voir la réponse
[2, 4, 5, 7, 9], pivot à l'indice 2Le pivot est 5. 2 est échangé avec 7, puis 4 avec 7 (qui prend sa place) : [2, 4, 9, 7, 5]. Le pivot est enfin échangé avec 9, la première valeur supérieure, ce qui donne [2, 4, 5, 7, 9] avec 5 en case 2.
Le tri rapide coûte … en moyenne et … dans le pire cas.
Voir la réponse
Le tri rapide coûte O(n log n) en moyenne et O(n²) dans le pire cas.
Si chaque partition coupe à peu près au milieu, il y a log n niveaux de n comparaisons. Si elle détache un seul élément, il y a n niveaux : n + (n−1) + … + 1 comparaisons.
Pivot : de quoi s'agit-il ?
Voir la réponse
Valeur choisie dans le tableau qui sert de frontière : après la partition, les éléments qui lui sont inférieurs ou égaux sont à sa gauche, les plus grands à sa droite.
Un pivot proche de la médiane coupe le tableau en deux moitiés égales ; un pivot extrême ne détache qu'un élément et dégrade le tri.