Algorithme de tri - Définition
La liste des auteurs de cet article est disponible ici.
Exemples d'algorithmes de tri
Tris par comparaison
Algorithmes lents
Ces algorithmes sont lents pour plus de 20 éléments parce qu'ils sont en O(n2).
- Tri à bulles : Algorithme quadratique, T(n) = O(n2), en moyenne et dans le pire des cas, stable et en place ; amusant mais pas efficace
- Tri par sélection : Algorithme quadratique, T(n) = O(n2), en moyenne et dans le pire des cas, pas stable si tri sur place ; rapide lorsque l'on a moins de 7 éléments
- Tri par insertion : Algorithme quadratique, T(n) = O(n2), en moyenne et dans le pire des cas, stable et en place. C'est le plus rapide et le plus utilisé pour des listes de moins de 15 éléments ;
Algorithmes plus rapides
- Tri de Shell (shell sort) : Amélioration du tri par insertion, mais pas stable. Complexité: au pire O(nlog2n) pour la série de pas 2p3q et
pour la série de pas 2k − 1. On ne connaît pas de série donnant O(nlogn).
- Tri fusion (merge sort) : O(nlogn) en moyenne et dans le pire des cas, stable mais pas en place ;
- Tri rapide (quick sort) : O(nlogn) en moyenne, mais en O(n2) (quadratique) au pire cas, en place mais pas stable
- Introsort : Amélioration du tri rapide, qui permet une exécution en O(nlogn) dans tous les cas.
- Tri par tas (heap sort) : O(nlogn) en moyenne et dans le pire des cas, en place mais pas stable. Toujours environ deux fois plus lent que le tri rapide, c'est-à-dire aux alentours de O(nlogn), il est donc intéressant de l'utiliser si l'on soupçonne que les données à trier seront souvent des cas quadratiques pour le tri rapide ;
- Tri par ABR : O(nlogn) en moyenne, O(n2) dans le pire des cas. Ce tri est un des plus lents (parmi les tris rapides) et des plus gourmands en mémoire à cause de la structure d'arbre binaire à manipuler. Il est possible de le rendre O(nlogn) dans tous les cas en maintenant un arbre équilibré (Arbre AVL).
- Smoothsort : tri inspiré du tri par tas en utilisant un arbre non inversé, ce tri est très rapide pour les ensembles déjà presque triés, sinon, il est en O(nlogn). Tri en place mais pas stable
Note : on peut facilement obtenir la stabilité d'un tri si l'on associe à chaque élément sa position initiale. Pour cela, on peut créer un deuxième tableau de même taille pour stocker l'ordre initial (on renonce alors au caractère en place du tri).
- On peut faire du tri fusion un tri en place et toujours en O(nlogn) mais l'algorithme effectue plus de copies et est plus compliqué au niveau de la programmation
- On peut rendre sa complexité algorithmique quasi-indépendante des données d'entrée en utilisant un pivot aléatoire ou en appliquant au tableau une permutation aléatoire avant de le trier.
Comparaison des algorithmes de tris en place
Cette comparaison des algorithmes prend en compte le nombre d'accès en écriture dans le tableaux ainsi que le nombre de comparaison. Par exemple pour un tri simple avec 2 éléments, il y a une comparaison, et si échange il y a, deux accès en écriture. Les données à trier sont choisies aléatoirement et le temps moyen est calculé.
Avec ces critères, les algorithmes de tris en place les plus rapides sur des tableaux de moins de 40 éléments sont le tri de Shell et le tri rapide (quicksort). Si le tri par insertion est parmi les premiers pour moins de 10 éléments, sa complexité augmente rapidement au-delà. Le tri par tas est clairement le plus lent. Le smoothsort obtient une position intermédiaire.
Notes :
- le tri de Shell du test utilise les pas optimisés (1, 4, 10, 23...)
- pour le tri rapide, l'utilisation de l'optimisation de Sedgewick ou de l'introsort ne change que très peu la vitesse moyenne sur les petits tableaux.
Lorsque l'on prend un nombre d'éléments moyen (entre 50 et 30 000), le tri en place le plus rapide est le tri rapide. La variante Sedgesort est légèrement plus rapide si l'on choisit bien la taille des petites listes, triées à la fin (ici au plus 8). Ensuite vient le tri de Shell qui n'est plus le plus rapide. Le smoothsort et le tri par tas changent de place. Enfin, la complexité du tri par insertion s'envole.
Comparaisons tris sur grands tableaux
Avec un nombre d'éléments entre 30 000 et 6 000 000 d'éléments, les résultats sont sensiblement les mêmes que pour les tableaux moyens. L'optimisation de Sedgewick est légèrement plus intéressante même si le gain reste marginal. D'autre part, le tri par insertion, de même que le tri à bulles et le tri par sélection, sont beaucoup trop lents pour être utilisés dans ce cas.
| Sedgesort | Quicksort simple | Shellsort | Heapsort | Smoothsort | |
|---|---|---|---|---|---|
| Rapport | 1,8 | 1,9 | 2,8 | 3 | 4,1 |
Tris utilisant la structure des données
- Tri comptage ou Tri par dénombrement (counting sort): Algorithme linéaire, T(n) = O(n), stable mais nécessite l'utilisation d'une seconde liste de même longueur que la liste à trier. Son utilisation relève de la condition que les valeurs à trier sont des entiers naturels dont on connaît les extrema ;
- Tri par base (radix sort) : c'est aussi un tri linéaire dans certaines conditions (moins restrictives que pour le tri par comptage), T(n) = O(n), stable mais nécessite aussi l'utilisation d'une seconde liste de même longueur que la liste à trier ;
- Tri par paquets (bucket sort) : Stable et en complexité linéaire -- T(n) = O(n), part de l'hypothèse que les données à trier sont réparties de manière uniforme sur un intervalle réel [a,b[.
Tris volumineux
Les algorithmes de tri doivent aussi être adaptés en fonction des configurations informatiques sur lesquels ils sont utilisés. Dans les exemples cités plus haut, on suppose que toutes les données sont présentes en mémoire centrale (ou accessibles en mémoire virtuelle). La situation se complexifie si l'on veut trier des volumes de données supérieurs à la mémoire centrale disponible (ou si l'on cherche à améliorer le tri en optimisant l'utilisation de la hiérarchie de mémoire).
Ces algorithmes sont souvent basés sur une approche assez voisine de celle du tri fusion. Le principe est le suivant :
- On découpe le volume de données à trier en sous-ensembles de taille inférieure à la mémoire rapide disponible,
- On trie chaque sous-ensemble en mémoire centrale pour former des "monotonies" (sous-ensembles triés).
- On interclasse ces monotonies.
Tris bande
Dans les débuts de l'informatique, lorsque le coût des mémoires de type disques ou tambours magnétiques était très élévé, les algorithmes de tri pouvaient n'utiliser que la mémoire centrale et les dérouleurs de bandes magnétiques.
En l'absence de disque, il fallait au moins 4 dérouleurs de bandes pour pratiquer un tel tri. Avec 4 dérouleurs (b1, b2, b3, b4), les opérations étaient les suivantes :
- (1) montage (manuel) du fichier à trier sur le dérouleur b1, et de bandes de manœuvre sur b2, b3, b4 ;
- (2) lecture de b1 par paquets successifs qui sont triés en mémoire, pour générer des monotonies qui sont écrites en alternance sur les dérouleurs b3 et b4 ;
- (3) sur le dérouleur b1, démontage de la bande contenant le fichier initial pour le remplacer par une bande de manœuvre ;
- (4) fusion (interclassement) des bandes b3 et b4 pour générer en alternance sur b1 et b2 des monotonies dont le volume est doublé ;
- (5) fusion de b1 et b2 sur b3 b4, et itération de (4) et (5) jusqu'à ce que les monotonies atteignent 50 % du volume à trier ;
- fusion finale pour générer le résultat.
En pratique, compte tenu de la fiabilité moyenne des équipements, on rencontrait donc fréquemment des salles machines avec 8 dérouleurs de bandes.