Quelle est la manière la plus rapide de l'algorithme de tri d'une liste chaînée?

Question

Je suis curieux de savoir si O(n log n) est le meilleur une liste chaînée peut faire.

Answer 1

Il est raisonnable de s'attendre à ce que vous ne pouvez pas faire mieux que O(N log N) en temps d'exécution.

Cependant, la partie la plus intéressante est de déterminer si vous pouvez les trier en place, de manière stable, dans le pire des cas, le comportement et ainsi de suite.

Simon Tatham, de Mastic fame, explique comment trier une liste liée avec la fusion de tri. Il conclut avec les commentaires suivants:

Comme tout se respecte algorithme de tri, ce qui a temps d'exécution O(N log N). Parce que c'est Mergesort, le pire temps d'exécution est toujours en O(N log N); il n'y a pas de cas pathologiques.

Auxiliaire de stockage exigence est faible et constante (c'est à dire un peu de variables à l'intérieur de la routine de tri). Grâce à la nature des comportements différents de listes de tableaux, ce Mergesort mise en œuvre évite de O(N) auxiliaire de stockage des coûts normalement associés à l'algorithme.

Il est aussi un exemple d'implémentation en C qui travail pour à la fois individuellement et doublement des listes liées.

@Jørgen Fogh mentionne ci-dessous, big-O notation peut en cacher une constante facteurs qui peuvent causer un algorithme de mieux performer en raison de la localité de mémoire, en raison d'un faible nombre d'éléments, etc.

Answer 2

Selon un certain nombre de facteurs, il peut effectivement être plus rapide pour copier la liste dans un tableau et ensuite utiliser un Quicksort.

La raison de ce qui pourrait être plus rapide qu'un tableau est beaucoup mieux cache de performance d'une liste liée. Si les nœuds de la liste sont dispersés dans la mémoire, vous peut-être générer le cache toute la place. Puis de nouveau, si le tableau est grand, vous obtiendrez le cache de toute façon.

Mergesort parallelises mieux, de sorte qu'il peut être un meilleur choix si vous le souhaitez. Il est également beaucoup plus rapide si vous effectuez directement sur la liste chaînée.

Depuis les deux algorithmes s'exécuter en O(n * log n), prise d'une décision éclairée impliquerait de profilage à la fois sur la machine que vous souhaitez exécuter.

--- EDIT

J'ai décidé de tester mon hypothèse et a écrit un C-programme qui a mesuré le temps (à l'aide d' clock()) nécessaire pour trier une liste d'entiers. J'ai essayé avec une liste liée, où chaque nœud a été attribué malloc() et une liste liée, où les nœuds sont disposées de façon linéaire dans un tableau, les performances du cache serait mieux. J'ai comparé avec le haut-qsort, ce qui inclus la copie de tout, de la fragmentation de la liste à un tableau et copie le résultat de retour à nouveau. Chaque algorithme a été exécuté sur le même 10 ensembles de données et les résultats ont été en moyenne.

Ce sont les résultats:

N = 1000:

Fragmenté liste avec fusion tri: 0.000000 secondes

Tableau avec qsort: 0.000000 secondes

Paniers liste avec fusion tri: 0.000000 secondes

N = 100000:

Fragmenté liste avec fusion tri: 0.039000 secondes

Tableau avec qsort: 0.025000 secondes

Paniers liste avec fusion tri: 0.009000 secondes

N = 1000000:

Fragmenté liste avec fusion tri: 1.162000 secondes

Tableau avec qsort: 0.420000 secondes

Paniers liste avec fusion tri: 0.112000 secondes

N = 100000000:

Fragmenté liste avec fusion tri: 364.797000 secondes

Tableau avec qsort: 61.166000 secondes

Paniers liste avec fusion tri: 16.525000 secondes

Conclusion:

Au moins sur ma machine, la copie dans un tableau est bien utile pour améliorer les performances du cache, puisque vous avez rarement complètement emballé liste liée dans la vraie vie. Il convient de noter que ma machine a 2.8 GHz Phenom II, mais seulement 0,6 GHz RAM, de sorte que le cache est très important.

Answer 3

C'est un joli petit article sur ce sujet. Sa conclusion empirique est que Treesort est le meilleur, suivi par Quicksort et Mergesort. Les sédiments de tri, le tri à bulles, tri de la sélection d'effectuer très mal.

UNE ÉTUDE COMPARATIVE DE LA LISTE LIÉE ALGORITHMES DE TRI par Ching-Kuang Shene

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.9981

Answer 4

Comparaison sortes (c'est à dire celles qui sont basées sur la comparaison des éléments) ne peut pas être plus rapide que l' n log n. Il n'a pas d'importance ce que la structure de données sous-jacente. Voir Wikipedia.

D'autres types de sorte que l'profiter qu'il y a beaucoup d'éléments identiques dans la liste (comme le comptage, le tri) ou de la distribution attendue des éléments dans la liste, sont plus rapides, mais je ne peux pas penser à tout qui fonctionnent particulièrement bien sur une liste liée.

Answer 5

Comme indiqué à plusieurs reprises, la limite inférieure sur la comparaison de la fonction de tri pour les données générales va être O(n log n). Brièvement resummarize ces arguments, il y a n! différentes façons d'une liste peut être triée. Toute sorte de comparaison de l'arbre qui a n! (qui est en O(n^n)) finale sortes aura besoin d'au moins log(n!) comme sa hauteur: cela vous donne un O(log(n^n)) limite inférieure, qui est O(n log n).

Ainsi, pour les données générales sur une liste liée, le meilleur de tri qui vont travailler sur des données qui permet de comparer deux objets va être O(n log n). Toutefois, si vous avez un domaine limité de choses à travailler, vous pouvez améliorer le temps qu'il faut (au moins proportionnelle à n). Par exemple, si vous travaillez avec des entiers, ne dépassant pas une certaine valeur, vous pouvez utiliser le Comptage de Tri ou Tri Radix, car ils utilisent les objets précis vous êtes de tri pour réduire la complexité avec la proportion de n. Soyez prudent, cependant, ces ajouter quelques autres choses à la complexité que vous pouvez ne pas tenir compte (par exemple, de Comptage, de Tri et de tri Radix les ajouter dans les facteurs qui sont basés sur la taille des nombres que vous êtes le tri, O(n+k) où k est la taille du plus grand nombre de Comptage, de Tri, par exemple).

Aussi, si vous avez des objets qui ont une parfaite hachage (ou au moins une table de hachage que les cartes de toutes les valeurs différemment), vous pouvez essayer d'utiliser un comptage ou de tri radix sur leurs fonctions de hachage.