Partie 1 : Tri quadratique d’une liste¶

Nous présentons ici quelques méthodes permettant de classer un ensemble d’éléments : nombres ou chaînes de caractères. Nous supposerons dans ce qui suit que le classement doit être réalisé dans l’ordre croissant

1) Tri-extraction :¶

Dans cette méthode, chaque élément est comparé à chacun de ses suivants. Si l’on trouve un élément supérieur à l’un de ses suivants, c’est qu’il n’est pas à sa place : on procède donc à l’échange des deux éléments correspondants.

2) Tri par sélection :¶

Le principe du tri par sélection consiste à parcourir les $n$ éléments de la liste, à déterminer le plus petit élément et à le mettre en première position dans la liste, puis à parcourir les $n-1$ éléments restants, à déterminer le plus petit élément parmi ceux-ci et à le mettre en seconde position dans le tableau trié, et ainsi de suite.

3) Tri-bulle :¶

Le tri bulle consiste à parcourir toute la liste de gauche à droite, en comparant les éléments consécutifs deux à deux, et en les permutant lorsqu’ils sont dans le mauvais ordre : ceci a pour effet d’amener le plus grand élément du tableau en dernière position.

Ainsi, l’élément la plus grande remonte en tête de classement comme une bulle à la surface. Puis on recommence pour les $n-1$ premiers éléments du tableau, en faisant des comparaisons d’éléments consécutifs de gauche à droite, et ainsi de suite jusqu’à ce que tout la liste soit triée. Cet algorithme est stable car un seul élément se déplace à la fois.

4) Tri-insertion :¶

Le tri par insertion consiste à prendre chaque élément $L[i]$ de la liste $L$, à trouver son emplacement $j$ dans la sous liste triée $[L[0], \ldots L[i-1]]$, puis à insérer l’élément $L[i]$ dans la partie triée. L’algorithme est stable et plus efficace que les précédents car on ne fait pas de comparaison inutile.