wake-up-neo.net

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.

85
Dirk

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

Der interessante Teil besteht jedoch darin, zu untersuchen, ob Sie in-place , stabil , das Worst-Case-Verhalten usw. sortieren können.

Simon Tatham, von PuTTY berühmt, erklärt, wie man Sortieren einer verknüpften Liste mit Merge-Sortierung . Er schließt mit den folgenden Anmerkungen:

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

Der Hilfsspeicherbedarf ist klein und konstant (d. H. Einige Variablen innerhalb der Sortierroutine). Aufgrund des inhärenten Verhaltens verknüpfter Listen gegenüber Arrays werden bei dieser Mergesort-Implementierung die mit dem Algorithmus normalerweise verbundenen zusätzlichen Speicherkosten O(N) vermieden.

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

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

86
csl

Abhängig von einer Reihe von Faktoren ist es möglicherweise schneller, die Liste in ein Array zu kopieren und dann einen Quicksort zu verwenden.

Der Grund dafür kann sein, dass ein Array schneller eine bessere Cache-Leistung als eine verknüpfte Liste hat. Wenn die Knoten in der Liste im Arbeitsspeicher verteilt sind, generieren Sie möglicherweise überall Cache-Fehler. Wenn das Array jedoch groß ist, werden Sie trotzdem Cache-Fehler erhalten.

Mergesort parallelisiert besser, daher ist es möglicherweise eine bessere Wahl, wenn Sie das wollen. 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, müssen Sie eine fundierte Entscheidung treffen, um sie auf dem Computer zu profilieren, auf dem Sie sie ausführen möchten.

--- BEARBEITEN

Ich beschloss, meine Hypothese zu testen und schrieb ein C-Programm, in dem die Zeit (mit clock()) gemessen wurde, die zum Sortieren einer verknüpften Liste von Ints benötigt wurde. Ich habe es mit einer verknüpften Liste versucht, bei der jeder Knoten mit malloc() zugewiesen wurde, und mit einer verknüpften Liste, bei der die Knoten linear in einem Array angeordnet waren, sodass die Cache-Leistung besser wäre. Ich verglich diese mit dem eingebauten qsort, bei dem alles von einer fragmentierten Liste in ein Array kopiert und das Ergebnis erneut zurückkopiert wurde. Jeder Algorithmus wurde mit den gleichen 10 Datensätzen ausgeführt und die Ergebnisse wurden gemittelt.

Das sind die Ergebnisse:

N = 1000:

Fragmentierte Liste mit Zusammenführungssortierung: 0,000000 Sekunden

Array mit qsort: 0,000000 Sekunden

Packliste mit Zusammenführungssortierung: 0,000000 Sekunden

N = 100000:

Fragmentierte Liste mit Zusammenführungssortierung: 0,039000 Sekunden

Array mit qsort: 0,025000 Sekunden

Packliste 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 Sortierreihenfolge: 0,112000 Sekunden

N = 100000000:

Fragmentierte Liste mit Zusammenführungssortierung: 364,797000 Sekunden

Array mit qsort: 61,166000 Sekunden

Packliste 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 realen Leben selten eine vollständig gepackte verknüpfte Liste haben. Es ist zu beachten, dass mein Rechner einen 2,8 GHz Phenom II, aber nur 0,6 GHz RAM besitzt, daher ist der Cache sehr wichtig.

66
Jørgen Fogh

Vergleichssorten (d. H. Sorten, die auf dem Vergleich von Elementen basieren) können möglicherweise nicht schneller als n log n sein. Es ist egal, was die zugrunde liegende Datenstruktur ist. Siehe Wikipedia .

Andere Sortierungen, bei denen es viele identische Elemente in der Liste gibt (wie z. B. die Zählungsart) oder eine erwartete Verteilung der Elemente in der Liste, sind schneller, obwohl ich mir nichts besonders gut vorstellen kann in einer verknüpften Liste.

6
Artelius

Wie schon oft erwähnt, wird die untere Grenze der sortenbasierten Sortierung für allgemeine Daten O (n log n) sein. Um diese Argumente kurz zusammenzufassen, gibt es n! Auf verschiedene Arten kann eine Liste sortiert werden. Jede Art von Vergleichsbaum mit n! (was in O (n ^ n)) möglich ist, benötigen Sie mindestens log (n!) als Höhe: Dies gibt Ihnen eine untere Grenze von O (log (n ^ n)), die O (n) ist log n). 

Für allgemeine Daten in einer verknüpften Liste ist also die beste Sortierung, die für alle Daten geeignet ist, die zwei Objekte vergleichen können, O (n log n). Wenn Sie jedoch ein begrenzteres Arbeitsgebiet haben, können Sie die benötigte Zeit verbessern (zumindest proportional zu n). Wenn Sie beispielsweise mit ganzen Zahlen arbeiten, die größer als ein bestimmter Wert sind, können Sie Counting Sort oder Radix Sort verwenden, da diese die spezifischen Objekte verwenden, die Sie sortieren, um die Komplexität mit n zu reduzieren . Seien Sie jedoch vorsichtig, da dies der Komplexität, die Sie möglicherweise nicht berücksichtigen, einige andere Dinge hinzufügt (z. B. Sortierung nach Sortieren und Radix-Sortierung). Beide Faktoren fügen Faktoren hinzu, die auf der Größe der zu sortierenden Zahlen basieren (O (n + k) ) wobei k die Größe der größten Zahl für "Counting Sort" ist).

Wenn Sie zufällig Objekte haben, die einen perfekten Hash haben (oder zumindest einen Hash, der alle Werte unterschiedlich abbildet), können Sie versuchen, eine Zähl- oder Radix-Sortierung für ihre Hash-Funktionen zu verwenden.

5
DivineWolfwood

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

EINE VERGLEICHENDE STUDIE ÜBER DIE VERBUNDENE LISTE, DIE ALGORITHME SORTIERT

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

5
Neal Richter

A Radix Sort eignet sich besonders für eine verknüpfte Liste, da es einfach ist, eine Tabelle von Kopfzeigern zu erstellen, die jedem möglichen Wert einer Ziffer entsprechen.

3
Mark Ransom

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

Eine andere Klasse spezieller Daten ist eine Vergleichsart einer fast sortierten Liste mit k Elementen, die nicht in der 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.

Bei einer verknüpften Liste mit uint_8 wird dieser Code beispielsweise nach O(N) - Zeit sortiert, wobei eine Histogramm-Sortierung verwendet wird:

#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 );
}
2
Pete Kirkham

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

1
Mitch Wheat

Wie ich weiß, ist der beste Sortieralgorithmus O (n * log n), egal in welchem ​​Container - es ist erwiesen, dass das Sortieren im weitesten Sinne des Wortes (Mergesort/Quicksort-Stil) nicht nachlassen kann. Durch die Verwendung einer verknüpften Liste erhalten Sie keine bessere Laufzeit. 

Der einzige Algorithmus, der in O(n) läuft, ist ein "Hack" -Algorithmus, der sich auf das Zählen von Werten stützt, anstatt tatsächlich zu sortieren.

1
laura

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

Die Komplexität ist O (n log m), wobei n die Anzahl der Elemente und m die Anzahl der Läufe ist. Im besten Fall ist O(n) (wenn die Daten bereits sortiert sind) und im ungünstigsten Fall ist O (n log n) wie erwartet.

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

(aktualisiert unten. Kommentator 1 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 keine großen Erklärungen, aber es ist gut, die Gelegenheit zu nutzen, um sowohl aufsteigende als auch absteigende Läufe zu akkumulieren (umgekehrt). Hier werden Elemente hinzugefügt, die kleiner als der Kopf des Laufs sind, und Elemente, die größer oder gleich dem Ende des Laufs sind, angefügt. (Beachten Sie, dass das Voranstellen strengere als verwenden sollte, um die Sortenstabilität zu erhalten.)

Es ist am einfachsten, den zusammenführenden Code 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);
    }

Ziehen Sie in Betracht, die Liste zu sortieren (d a g i b e c f j h) (Läufe ignorieren). Die Stackzustä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) ]

Dann schließlich alle diese Listen zusammenführen.

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 hier eine vorübergehende Ähnlichkeit mit Timsort, obwohl Timsort seinen Stack verwendet und so etwas wie eine Fibonacci-Sequenz verwendet, bei der Potenzen von zwei verwendet werden.

Durch das Sammeln von Läufen werden alle bereits sortierten Daten ausgenutzt, so dass die beste Fallkomplexität O(n) für eine bereits sortierte Liste (ein Lauf) ist. 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 eine, wodurch die Kosten für das Auffinden der Läufe an erster Stelle bezahlt werden.) Die Komplexität im ungünstigsten Fall ist O (n log n) wie erwartet für Daten, die hoch randomisiert sind.

(Um ... Zweites Update.)

Oder sehen Sie einfach Wikipedia auf bottom-up mergesort .

1
Stan Switzer

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

0
ypnos

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

  • Kopieren in Array O (n),

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

  • ggf. Rückkopplung in die verknüpfte Liste O(n),

also wird es o (nlgn) sein.

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 programmieren, können Sie beispielsweise eine Arrayliste verwenden. 

0
Shirin