Pourquoi les tris lisses ne sont-ils pas plus courants ?

Question

De la lecture ce article de Wikipedia sur les algorithmes de tri, il semblerait que smoothsort soit le meilleur algorithme de tri qui soit. Il est le plus performant dans toutes les catégories : le meilleur, le moyen et le pire. Rien ne le surpasse dans aucune catégorie. Il a également des besoins constants en mémoire. Le seul inconvénient est qu'il n'est pas stable.

Il bat timsort en mémoire, et il bat quicksort à la fois dans le pire des cas et en mémoire.

Mais je n'ai jamais entendu parler de smoothsort. Personne ne le mentionne jamais, et la plupart des discussions semblent tourner autour d'autres algorithmes de tri.

Pourquoi ça ?

Answer 1

Les performances du Big-O sont excellentes pour la publication d'articles, mais dans le monde réel, nous devons également tenir compte des constantes. Quicksort est depuis longtemps l'algorithme de choix pour le tri instable, en place et en mémoire, car il est possible de mettre en œuvre sa boucle interne de manière très efficace et il est très convivial pour le cache. Même si vous pouvez implémenter la boucle interne de smoothsort de manière aussi efficace, ou presque, que celle de quicksort, vous constaterez probablement que son taux d'absence de cache la rend plus lente.

Nous atténuons les pires performances de Quicksort en faisant un peu plus d'efforts pour choisir de bons pivots (afin de réduire le nombre de cas pathologiques) et pour détecter les cas pathologiques. Regardez en haut introsort . Introsort exécute d'abord quicksort, mais passe à heapsort s'il détecte une récursion excessive (ce qui indique un cas pathologique pour quicksort).

Answer 2

Une meilleure asymptotique n'implique pas de meilleures performances (même si c'est souvent le cas). La constante cachée peut être plusieurs fois plus grande, ce qui fait qu'elle est plus lente qu'un autre alogrithme (avec une complexité asymptotique identique ou même pire) sur les tableaux de relativement petite taille (où relativement faible En fait, le tableau peut être de taille arbitraire, 10 %. 100 par exemple. C'est de l'analyse asymptotique). Mais je ne sais rien des constantes cachées de smoothsort.

Par exemple, il y a un algorithme O(n) pire cas en temps pour trouver la statistique d'ordre k, mais il est si complexe que la version pire cas O(n log n) le surpasse dans la plupart des cas.

Il y a aussi une intéressante comparaison :

Comme vous pouvez le constater, Timsort et Smoothsort n'ont pas fait l'affaire. Smoothsort est pire que les tris STL dans tous les cas (même avec std:bitset remplacé par des opérations sur les bits bruts)

Answer 3

Tout d'abord, je dirais que ce n'est pas comme si Smoothsort n'était pas célèbre. Cela dépend du besoin de l'utilisateur et cela dépend aussi de l'utilisateur qui l'utilise ou non.

L'avantage de smoothsort est qu'il est plus proche du temps O(n) si l'entrée est déjà triée à un certain degré, alors que heapsort est en moyenne O(n log n) quel que soit l'état initial trié.

De la Documentation :-

L'algorithme smoothsort doit être capable de garder en mémoire les tailles de tous les tas de la chaîne. Puisque toutes ces valeurs sont distinctes, cela est généralement fait en utilisant un vecteur de bits. De plus, comme il y a au maximum O(log n) nombres dans la séquence, ces bits peuvent être codés en O(1) mots machine, en supposant un modèle de machine transdichotomique. transdichotomique.