Les algorithmes de tri entre la théorie et la pratique

Résumé du document

On se propose de présenter un document synthétique sur les algorithmes de tris en présentant leurs principes, leurs complexités, et certaines pistes d'optimisation et puis de les comparer suivant différents critères.

Les tris quadratiques appartenant à cette classe d'algorithmes s'exécutent en O(n²), et ne sont donc pas efficaces (en général) pour des grandes données.
Nous présenterons ici le tri bulles avec 3 variantes :
- Le tri bulles classique
Il s'agit de parcourir le tableau et de comparer deux à deux chaque élément voisin et de les permuter s'ils ne sont pas dans le même ordre et de réitérer ce processus. Le nombre de comparaisons est de l'ordre de n(n-1)/2. Le nombre d'échanges dépendra de la distribution des valeurs et aura comme meilleure valeur 0 si les données sont déjà triées
- Première variante : ajout d'une variable booléenne
On rajoute une variable booléenne qui nous permettra d'arrêter le processus quand on trouve que les données ont été triées et ceci nous évitera de faire des opérations pour rien
- Deuxième variante : ajout d'une deuxième variable booléenne
Ici, on ne va pas utiliser une boucle for pour parcourir le tableau mais plutôt une boucle while qui s'arrêtera quand le tableau sera trié
- Troisième variante : on change la variable du parcours
Pour cette optimisation, on change la variable du parcours pour qu'elle prenne l'indice du dernier emplacement où un échange est survenu.

Extraits

[...] Première variante et deuxième variante: ajout d'une variable booléenne Le mérite de ces deux algorithmes se voit quand on soumet un tableau déjà trié vu qu'il prend ceci en compte et donc le nombre de comparaisons descend pour atteindre n-1 au lieu de pour la formulation classique Troisième variante : on change la variable du parcours Cet algorithme ne présente pas un intérêt majeur et la petite optimisation qu'il met en oeuvre se montre très modeste d'après les résultats expérimentaux (presque la même performance qu'un algorithme de tri bulle normal Tri Sélection Ce tri est indépendant des données entrées et est très régulier (écart type nul pour chaque élément de complexité). Cet algorithme est le plus intuitif et il est aussi le plus lourd en terme de comparaison. [...]

[...] Conclusion générale Chaque algorithme présente des points forts et des points faibles, mais globalement on peut dire que le tri rapide optimisé peut présenter un grand intérêt en général si on n'a pas des a priori sur les données. Néanmoins, le fait de connaître des informations supplémentaires sur les données à trier peut nous pousser à choisir un algorithme plus adapter : en effet le tri insertion s'avère très efficaces quand les données sont presque triées, le tri rapide classique est lui très efficace si les données sont désordonnées et le tri casier si les données sont facilement dénombrables. [...]

[...] En effet la plupart des algorithmes implémentés ne présentent pas en pratique un nombre de comparaisons, de copies ou même d'échanges fixé par la taille des données en entrée. La nature de ces données, à savoir si ces dernières sont triées ou non, influe sur le nombre d'opérations nécessaires à effectuer pour aboutir à des données triées. On s'intéresse donc au nombre moyen d'opérations (copies/échanges/comparaisons) effectuées par chaque algorithme. L'écart-type est également à calculer, car il renseigne sur la "régularité" des performances de chaque algorithme. Pour estimer ces 2 valeurs, on soumet, à taille de données fixe expériences. [...]

[...] Les deux algorithmes qu'on présente ici sont du type diviser pour régner et présentent des performances satisfaisantes par rapport à la classe quadratique. Tri rapide Le tri rapide classique On choisit un pivot et on met compare les éléments par rapport à lui, suit à ceci on partitionne notre tableau et on le trie selon le même principe récursivement Ce tri est très efficace quand les données sont désordonnées, mais il s'avère très inefficace dans le cas de données triées ou ordonnées et sa complexité dans ce pire atteint Le tri rapide optimisé Afin de contourner cette limitation, on effectue un mélange (en temps linéaire) des clés avant le tri afin de rendre le tri plus efficace, ceci nous permettra de garder une complexité en O(n log2 moyenne. [...]

[...] Ce tri ayant pour principe de construire avec les données un tas (un tas est un arbre binaire complet dans lequel tous les fils ont des étiquettes supérieures à leurs pères et donc le minimum se trouve dans la racine, on l'enlève et on remet dans la racine la valeur de la dernière feuille de l'arbre et on reconstruit le tas en log n (car il s'agit d'un arbre binaire complet) et on réitère ce processus pour avoir un algorithme de tri quasi-linéaire ayant une très bonne efficacité. Pour conclure, cette multitude d'algorithmes de tri nous donne un large choix, mais nous impose aussi des contraintes et le véritable défi et d'essayer de trouver le meilleur algorithme qui serait le mieux adapté à chaque situation et savoir connaître ces situations d'une manière automatisée tout en prenant en compte les ressources disponibles (mémoire vs fréquence du microprocesseur). [...]