5.4 Tris récursifs
Exercice 5.11 --- Quicksort.
Le tri Quicksort a été introduit par C.A.R. Hoare en 1960. Il
consiste à prendre un élément au hasard dans le table à
trier. Soit v cet élément. On partitionne le reste du
tableau en deux zones :
-
les éléments plus petit ou égaux à v ;
- les éléments plus grand à v.
Il faut maintenant mettre les éléments plus petits ou égaux
à v en tête de la table, les éléments plus grands en fin
de table et mettre v à sa place définitive entre les deux
zones.
On peut recommencer récursivement cette manipulation sur les deux
partitions ainsi créés tant qu'elles ne sont pas réduites à
un éléments.
Implanter un tri Quicksort.
5.4.2 Tri par fusion
Cette notion ne sera pas abordée dans ce cours.
Pour tout commentaire : Alexandre Sedoglavic.