Algorithme du tri rapide
Le « tri rapide » est un algorithme de tri particulièrement efficace. L'objectif de cette page est d'illustrer le fonctionnement de l'algorithme du tri rapide. Deux versions de l'algorithme de partitionnement sont illustrées ci-dessous.
Algorithme avec partition simple
Le fichier pdf suivant illustre de manière graphique le fonctionnement de l'algorithme sur un tableau de 10 entiers en montrant la chaine des appels récursifs.
(:embed quicksort.pdf:)
L'algorithme utilisé est le suivant :
tri(tab, debut, fin) :
si debut < fin
iPivot ← partition(tab, debut, fin)
tri(tab, debut, iPivot-1)
tri(tab, iPivot+1, fin)
fsi
partition(tab, debut, fin) :
iPivot ← debut
pivot ← tab[debut]
pour i allant de debut+1 a fin
si tab[i] < pivot
tab[iPivot] ← tab[i]
tab[i] ← tab[iPivot+1]
tab[iPivot+1] ← pivot
iPivot++
fsi
fpour
retourner iPivot
Algorithme avec partition optimisée « double parcours »
La vidéo montre le déroulement pas-à-pas de l'algorithme de placement du pivot, implémenté par la fonction placer (voir le code java ci-dessous).
Il est conseillé de visionner la vidéo en ayant le code de la fonction sous les yeux (en ouvrant une deuxième fois cette page dans une autre fenêtre par exemple).
(:video FISDA-QuickSort-Placer.mp4:)
class Tableau {
private int[] tab_;
public void triRapide() {
triRapide_P(0, tab_.length − 1);
}
private void triRapide_P(int min, int max) {
if (min < max) {
int posPivot = placer(min, max);
triRapide_P(min, posPivot−1);
triRapide_P(posPivot+1, max);
}
}
private int placer (int min, int max) {
int pivot = tab_[min];
int gauche = min+1;
int droite = max;
while (gauche <= droite) {
while (tab_[droite] > pivot){
droite−−;
}
while ((gauche <= droite) && (tab_[gauche] <= pivot)){
gauche++;
}
if (gauche < droite) {
tab_[droite ] = tab_[gauche];
tab_[gauche] = tmp;
gauche++;
droite−−;
}
}
tab_[min] = tab_[droite];
tab_[droite ] = pivot;
return droite ;
}
}