Un algorithme de tri est un algorithme permettant d’organiser une collection d’objets selon une relation d’ordre déterminée. Le tri par sélection, ou brute force sorting en anglais, est un algorithme qui trie les valeurs d’un tableau par ordre croissant. La tri par sélection est probablement le plus intuitif des algorithmes de tri, en pseudo-code, il s’écrit de la façon suivante (pour un tableau à trier de n éléments):
procédure tri_selection(tableau t, entier n)
pour i de 0 à n - 2
min ← i
pour j de i + 1 à n - 1
si t[j] < t[min], alors min ← j
fin pour
si min ≠ i, alors échanger t[i] et t[min]
fin pour
fin procédure
Il peut être intéressant d’analyser la complexité de cet algorithme. La complexité correspond à la quantité de ressources (par exemple de temps ou d’espace en mémoire) nécessaire à l’exécution d’un algorithme. Généralement, on calcule le temps d’exécution dans le pire des cas. Pour le tri par sélection, l’algorithme effectue toujours n(n-1)/2 comparaisons, sa complexité est donc O(n²), c’est une complexité dite quadratique. Du point de vue du temps, l’algorithme est inefficace, en effet, les meilleurs algorithmes de tri s’exécutent en temps O(n log n), c’est un complexité dite linéarithmique. Concrètement, cela veut dire que pour un tableau de taille n=1 000 000, il faudrait 2 heures et 48 minutes pour que le tri par sélection finisse d’ordonner le tableau, tandis que le meilleur algorithme de tri, lui, aura besoin de 60 millisecondes.
En revanche, le tri par sélection est un tri en place, c’est à dire que les éléments sont triés directement dans la structure, on n’utilise donc pas plus d’espace en mémoire que la place occupée par le tableau, de ce point de vue, le tri par sélection est intéressant.
L’animation suivante permet de visualiser le fonctionnement du tri par sélection. Les barres blanches représentent les valeurs du tableau. Lorsqu’une barre est rouge, c’est qu’elle est en train d’être comparée par l’algorithme pour rechercher le minimum. Lorsqu’une barre s’affiche en vert, c’est que le programme vérifie sa bonne position dans le tableau.
- Appuyez sur ‘ESPACE’ pour démarrer ou pauser l’animation
- Appuyez sur ‘Z’ pour accélérer l’animation
- Appuyez sur ‘S’ pour ralentir l’animation
- Appuyez sur ‘R’ pour redémarrer l’animation