Exercice Algorithme : Le Tri Rapide

Le Tri Rapide

Principe de la méthode

Choisir un élément du tableau appelé pivot,

Ordonner les éléments du tableau par rapport au pivot

Appeler récursivement le tri sur les parties du tableau à gauche et à droite du pivot.

Travail à Faire :

• Réaliser l’Algorithme du Tri Rapide

Correction

Procédure TriRapide (E/S t : Tableau [1..MAX] d'Entier; gauche,droit : Naturel)
Déclaration i,j : Naturel; pivot,x : Entier
 
Début
 
i <-- gauche; 
j <--  droit;pivot t[(i+j)/2]
Répéter
 
Tant que t[i] < pivot 
Faire i <-- i+1
Fin tant que
 
Tant que t[j] > pivot 
Faire j <-- j-1
Fin tant que
 
Si i <= j alors
Echanger(tab[i],tab[j])
I <-- i+1
J <-- j-1
Fin si
 
Jusqu'à ce que i > j
 
Si gauche < j alors
TriRapide(t, gauche, j)
Fin si
 
Si i < droit alors
TriRapide(t, i, droit)
Fin si
 
Fin