TP : Algorithmes de tri
1 Introduction
Lorsque les données sont triées, un certain nombre de problèmes devient trés facile à résoudre: recherche,
min, max, le k ème plus petit élément d’une liste.
Trier un ensemble d’objets consiste à les ordonner en fonction d’une relation d’ordre définie sur ces ob-
jets. Nous allons essentiellement nous intéresser à trois algorithmes de tris qui procèdent par comparaison
entre les éléments d’une liste: tri à bulles, tri par selection et le tri par insertion.
Nous allons donc considérer une liste L = [a0 , a1 , . . . , an−1 ] d’éléments d’un ensemble E muni d’un opérateur
de comparaison et nous autoriser les seules opérations suivantes:
comparer deux éléments ai et aj à l’aide de l’opérateur de comparaison ;
permuter deux éléments ai et aj de la liste.
Nous allons voir aussi un autre algorithme de tri qui n’utilise pas la comparaison pour faire le tri: tri par
dénombrement.
Caractéristiques d’un algorithmes de tri:
– Stabilité: On dit d’un algorithme de tri qu’il est stable lorsqu’il préserve l’ordre des indices
entre deux éléments équivalents. Autrement dit, si ai et aj sont équivalents et si i < j, alors
dans la liste triée ai sera toujours placé avant aj .
Tri stable Tri instable
– Tri sur place: l’algorithme ne nécessite pas (ou peu) de mémoire supplémentaire pour trier,
il réarrange directement les éléments dans la liste fournie en paramètre.
2 Tri à bulle: bubble sort
Principe :
Le tri à bulles fait plusieurs passages à travers une listes. il compare deux éléments
adjacents et permute ceux qui ne sont pas en ordre. Chaque passage permet de placer
la plus grande valeur dans sa place convenable.
2.1 Exemple et exercice
Exercice.
Écrire une fonction bubbleSort(L) qui prend en argument une liste L puis trie la
liste L suivant le principe ci-dessus.
Figure 1: Premier passage du tri à bulles
3 Tri par selection: selection sort
Principe :
Sur une liste de n éléments, le principe du tri par sélection est le suivant :
Rechercher le plus petit élément de la liste, et l’échanger (permuter) avec l’élément
d’indice 0 ;
Rechercher le second plus petit élément de la liste, et l’échanger avec l’élément
d’indice 1 ;
Continuer de cette façon jusqu’à ce que le tableau soit entièrement trié.
3.1 Exemple et exercice
Exercice.
1. Écrire une fonction minimum(L, j) qui prend en argument une liste L et un indice
j puis calcule et renvoie l’indice du minimum de la partie de la liste comprise entre
les indices j et len(L) − 1;
2. Écrire une fonction selectionSort(L) qui prend en argument une liste L puis trie
la liste L suivant le principe ci-dessus.
Figure 2: Application du tri par selection à une liste de nombres
4 Tri par insertion: insertion sort
Principe :
Il consiste à parcourir la liste à partir de la position 1 en insérant à chaque étape l’élément
d’indice j dans la partie de la liste (déjà triée) à sa gauche.
4.1 Exemple et exercice
Figure 3: Application du tri par insertion à une liste de nombres
Exercice.
1. Écrire une fonction inserer(L, j) qui prend en argument une liste L et un indice
j puis insère l’élément L[j] dans la partie du tableau L[0:j] supposée triée par
ordre croissant;
2. Écrire une fonction insertionSort(L) qui prend en argument une liste L puis trie
la liste L suivant le principe ci-dessus.
5 Tri par dénombrement: counting sort
Le tri par dénombrement suppose que chacun des n éléments de la liste à trier L (L[i]
avec i ∈ [|0, n − 1|] et n=len(L)) est un entier de l’intervalle 0 à k, k étant un certain
nombre entier.
Principe :
Le principe du tri par dénombrement est de déterminer, pour chaque élément L[i] de
la liste à trier L, le nombre d’éléments inférieurs ou égales à L[i]. Cette information
peut servir à placer l’élément L[i] directement à sa position dans la liste de sortie. Par
exemple, s’il existe 17 éléments inférieurs ou égales à L[i], alors L[i] se trouvera en
sortie à la position d’indice 16. Ce schéma doit être légèrement modifié pour gérer la
situation dans laquelle plusieurs éléments ont la même valeur, puisqu’on ne veut pas tous
les placer à la même position.
1. Créer une liste F qui va contenir le résultat de sortie, i.e: la liste triée;
2. Créer et remplir une liste count par le nombre d’apparition de chaque élément L[i] de la liste L;
3. Calculer pour j = 0, 1, . . . , k, le nombre d’éléments qui sont inférieurs ou égaux à j et ce en gérant
un cumul constamment actualisé de la liste count;
4. Placer chaque élément L[i] à sa bonne place dans la liste de sortie F. Si les n éléments sont tous
distinct, alors pour chaque L[i] la valeur count[L[i]] est la position finale correcte de L[i] dans
la liste de sortie, car il y a count[L[i]] éléments inférieurs ou égaux à L[i]. Comme les éléments
pourraient ne pas être distincts, on décrémente count[L[i]] chaque fois que l’on place une valeur
L[i] dans la liste F. Décrémenter count[L[i]] entraı̂ne que le prochain élément qui a une valeur
égale à L[i], s’il y en a un, ira à la position située juste avant L[i] dans le tableau de sortie.
5.1 Exemple et Exercice
Figure 4: Application du tri par dénombrement
Exercice.
1. Écrire une fonction countingSort(L) qui prend en argument une liste L puis trie la liste L suivant
le principe ci-dessus;
2. Donner la version récursive des algorithmes de tri suivants: Tri à bulle, Tri par selection, Tri
par insertion.