Programmer un des tris les plus populaires, implanté dans la plupart
des langages: le
quick sort. Cet algorithme de tri efficace se
décompose en deux étapes:
- le partionnement: qui consiste à organiser le tableau à
trier selon une valeur pivot (le premier élément du tableau à
trier). Le pivot doit à la suite de cette opération se trouver à sa
place finale avec à sa gauche des éléments (pas nécessairement triés)
inférieurs et à sa droite des éléments (pas nécessairement triés)
supérieurs.
- la récursion: l'étape précédente fait apparaître deux
tableaux: celui à droite de la valeur pivot et celui à gauche. Lancer
le partitionnement de ces deux tableaux.
On voit clairement la récursion inhérente à cette définition:
programmez là ! Vous définirez pour cela une méthode à trois
arguments: une référence sur le tableau à trier, l'indice de l'élément
où doit commencer le tri, et l'indice du dernier élément à trier.
Note: pour placer le premier élément du tableau T à sa
place finale, appliquez l'algorithme suivant où d et f
désignent respectivement l'indice de début et de fin de tableau et
T[i] le i-ème élément de T:
- tant que T[f] est supérieur à T[d], décrémenter f
de 1.
- permuter (s'il y a lieu) T[f] avec T[d]
- incrémenter d de 1.
- tant que T[d] est inférieur à T[f], incrémenter d.
- permuter (s'il y a lieu) T[d] avec T[f]
- décrémenter f
- aller en 1
Inspirez-vous de l'exemple suivant où le nombre en gras représente
le pivot et celui en italique la valeur à permuter.
37 | 2 | 6 | 4 | 89 | 8 | 10 | 12 | 68 | 45 |
12 | 2 | 6 | 4 | 89 | 8 | 10 | 37 | 68 | 45 |
12 | 2 | 6 | 4 | 37 | 8 | 10 | 89 | 68 | 45 |
12 | 2 | 6 | 4 | 10 | 8 | 37 | 89 | 68 | 45 |
Exercice 2
Comparez les performances du quicksort et du tri à bulles pour trier
des tableaux de différente taille (100, 1000, 10000 éléments)
initialisés avec des entiers entre 0 et 1000. Faites le tests dans les
deux situations suivantes:
- un tableau dont les valeurs ont été remplies aléatoirement par des entiers entre 0 et 1000
- un tableau presque trié (pour obtenir un tableau presque trié, triez d'abord ce tableau puis permutez quelques éléments