Was ist der schnellste Algorithmus zum Sortieren einer verknüpften Liste?

Ich bin gespannt, ob O (n log n) das Beste ist, was eine verknüpfte Liste tun kann.

Es ist vernünftig zu erwarten, dass Sie in der Laufzeit nicht besser als O (N log N) arbeiten können .

Der interessante Teil besteht jedoch darin, zu untersuchen, ob Sie es stabil , im Worst-Case-Verhalten und so weiter sortieren können.

Simon Tatham, von Putty Fame, erklärt, wie man eine verknüpfte Liste mit merge sort sortiert . Er schließt mit folgenden Kommentaren:

Wie bei jedem selbstsortierenden Sortieralgorithmus hat dies die Laufzeit O (N log N). Da dies Mergesort ist, ist die Worst-Case-Laufzeit immer noch O (N log N); Es gibt keine pathologischen Fälle.

Der zusätzliche Speicherbedarf ist klein und konstant (dh einige Variablen innerhalb der Sortierroutine). Dank des inhärent unterschiedlichen Verhaltens von verknüpften Listen aus Arrays vermeidet diese Mergesort-Implementierung die O (N) -Speicherkosten, die normalerweise mit dem Algorithmus verbunden sind.

Es gibt auch eine Beispielimplementierung in C, die sowohl für einfach als auch doppelt verknüpfte Listen funktioniert.

Wie @ Jørgen Fogh unten erwähnt, kann die Groß-O-Notation einige konstante Faktoren verbergen, die dazu führen können, dass ein Algorithmus aufgrund von Speicherlokalität aufgrund einer geringen Anzahl von Elementen usw. besser abschneidet.

Abhängig von einer Reihe von Faktoren kann es tatsächlich schneller sein, die Liste in ein Array zu kopieren und dann ein Quicksort zu verwenden .

Der Grund dafür könnte sein, dass ein Array eine viel bessere Cache-Performance als eine verknüpfte Liste hat. Wenn die Knoten in der Liste im Speicher verteilt sind, generieren Sie möglicherweise Cache-Misses überall. Wenn das Array groß ist, werden Sie trotzdem Cache-Misses bekommen.

Mergesort ist besser parallelisierbar, daher könnte es eine bessere Wahl sein, wenn Sie das möchten. Es ist auch viel schneller, wenn Sie es direkt in der verknüpften Liste ausführen.

Da beide Algorithmen in O (n * log n) laufen, würde eine fundierte Entscheidung bedeuten, sie auf der Maschine zu profilieren, auf der Sie sie ausführen möchten.

— BEARBEITEN

Ich beschloss, meine Hypothese zu testen und schrieb ein C-Programm, das die Zeit (unter Verwendung von clock() ) zum Sortieren einer verknüpften Liste von Ints maß. Ich versuchte mit einer verbundenen Liste, in der jeder Knoten mit malloc() und einer verbundenen Liste zugewiesen wurde, in der die Knoten in einem Array linear ausgebreitet wurden, also würde die Zwischenspeicherleistung besser sein. Ich habe diese mit dem integrierten qsort verglichen, der das Kopieren von allem von einer fragmentierten Liste in ein Array und das erneute Kopieren des Ergebnisses beinhaltete. Jeder Algorithmus wurde auf denselben 10 Datensätzen ausgeführt und die Ergebnisse wurden gemittelt.

Dies sind die Ergebnisse:

N = 1000:

Fragmentierte Liste mit merge sort: 0.000000 Sekunden

Array mit qsort: 0,000000 Sekunden

Gepackte Liste mit merge sort: 0.000000 Sekunden

N = 100000:

Fragmentierte Liste mit merge sort: 0,039000 Sekunden

Array mit qsort: 0,025000 Sekunden

Gepackte Liste mit merge sort: 0.009000 Sekunden

N = 1000000:

Fragmentierte Liste mit merge sort: 1.162000 Sekunden

Array mit qsort: 0.420000 Sekunden

Gepackte Liste mit merge sort: 0.112000 Sekunden

N = 100000000:

Fragmentierte Liste mit merge sort: 364.797000 Sekunden

Array mit qsort: 61.166.000 Sekunden

Gepackte Liste mit merge sort: 16.525000 Sekunden

Fazit:

Zumindest auf meinem Rechner lohnt sich das Kopieren in ein Array, um die Cache-Performance zu verbessern, da Sie im realen Leben selten eine vollständig gepackte Liste haben. Es sollte bemerkt werden, dass meine Maschine einen 2.8GHz Phenom II, aber nur 0.6GHz RAM hat, so ist der Cache sehr wichtig.

Vergleichsarten (dh solche, die auf Vergleichselementen basieren) können unmöglich schneller als n log n . Es spielt keine Rolle, was die zugrunde liegende Datenstruktur ist. Siehe Wikipedia .

Andere Arten von Sortierungen, die Vorteile daraus ziehen, dass viele identische Elemente in der Liste vorhanden sind (wie z. B. die Zählsortierung), oder eine erwartete Verteilung von Elementen in der Liste, sind schneller, obwohl mir nichts besonders gut gefällt auf einer verknüpften Liste.

Wie oft erwähnt, wird die untere Grenze bei der vergleichsbasierten Sortierung für allgemeine Daten O (n log n) sein. Um diese Argumente kurz zusammenzufassen, gibt es n! verschiedene Möglichkeiten, wie eine Liste sortiert werden kann. Jede Art von Vergleichsbaum, der n hat! (was in O (n ^ n) ist) mögliche finale Sortierungen wird mindestens log (n!) als seine Höhe benötigen: das gibt dir eine O (log (n ^ n)) untere Grenze, die O (n ist) log n).

Für allgemeine Daten in einer verknüpften Liste wird daher die bestmögliche Sortierung für alle Daten, die zwei Objekte vergleichen können, O (n log n) sein. Wenn Sie jedoch eine eingeschränkte Domäne von Dingen haben, in denen Sie arbeiten können, können Sie die benötigte Zeit verbessern (zumindest proportional zu n). Wenn Sie beispielsweise mit Ganzzahlen arbeiten, die nicht größer als ein bestimmter Wert sind, können Sie ” Zählen” oder ” Radix sortieren” verwenden, da diese die spezifischen Objekte verwenden, die Sie sortieren, um die Komplexität im Verhältnis zu n zu reduzieren. Seien Sie jedoch vorsichtig, diese fügen der Komplexität einige andere Dinge hinzu, die Sie möglicherweise nicht berücksichtigen (zum Beispiel addieren die Sortier- und Radix-Sortierung Faktoren, die auf der Größe der von Ihnen sortierten Zahlen basieren, O (n + k) ), wobei k die Größe der größten Zahl für zählende Sortierung ist, zum Beispiel).

Wenn Sie Objekte mit einem perfekten Hash haben (oder zumindest einen Hash, der alle Werte unterschiedlich abbildet), könnten Sie versuchen, eine Zähl- oder Radix-Sortierung für ihre Hash-functionen zu verwenden.

Dies ist ein nettes kleines Papier zu diesem Thema. Seine empirische Schlussfolgerung ist, dass Treesort am besten ist, gefolgt von Quicksort und Mergesort. Sedimentsortierung, Blasensortierung, Sortierauswahl funktionieren sehr schlecht.

Eine vergleichende Studie von verknüpften LIST SORTING ALGORITHMEN von Ching-Kuang Shene

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

Eine Radix-Sortierung ist besonders für eine verkettete Liste geeignet, da es einfach ist, eine Tabelle mit Kopfzeigern zu erstellen, die jedem möglichen Wert einer Ziffer entsprechen.

Merge sort benötigt keinen O (1) -Zugang und ist O (n ln n). Keine bekannten Algorithmen zum Sortieren allgemeiner Daten sind besser als O (n ln n).

Die speziellen Datenalgorithmen wie Radix-Sortierung (begrenzt die Größe der Daten) oder Histogrammsortierung (Zählung diskreter Daten) können eine verkettete Liste mit einer niedrigeren Wachstumsfunktion sortieren, solange Sie eine andere Struktur mit O (1) -Zugriff als temporären Speicher verwenden .

Eine weitere class spezieller Daten ist eine Vergleichssorte einer nahezu sortierten Liste mit k Elementen außerhalb der Reihenfolge. Dies kann in O (kn) -Operationen sortiert werden.

Das Kopieren der Liste in ein Array und zurück wäre O (N), so dass jeder Sortieralgorithmus verwendet werden kann, wenn Platz kein Problem ist.

Bei einer verknüpften Liste, die uint_8 enthält, uint_8 dieser Code zum Beispiel in O (N) uint_8 eine Histogrammsortierung:

 #include  #include  #include  typedef struct _list list_t; struct _list { uint8_t value; list_t *next; }; list_t* sort_list ( list_t* list ) { list_t* heads[257] = {0}; list_t* tails[257] = {0}; // O(N) loop for ( list_t* it = list; it != 0; it = it -> next ) { list_t* next = it -> next; if ( heads[ it -> value ] == 0 ) { heads[ it -> value ] = it; } else { tails[ it -> value ] -> next = it; } tails[ it -> value ] = it; } list_t* result = 0; // constant time loop for ( size_t i = 255; i-- > 0; ) { if ( tails[i] ) { tails[i] -> next = result; result = heads[i]; } } return result; } list_t* make_list ( char* string ) { list_t head; for ( list_t* it = &head; *string; it = it -> next, ++string ) { it -> next = malloc ( sizeof ( list_t ) ); it -> next -> value = ( uint8_t ) * string; it -> next -> next = 0; } return head.next; } void free_list ( list_t* list ) { for ( list_t* it = list; it != 0; ) { list_t* next = it -> next; free ( it ); it = next; } } void print_list ( list_t* list ) { printf ( "[ " ); if ( list ) { printf ( "%c", list -> value ); for ( list_t* it = list -> next; it != 0; it = it -> next ) printf ( ", %c", it -> value ); } printf ( " ]\n" ); } int main ( int nargs, char** args ) { list_t* list = make_list ( nargs > 1 ? args[1] : "wibble" ); print_list ( list ); list_t* sorted = sort_list ( list ); print_list ( sorted ); free_list ( list ); } 

Keine direkte Antwort auf Ihre Frage, aber wenn Sie eine Skip-Liste verwenden , ist sie bereits sortiert und hat O (log N) Suchzeit.

Wie ich weiß, ist der beste Sortieralgorithmus O (n * log n), unabhängig vom Container – es wurde bewiesen, dass die Sortierung im weiten Sinne des Wortes (Mergesort / Quicksort usw.) nicht niedriger sein kann. Durch die Verwendung einer verketteten Liste erhalten Sie keine bessere Laufzeit.

Der einzige Algorithmus, der in O (n) läuft, ist ein “Hack” -Algorithmus, der auf dem Zählen von Werten beruht, anstatt tatsächlich zu sortieren.

Mergesort ist das Beste, was Sie hier tun können.

Hier ist eine Implementierung , die die Liste nur einmal durchläuft, Läufe sammelt und dann die Merges auf die gleiche Weise plant wie Mergesort.

Die Komplexität ist O (n log m), wobei n die Anzahl der Elemente und m die Anzahl der Läufe ist. Der beste Fall ist O (n) (wenn die Daten bereits sortiert sind) und der schlimmste Fall ist O (n log n) wie erwartet.

Es benötigt O (log m) temporären Speicher; Die Sortierung erfolgt direkt in den Listen.

(updated unten. commenter man macht einen guten Punkt, dass ich es hier beschreiben sollte)

Der core des Algorithmus ist:

  while list not empty accumulate a run from the start of the list merge the run with a stack of merges that simulate mergesort's recursion merge all remaining items on the stack 

Akkumulierende Läufe erfordern nicht viel Erklärung, aber es ist gut, die Gelegenheit zu nutzen, um sowohl aufsteigende als auch absteigende Läufe (umgekehrt) zu akkumulieren. Hier werden Elemente vorangestellt, die kleiner als der Kopf des Laufs sind, und Elemente angehängt, die größer oder gleich dem Ende des Laufs sind. (Beachten Sie, dass das Voranstellen striktes Less-Than verwenden sollte, um die Sortierstabilität zu erhalten.)

Am einfachsten fügen Sie den Code hier einfach ein:

  int i = 0; for ( ; i < stack.size(); ++i) { if (!stack[i]) break; run = merge(run, stack[i], comp); stack[i] = nullptr; } if (i < stack.size()) { stack[i] = run; } else { stack.push_back(run); } 

Überlegen Sie, die Liste zu sortieren (dagibecfjh) (Ignorieren von Läufen). Die Stapelzustände gehen wie folgt vor:

  [ ] [ (d) ] [ () (ad) ] [ (g), (ad) ] [ () () (adgi) ] [ (b) () (adgi) ] [ () (be) (adgi) ] [ (c) (be) (adgi ) ] [ () () () (abcdefgi) ] [ (j) () () (abcdefgi) ] [ () (hj) () (abcdefgi) ] 

Dann schließe schließlich alle diese Listen zusammen.

Beachten Sie, dass die Anzahl der Elemente (Läufe) im Stapel [i] entweder Null oder 2 ^ i ist und die Stapelgröße durch 1 + log2 (nruns) begrenzt ist. Jedes Element wird einmal pro Stapelebene zusammengeführt, daher O (n log m) Vergleiche. Es gibt eine vorübergehende Ähnlichkeit mit Timsort hier, obwohl Timsort seinen Stapel mit etwas wie eine Fibonacci-Sequenz, wo dies Potenzen von zwei verwendet.

Akkumulierende Läufe nutzen bereits sortierte Daten aus, so dass die Best Case-Komplexität für eine bereits sortierte Liste (ein Lauf) O (n) ist. Da wir sowohl aufsteigende als auch absteigende Läufe sammeln, haben Läufe immer mindestens die Länge 2. (Dies reduziert die maximale Stapeltiefe um mindestens eins, was die Kosten für das Finden der Läufe an erster Stelle ausmacht.) Worst Case Komplexität ist O (n log n), wie erwartet, für Daten, die stark randomisiert sind.

(Ähm ... Zweites Update.)

Oder sieh einfach Wikipedia auf Bottom-up-Mergesort .