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.

Ce document peut être téléchargé ici.

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). 

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 ;
	}
}