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

Ce fichier pdf illustre de manière graphique le fonctionnement de l'algorithme sur un tableau de 10 entiers en montrant la chaine des appels récursifs.

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 »

Cette 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 la vidéo dans une autre fenêtre par exemple).

class Tableau {

	private int[] tab_;

	public Tableau(int[] tab){
        	this.tab_ = 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) {
				int tmp = tab_[droite];
				tab_[droite ] = tab_[gauche];
				tab_[gauche] = tmp;
				gauche++;
				droite−−;
			}
		}

		tab_[min] = tab_[droite]; 
		tab_[droite ] = pivot; 

		return droite ;
	}

	public String toString(){
		return Arrays.toString(tab_);
	}

	public static void main(String[] args){
		Tableau mytab = new Tableau(new int[]{5, 4, 3, 2, 3});
		System.out.println(mytab);

		mytab.triRapide();
		System.out.println(mytab);
	}
}