Comparaison des algorithmes de tri

Les algorithmes de tri sont une partie importante de la gestion des données. AtCprogramming.com , nous proposons des tutoriels pour comprendre les techniques les plus importantes et les plus communes. Chaque algorithme a des forces et des faiblesses particulières et dans de nombreux cas, la meilleure chose à faire est simplement d’utiliser la fonction intégrée qsort. Pour les moments où ce n’est pas une option ou si vous avez juste besoin d’un algorithme de tri rapide et sale, il existe une variété de choix.

La plupart des algorithmes de tri fonctionnent en comparant les données triées. Dans certains cas, il peut être souhaitable de trier un grand nombre de données (par exemple, une structure contenant un nom et une adresse) en fonction d’une partie seulement de ces données.La donnée réellement utilisée pour déterminer l’ordre trié s’appelle la clé.
Les algorithmes de tri sont généralement jugés par leur efficacité. Dans ce cas, l’efficacité fait référence à l’efficacité algorithmique à mesure que la taille de l’entrée augmente et est généralement basée sur le nombre d’éléments à trier. La plupart des algorithmes utilisés ont une efficacité algorithmique de O(n^2) ou O(n*log(n)). Quelques algorithmes de cas particuliers (un exemple est mentionné dans Programming Pearls) peuvent trier certains ensembles de données plus rapidement que O(n*log(n)). Ces algorithmes ne sont pas basés sur la comparaison des éléments triés et reposent sur des tests. Il a été démontré qu’aucun algorithme de comparaison de clés ne peut mieux performer que O(n*log(n)).
De nombreux algorithmes qui ont la même efficacité n’ont pas la même vitesse sur la même entrée. Premièrement, les algorithmes doivent être jugés en fonction de leur efficacité moyenne, dans le meilleur des cas et dans le pire des cas. Certains algorithmes, tels que le tri rapide, fonctionnent exceptionnellement bien pour certaines entrées, mais horriblement pour d’autres. D’autresalgorithmes, tels que le tri par fusion, ne sont pas affectés par l’ordre des données d’entrée.Même une version modifiée de bubble sort peut se terminer en O(n) pour les entrées les plus favorables.
Un deuxième facteur est le « terme constant ». Comme la notation big-O fait abstraction de nombreux détails d’un processus, elle est très utile pour regarder la grande image. Mais une chose qui est abandonnée est la constante devant l’expression: par exemple, O(c * n) est juste O(n). Dans le monde réel, theconstant, c, variera selon différents algorithmes. Un quicksort bien implémenté devrait avoir un multiplicateur constant beaucoup plus petit que le tri de tas.
Un deuxième critère pour juger les algorithmes est leur espace requis – ils nécessitent un espace de travail ou le tableau peut-il être trié en place (sans mémoire supplémentaire au-delà de quelques variables)? Certains algorithmes ne nécessitent jamais d’espace supplémentaire, tandis que d’autres sont plus faciles à comprendre lorsqu’ils sont implémentés avec un espace supplémentaire (le tri de tas, par exemple, peut être effectué en place, mais conceptuellement, il est beaucoup plus facile de penser à un tas séparé). Les exigences d’espace peuvent même dépendre de la structure de données utilisée (tri de fusion sur les tableaux par rapport au tri de fusion sur les listes en lien, par exemple).
Un troisième critère est la stabilité — le tri conserve-t-il l’ordre des clés avec des valeurs égales? La plupart des sortes simples font exactement cela, mais certaines sortes, telles quetrire bon marché, ne le font pas.
Le graphique suivant compare les algorithmes de tri sur les différents critères énoncés ci-dessus; les algorithmes avec des termes constants plus élevés apparaissent en premier, bien qu’il s’agisse clairement d’un concept dépendant de l’implémentation et ne devraient être pris que comme un guide approximatif lors de la sélection entre des types de la même efficacité big-O.

Tri par insertion

td>

	Time
Sort	Average	Best	Worst	Space	Stability	Remarks
Bubble sort	O(n^2)	O(n^2)	O(n^2)	Constant	Stable	Always use a modified bubble sort
Modified Bubble sort	O(n^2)	O(n)	O(n^2)	Constant	Stable	Stops after reaching a sorted array
Selection Sort	O(n^2)	O(n^2)	O(n^2)	Constante	Stable	Même une entrée parfaitement triée nécessite de balayer l’ensemble du tableau
O(n^2)	O(n)	O(n^2)	Constante	Stable	Dans le meilleur des cas (déjà trié), chaque insertion nécessite un temps constant
Tri de tas	O(n*log(n))	O(n*log(n))	O(n*log(n))	Constante	Instable	En utilisant le tableau d’entrée comme stockage pour le tas, il est possible d’obtenir un espace constant
Trier par fusion	O(n*log(n))	O(n* log(n))	O(n* log(n))	Dépend	Stable	Sur les tableaux, le tri par fusion nécessite un espace O(n); sur les listes chaînées, le tri par fusion nécessite un espace constant
Quicksort	O(n*log(n))	O(n *log(n))	O(n^2)	Constante	Stable	Choisir au hasard une valeur pivot (ou mélanger le tableau avant le tri) peut aider à éviter les pires scénarios tels qu’un tableau parfaitement trié.