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 kann.

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

Der interessante Teil ist jedoch zu untersuchen, ob Sie es an Ort und Stelle stabil sortieren können, wie es sich im schlimmsten Fall verhält und so weiter.

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

Wie jeder selbst respektierende Sortieralgorithmus hat dieser die Laufzeit O (N log N). Da dies Mergesort ist, beträgt die Laufzeit im ungünstigsten Fall immer noch O (N log N). Es gibt keine pathologischen Fälle.

Der zusätzliche Speicherbedarf ist gering und konstant (dh einige Variablen innerhalb der Sortierroutine). Dank des inhärent unterschiedlichen Verhaltens verknüpfter Listen von Arrays werden durch diese Mergesort-Implementierung die normalerweise mit dem Algorithmus verbundenen O (N) -Hilfsspeicherkosten vermieden.

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

Wie @ Jørgen Fogh weiter unten erwähnt, kann die Big-O-Notation einige konstante Faktoren verbergen, die dazu führen können, dass ein Algorithmus aufgrund der Speicherlokalität, aufgrund einer geringen Anzahl von Elementen usw. eine bessere Leistung erbringt.

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

Der Grund dafür ist möglicherweise, dass ein Array eine viel bessere Cache-Leistung aufweist als eine verknüpfte Liste. Wenn die Knoten in der Liste im Speicher verteilt sind, können Sie überall Cache-Fehler generieren. Andererseits, wenn das Array groß ist, werden Sie trotzdem Cache-Fehler bekommen.

Mergesort parallelisiert besser, daher ist es möglicherweise eine bessere Wahl, wenn Sie dies wünschen. Es ist auch viel schneller, wenn Sie es direkt in der verknüpften Liste ausführen.

Da beide Algorithmen in O (n * log n) ausgeführt werden, müssen Sie für eine fundierte Entscheidung beide Profile auf dem Computer erstellen, auf dem Sie sie ausführen möchten.

--- BEARBEITEN

Ich beschloss, meine Hypothese zu testen und schrieb ein C-Programm, das die Zeit (unter Verwendung clock()) zum Sortieren einer verknüpften Liste von Ints maß. Ich habe es mit einer verknüpften Liste versucht, in der jedem Knoten zugewiesen wurde, malloc()und einer verknüpften Liste, in der die Knoten linear in einem Array angeordnet waren, damit die Cache-Leistung besser ist. Ich habe diese mit dem integrierten qsort verglichen, bei dem alles von einer fragmentierten Liste in ein Array kopiert und das Ergebnis erneut kopiert wurde. Jeder Algorithmus wurde mit denselben 10 Datensätzen ausgeführt und die Ergebnisse wurden gemittelt.

Dies sind die Ergebnisse:

N = 1000:

Fragmentierte Liste mit Zusammenführungssortierung: 0,000000 Sekunden

Array mit qsort: 0,000000 Sekunden

Gepackte Liste mit Zusammenführungssortierung: 0,000000 Sekunden

N = 100000:

Fragmentierte Liste mit Zusammenführungssortierung: 0,039000 Sekunden

Array mit qsort: 0,025000 Sekunden

Gepackte Liste mit Zusammenführungssortierung: 0,009000 Sekunden

N = 1000000:

Fragmentierte Liste mit Zusammenführungssortierung: 1.162000 Sekunden

Array mit qsort: 0,420000 Sekunden

Gepackte Liste mit Zusammenführungssortierung: 0,112000 Sekunden

N = 100000000:

Fragmentierte Liste mit Zusammenführungssortierung: 364.797000 Sekunden

Array mit qsort: 61.166000 Sekunden

Gepackte Liste mit Zusammenführungssortierung: 16.525000 Sekunden

Fazit:

Zumindest auf meinem Computer lohnt sich das Kopieren in ein Array, um die Cache-Leistung zu verbessern, da Sie im wirklichen Leben selten eine vollständig gepackte verknüpfte Liste haben. Es sollte beachtet werden, dass mein Computer ein 2,8 GHz Phenom II hat, aber nur 0,6 GHz RAM, daher ist der Cache sehr wichtig.

Vergleichssorten (dh solche, die auf dem Vergleichen von Elementen basieren) können möglicherweise nicht schneller sein als n log n. Es spielt keine Rolle, wie die zugrunde liegende Datenstruktur aussieht. Siehe Wikipedia .

Andere Arten von Sortierungen, die davon profitieren, dass viele identische Elemente in der Liste vorhanden sind (z. B. die Zählsortierung) oder eine erwartete Verteilung von Elementen in der Liste, sind schneller, obwohl ich mir keine vorstellen kann, die besonders gut funktionieren auf einer verknüpften Liste.

Dies ist ein schönes kleines Papier zu diesem Thema. Seine empirische Schlussfolgerung ist, dass Treesort am besten ist, gefolgt von Quicksort und Mergesort. Sedimentsortierung, Blasensortierung, Auswahlsortierung sind sehr schlecht.

Eine vergleichende Studie zu verknüpften Sortieralgorithmen von Ching-Kuang Shene

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

Wie oft erwähnt, wird die Untergrenze für die vergleichsbasierte Sortierung für allgemeine Daten O (n log n) sein. Um diese Argumente kurz wieder zusammenzufassen, gibt es n! Verschiedene Arten, wie eine Liste sortiert werden kann. Jede Art von Vergleichsbaum, der n hat! (was in O (n ^ n) ist) Mögliche endgültige Sortierungen benötigen mindestens log (n!) als Höhe: Dies gibt Ihnen eine Untergrenze von O (log (n ^ n)), die O (n) ist log n).

Für allgemeine Daten in einer verknüpften Liste ist die bestmögliche Sortierung, die für alle Daten funktioniert, die zwei Objekte vergleichen können, O (n log n). Wenn Sie jedoch einen begrenzten Arbeitsbereich haben, in dem Sie arbeiten können, können Sie die dafür benötigte Zeit verbessern (zumindest proportional zu n). Wenn Sie beispielsweise mit Ganzzahlen arbeiten, die nicht größer als ein Wert sind, können Sie Counting Sort oder Radix Sort verwenden , da diese die spezifischen Objekte verwenden, die Sie sortieren, um die Komplexität proportional zu n zu verringern. Seien Sie jedoch vorsichtig, diese fügen der Komplexität, die Sie möglicherweise nicht berücksichtigen, einige andere Dinge hinzu (z. B. Zählsortierung und Radix-Sortierung fügen Faktoren hinzu, die auf der Größe der zu sortierenden Zahlen basieren, O (n + k) ) wobei k zum Beispiel die Größe der größten Zahl für Counting Sort ist).

Wenn Sie Objekte haben, die einen perfekten Hash haben (oder zumindest einen Hash, der alle Werte unterschiedlich abbildet), können Sie versuchen, ihre Hash-Funktionen mit einer Zähl- oder Radix-Sortierung zu versehen.

Eine Radix-Sortierung eignet sich besonders für eine verknüpfte Liste, da es einfach ist, eine Tabelle mit Kopfzeigern zu erstellen, die jedem möglichen Wert einer Ziffer entspricht.

Die Zusammenführungssortierung erfordert keinen O (1) -Zugriff 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 Datengröße) oder Histogramm-Sortierung (zählt diskrete Daten) können eine verknüpfte Liste mit einer geringeren Wachstumsfunktion sortieren, sofern Sie eine andere Struktur mit O (1) -Zugriff als temporären Speicher verwenden .

Eine andere Klasse von Spezialdaten ist eine Vergleichssorte einer fast sortierten Liste mit k Elementen, die nicht in der richtigen Reihenfolge sind. Dies kann in O (kn) -Operationen sortiert werden.

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

Wenn eine verknüpfte Liste enthält uint_8, sortiert dieser Code sie beispielsweise in O (N) -Zeit mithilfe einer Histogrammsortierung:

#include <stdio.h>
#include <stdint.h>
#include <malloc.h>

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 Überspringliste verwenden , ist diese bereits sortiert und hat eine Suchzeit von O (log N).

Wie ich weiß, ist der beste Sortieralgorithmus O (n * log n), unabhängig vom Container - es wurde bewiesen, dass das Sortieren im weiteren Sinne des Wortes (Mergesort / Quicksort usw.) nicht niedriger sein kann. Wenn Sie eine verknüpfte Liste verwenden, erhalten Sie keine bessere Laufzeit.

Der einzige Algorithmus, der in O (n) ausgeführt wird, ist ein "Hack" -Algorithmus, der auf dem Zählen von Werten und nicht auf dem tatsächlichen Sortieren beruht.

Hier ist eine Implementierung , die die Liste nur einmal durchläuft, Läufe sammelt und dann die Zusammenführungen auf die gleiche Weise plant wie die Zusammenführung.

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 schlechteste Fall ist erwartungsgemäß O (n log n).

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

(aktualisiert unten. Kommentator eins macht einen guten Punkt, dass ich es hier beschreiben sollte)

Der Kern 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

Das Sammeln von Läufen erfordert 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 beim Voranstellen strikt weniger als verwendet werden sollte, um die Sortierstabilität zu gewährleisten.)

Es ist am einfachsten, den Zusammenführungscode hier einzufügen:

    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);
    }

Sortieren Sie die Liste (dagibecfjh) (ignorieren Sie Läufe). Die Stapelzustände gehen wie folgt vor:

    [ ]
    [ (d) ]
    [ () (a d) ]
    [ (g), (a d) ]
    [ () () (a d g i) ]
    [ (b) () (a d g i) ]
    [ () (b e) (a d g i) ]
    [ (c) (b e) (a d g i ) ]
    [ () () () (a b c d e f g i) ]
    [ (j) () () (a b c d e f g i) ]
    [ () (h j) () (a b c d e f g i) ]

Führen Sie dann schließlich alle diese Listen zusammen.

Beachten Sie, dass die Anzahl der Elemente (Läufe) am 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 hier eine vorübergehende Ähnlichkeit mit Timsort, obwohl Timsort seinen Stapel mit einer Fibonacci-Sequenz beibehält, bei der Zweierpotenzen verwendet werden.

Das Akkumulieren von Läufen nutzt bereits sortierte Daten, sodass die Best-Case-Komplexität für eine bereits sortierte Liste (ein Lauf) O (n) beträgt. Da wir sowohl aufsteigende als auch absteigende Läufe akkumulieren, haben Läufe immer mindestens die Länge 2. (Dies reduziert die maximale Stapeltiefe um mindestens eins und zahlt die Kosten für das Auffinden der Läufe.) Die Komplexität im schlimmsten Fall ist O (n log n), wie erwartet, für Daten, die stark randomisiert sind.

(Ähm ... Zweites Update.)

Oder sehen Sie einfach Wikipedia auf Bottom-Up-Mergesort .

Sie können es in ein Array kopieren und dann sortieren.

• Kopieren in Array O (n),

• Sortieren von O (nlgn) (wenn Sie einen schnellen Algorithmus wie Merge Sort verwenden),

• ggf. in die verknüpfte Liste O (n) zurückkopieren,

also wird es O sein (nlgn).

Beachten Sie, dass Sie die Größe des Arrays nicht kennen, wenn Sie die Anzahl der Elemente in der verknüpften Liste nicht kennen. Wenn Sie in Java codieren, können Sie beispielsweise eine Arrayliste verwenden.

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