Le problème du tri :

Un algorithme de tri est un algorithme qui résout un problème de tri :

• Entrée : une séquence (liste) de n objets $( a_0, a_1, \dots, a_{n-2}, a_{n-1} )$. Ces objets peuvent être des entiers, des chaînes de caractères, etc., mais il faut qu’on puisse les ordonner par une relation d’ordre.
• Sortie : un réarrangement ($a’_0, a’_1, \dots, a’_{n-2}, a’_{n-1} $) de la séquence d’entrée tel que :$ ( a’_0 \leq a’_1 \leq \dots \leq a’_{n-2} \leq a’_{n-1} )$. Ce réarrangement peut être effectué sur place par modification du même conteneur (liste) de la séquence initiale ou par création d’un nouveau conteneur pour la séquence ordonnée.

Importance en informatique :

Le tri est historiquement un problème majeur en informatique pour plusieurs raisons :

• on a souvent besoin de trier des données (notes, noms, photos, etc.)
• les algorithmes de tri sont des sous-programmes indispensables à de nombreuses applications (gestionnaires de fenêtres graphiques, compilateurs, etc.)
• la diversité des algorithmes de tri qui ont été développés présente un intérêt pédagogique dans l’apprentissage de l’algorithmique.

Dans ce chapitre, pour simplifier, on se cantonnera au tri de listes de nombres.

Tri par selection

Principe

Le principe du tri par sélection d’une liste \( L = [L[0], L[1], \dots, L[\text{len}(L)-1]] \):

• Pour chaque entier \( i \) ( \( 0 \leq i \leq \text{len}(L)-2 \) ):
  • parcourir les éléments \( L[i], L[i+1], \dots, L[\text{len}(L)-1] \), retenir l’indice \( k \) du plus petit.
  • placer au rang \( i \) le plus petit élément d’indice \( k \) (en échangeant \( L[i] \) et \( L[k] \)).

Code Python

Ecris le code Python pour l’algorithme précédent et le compare avec le code proposé

Code proposé

Tri par insertion

Principe

La technique consiste à considérer chaque élément à trier, un par un et à l’insérer en bonne place relative dans la partie des éléments déjà triés aux étapes précédentes. À chaque étape, l’insertion d’un élément est effectuée.

• Au départ, L[0] est l’élément de référence.
• À l’étape 1, l’élément L[1] est placé correctement par rapport à la partie déjà triée L[:1], c’est-à-dire uniquement L[0].
• À la i-ème étape, L[i] est donc inséré dans la sous-liste L[:i].

Code Python

Ecris le code Python pour l'algorithme précédent et le compare avec le code proposé

Code proposé

Tri bulle (ou par échange)

Principe

La technique d’échange consiste à comparer les éléments de la liste, 2 par 2, et à les permuter (ou échanger) s’ils ne sont pas dans le bon ordre, jusqu’à ce que la liste soit complètement triée. Le tri Bulle effectue des comparaisons entre voisins :

• À la première étape, L[0] et L[1] sont comparés et éventuellement permutés. Ensuite, l’algorithme compare L[1] et L[2], et ainsi de suite jusque L[n-2] et L[n-1].
  Etant parti de L[0] jusqu’à L[n-2], on peut voir qu’après cette première étape, L[n-1] contiendra le maximum des valeurs de L, la sous-liste de L d’indices 0..(n-2) contenant les autres valeurs déjà légèrement réorganisées.
• À la 2ème étape, on recommence donc les comparaisons/échanges pour les valeurs entre L[0] et L[n-2], ce qui aura pour effet de mettre en place dans L[n-2], le second maximum et de réorganiser à nouveau légèrement les autres valeurs dans la sous-liste de L d’indices 0..(n-3).
• À la ième étape, on devra donc réorganiser la sous-liste de L d’indices 0..(n-i).

Code Python

Ecris le code Python pour l'algorithme précédent et le compare avec le code proposé

Code proposé

Complexité

Pour tout ces principes, la complexité est de $O(n^2)$

Tri par Fusion

Principe

• Partant d’une liste d’éléments à trier, on commence par diviser cette liste en deux sous-listes (presque de même taille).
• On trie les deux sous-listes.
• Puis on fusionne les sous-listes triées.
• Une liste à un élément est triviale à trier et forme la condition d’arrêt de la procédure récursive.

Code Python

Ecris le code Python pour l'algorithme précédent et le compare avec le code proposé

Code proposé

Complexité

La complexité du tri par fusion est de $O(n.log(n))$