Chapitre 4 :
Algorithmes de tri
1. Présentation
2. Tri par sélection
3. Tri à bulles
4. Tri par insertion
5. Tri par fusion
6. Tri rapide
Présentation
Le tri de données signifie, les rangées ou les classées dans un
ordre donné et selon un critère déterminé.
Les données peuvent être dans un tableau, dans une liste, dans un
fichier ou dans un autre structure de données.
Si nous considérons un petit tableau, tel que (7, 1, 15, 8, 2), il est
évidemment facile de l'ordonner pour obtenir (1, 2, 7, 8, 15).
Mais s'il s'agit d'un tableau de plusieurs centaines, voire millions
d’éléments, c'est nettement moins évident.
Tri par sélection
Principe:
on recherche le plus petit élément parmi les n éléments et
on l‘échange avec le premier élément ; puis on recherche le
plus petit élément parmi les n-1 derniers éléments de ce
nouveau tableau et on l‘échange avec le deuxième élément ;
plus généralement, a la k-ième étape, on recherche le plus
petit élément parmi les n - k + 1 derniers éléments du
tableau en cours et on l‘échange avec le k-ième élément.
Tri par sélection
Exemple:
trier en ordre croissant le tableau T suivant:
• Première étape: permutation entre le minimum (-20) et le
premier élément de la partie non triée (80)
• Deuxième étape: permutation entre le minimum (8) et le
premier élément de la partie non triée (45)
Tri par sélection
• Troisième étape: permutation entre le minimum (10) et le
premier élément de la partie non triée (12)
• Quatrième étape: permutation entre le minimum (12) et le
premier élément de la partie non triée (45)
• Cinquième étape: permutation entre le minimum (15) et le
premier élément de la partie non triée (80)
Tri par sélection
• Sixième étape: permutation entre le minimum (45) et le
premier élément de la partie non triée (80)
• Septième étape: le minimum (65) est lui-même le premier
élément de la partie non triée (pas de permutation)
• Puisque la partie non trié ne contient qu’un seule élément, le
tri par sélection s’arrête et le résultat final du tri du tableau T
est le suivant:
Tri à bulles
Principe: consiste à parcourir le tableau de gauche à droite en
comparant les élément consécutifs et en les permutant s’il ne sont
pas dans le bon ordre. Au cour d’un parcour du tableau, les plus
grands éléments remontent de proche en proche vers la droite
comme des bulles vers la surface.
On s’arrête dès que l’on détecte que le tableau est trié: si aucune
permutation n’à été faite au cour d’un parcour.
Tri à bulles
Exemple: trier en ordre croissant le tableau T suivant:
Première étape: Le parcours de la partie non triée du tableau T donne
le résultat suivant:
Deuxième étape: Le parcours de la partie non triée du tableau T donne
le résultat suivant:
Tri à bulles
Troisième étape: Le parcours de la partie non triée du tableau T donne
le résultat suivant:
Quatrième étape: Le parcours de la partie non triée du tableau T
donne le résultat suivant:
Cinquième étape: Le parcours de la partie non triée du tableau T
donne le résultat suivant:
Tri à bulles
Sixième étape:
On constate que lors du parcours des éléments de la partie non
triée il n’y a aucun changement. Ce qui signifie que le tableau T
est trié et le résultat final du tri est le suivant:
Tri par insertion
Principe: consiste à insérer un élément du tableau dans une
partie déjà ordonnée de ce tableau, puis à recommencer avec les
éléments qui restent. La partie de départ qui est trié est le premier
élément.
La liste à trier est divisée en deux parties: partie gauche est triée,
et la partie droite est non trie.
À chaque passage, le premier élément de la partie non triée est
introduite dans la partie triée, de telle sorte que cette dernière
reste triée.
Pour une liste de n éléments , n-1 passage sont nécessaires.
Tri par insertion
Exemple: trier en ordre croissant le tableau T suivant:
Première étape: insertion du deuxième élément (45) dans sa
place (1)
Le résultat d’insertion de l’élément 45 est le suivant:
Tri par insertion
Deuxième étape: insertion du troisième élément (12) dans sa
place (1)
Troisième étape: insertion du quatrième élément (8) dans sa
place (1)
Quatrième étape: insertion du cinquième élément (-20) dans sa
place (1)
Tri par insertion
Cinquième étape: insertion du sixième élément (15) dans sa
place (4)
Sixième étape: insertion du septième élément (65) dans sa place
(6) )
Septième étape: insertion du huitième élément (10) dans sa place
(3)
Tri par fusion
Principe: Le tri fusion repose fondamentalement sur l'algorithme
de fusionnement de deux tableaux triés. Il est naturellement décrit
de façon récursive comme suit:
Si le tableau n'a qu'un seul élément alors
il est déjà trié.
Sinon
Séparer le tableau en deux parties à peu près égales.
Trier récursivement les deux parties avec l'algorithme du tri
fusion.
Fusionner les deux tableaux triés en un seul tableau trié.
Algorithme de fusion de deux listes de taille p et q
on compare les deux premiers des deux listes, on prend le plus
petit et on recommence avec les deux listes restantes. On fait un
total de p + q − 1 comparaisons.
Tri par fusion
Exemple: trier en ordre croissant le tableau T suivant:
Les étapes de déroulement du tri fusion sur le tableau T sont
illustrées par le schéma suivant:
Tri par fusion
Tri rapide
On cherche à trier n éléments. On choisit l’un d’entre eux, appelé
pivot, et on partage les éléments en les positionnant par rapport
au pivot : on place à gauche du pivot ceux qui sont inférieurs ou
égaux au pivot, et à droite ceux qui sont supérieurs. La seconde
phase consiste simplement en deux appels récursifs de
l'algorithme, l'un pour la sous-ensemble gauche et l'autre pour la
sous-ensemble droite.
Tri rapide
Exemple: trier en ordre croissant le tableau T suivant:
On choisit comme pivot l’élément au milieu du tableau.
Première étape: placement du pivot (8) dans sa place (2)
Deuxième étape:
Maintien de l’élément -20 dans sa place (1) car le sous-tableau à
gauche est de taille 1 et placement du pivot (12) du sous-tableau à droit
dans sa place (4).
Tri rapide
Troisième étape:
Maintien de l’élément 10 dans sa place (3) car le sous-tableau à gauche
est de taille 1 et placement du pivot (45) du sous-tableau à droit dans sa
place (6).
Quatrième étape:
Maintien de l’élément 15 dans sa place (5) car le sous-tableau à gauche
est de taille 1 et placement du pivot (80) du sous-tableau à droit dans sa
place (8).
Puisque le tableau restant est de taille 1, le tri rapide s’arrête et le
résultat final du tri du tableau T est le suivant :
