Jaki jest najszybszy algorytm sortowania połączonej listy?

W zależności od wielu czynników, może być w rzeczywistości szybsze skopiowanie listy do tablicy, a następnie użycie Quicksort .

Powodem, dla którego może to być szybsze, jest to, że tablica ma znacznie lepsze wydajność pamięci podręcznej niż lista połączona. Jeśli węzły na liście są rozproszone w pamięci, może generować braki pamięci podręcznej w całym miejscu. Z drugiej strony, jeśli tablica jest duża, to i tak dostaniesz brak pamięci podręcznej.

Mergesort jest lepszy, więc może być lepszym wyborem, jeśli jest czego chcesz. Jest to również znacznie szybsze, jeśli wykonasz go bezpośrednio na połączonej liście.

Ponieważ oba algorytmy działają w O ( n * log n), podjęcie świadomej decyzji wiązałoby się z profilowaniem ich obu na maszynie, na której chcesz je uruchomić.

- - - Edycja

Postanowiłem przetestować moją hipotezę i napisałem program w języku C, który mierzył czas (używając clock()) do sortowania połączonej listy ints. Próbowałem z połączoną listą, gdzie każdy węzeł został przydzielony z malloc() i połączoną listą, gdzie węzły zostały ułożone liniowo w tablicy, więc wydajność pamięci podręcznej byłaby lepsza. Porównałem je z wbudowanym qsortem, który obejmował kopiowanie wszystkiego z pofragmentowanej listy do tablicy i ponowne kopiowanie wyniku. Każdy algorytm był uruchamiany na tych samych 10 zestawach danych, a wyniki były uśredniane.

Oto wyniki:

N = 1000:

Fragmented list with merge sort: 0.000000 seconds

Tablica z qsort: 0.000000 sekund

Pakowane lista z sortowaniem scalonym: 0.000000 sekund

N = 100000:

Fragmented list with merge sort: 0.039000 seconds

Tablica z qsort: 0.025000 sekund

Lista spakowana z sortowaniem scalonym: 0.009000 sekund

N = 1000000:

Fragmented list with merge sort: 1.162000 seconds

Tablica z qsort: 0.420000 sekund

Lista spakowana z sortowaniem scalonym: 0.112000 sekund

N = 100000000:

Fragmentaryczna lista with Merge sort: 364.797000 seconds

Tablica z qsort: 61.166000 sekund

Lista spakowana z sortowaniem scalonym: 16.525000 sekund

Wniosek:

Przynajmniej na moim komputerze, kopiowanie do tablicy jest warte poprawy wydajności pamięci podręcznej, ponieważ rzadko masz całkowicie spakowaną listę linkowanych w prawdziwym życiu. Należy zauważyć, że moja maszyna ma Phenom II 2.8 GHz, ale tylko 0.6 GHZ RAM, więc pamięć podręczna jest bardzo ważna.

To jest fajny artykuł na ten temat. Jego empiryczny wniosek jest taki, że Treesort jest najlepszy, a następnie Quicksort i Mergesort. Sortowanie osadów, sortowanie pęcherzyków, sortowanie selekcji działają bardzo źle.

A COMPARATIVE STUDY OF LINKED LIST SORTING ALGORITHMS by Ching-Kuang Shene

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

Sortowanie porównawcze (tj. oparte na porównywaniu elementów) nie może być szybsze niż n log n. Nie ma znaczenia, jaka jest podstawowa struktura danych. Zobacz Wikipedia .

Inne rodzaje sortowania, które korzystają z tego, że na liście jest wiele identycznych elementów (takich jak sortowanie liczenia), lub spodziewany rozkład elementów na liście, są szybsze, choć nie mogę myśleć o takich, które działają szczególnie dobrze na liście połączonej.

Jak stwierdzono wiele razy, dolna granica sortowania opartego na porównaniu dla ogólnych danych będzie wynosić O (N log n). Aby krótko podsumować te argumenty, są n! różne sposoby sortowania listy. Każdy rodzaj drzewa porównawczego, który ma n! (co jest w O (N^n)) możliwe sortowanie końcowe będzie wymagało co najmniej log(N!) jako jego wysokość: daje to o(log (n^n)) niższą granicę, czyli O (n log n).

Tak więc, dla ogólnych danych na linkowanej liście, najlepszy możliwy sortowanie, które będzie działać na każdym dane, które mogą porównać dwa obiekty, będą O (N log n). Jeśli jednak masz bardziej ograniczoną dziedzinę rzeczy do pracy, możesz poprawić czas potrzebny na pracę (przynajmniej proporcjonalnie do n). Na przykład, jeśli pracujesz z liczbami całkowitymi nie większymi niż jakaś wartość, możesz użyć liczenia sortowania lub Radix sortowania, ponieważ używają one konkretnych obiektów, które sortujesz, aby zmniejszyć złożoność proporcjonalnie do N. bądź ostrożny, te dodać kilka innych rzeczy do złożoności, która może być możesz nie brać pod uwagę (na przykład liczenie sortowania i sortowanie Radix dodają czynniki, które są oparte na wielkości sortowanych liczb, O (n+k), gdzie k jest wielkością największej liczby do liczenia sortowania, na przykład).

Ponadto, jeśli masz obiekty, które mają idealny hash (lub przynajmniej hash, który odwzorowuje wszystkie wartości w różny sposób), możesz spróbować użyć sortowania liczenia lub radix na ich funkcjach hash.

A sortowanie Radix jest szczególnie odpowiednie dla listy połączonej, ponieważ łatwo jest stworzyć tabelę wskaźników head odpowiadającą każdej możliwej wartości cyfry.

Sortowanie scalające nie wymaga dostępu O(1) i jest O (N ln n). Żadne znane algorytmy sortowania danych ogólnych nie są lepsze niż O (n ln n).

Specjalne algorytmy danych, takie jak sortowanie radix (ogranicza rozmiar danych ) lub sortowanie histogramu(liczy dane dyskretne), mogą sortować połączoną listę z funkcją niższego wzrostu, o ile używa się innej struktury z dostępem O (1) jako tymczasowego przechowywania.

Inną klasą danych specjalnych jest porównanie prawie posortowanej listy z k elementy nie w porządku. Można to sortować w operacjach O (kn).

Kopiowanie listy do tablicy i z powrotem byłoby O( N), więc każdy algorytm sortowania może być użyty, jeśli spacja nie jest problemem.

Na przykład, biorąc pod uwagę połączoną listę zawierającą uint_8, kod ten posortuje go w czasie O (N) używając sortowania histogramu:

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

Nie jest to bezpośrednia odpowiedź na twoje pytanie, ale jeśli używasz Pomiń listę, jest ona już posortowana i ma czas Wyszukiwania O (log N).

Jak wiem, najlepszym algorytmem sortowania jest O(n * log n), niezależnie od kontenera-udowodniono, że sortowanie w szerokim tego słowa znaczeniu (styl mergesort/quicksort itp.) nie może iść niżej. Korzystanie z połączonej listy nie da ci lepszego czasu uruchamiania.

Jedynym algorytmem, który działa w O (n), jest algorytm" hack", który polega na zliczaniu wartości, a nie na sortowaniu.

Oto implementacja , która przemierza listę tylko raz, zbierając biegi, a następnie rozkłada połączenia w taki sam sposób, jak robi to mergesort.

Złożoność to O (N log m), gdzie n to liczba pozycji, A m to liczba uruchomień. Najlepszym przypadkiem jest O(N) (jeśli dane są już posortowane), a najgorszym jest O (n log n) zgodnie z oczekiwaniami.

Wymaga o (log M) pamięci tymczasowej; sortowanie odbywa się na miejscu na listach.

(Aktualizacja poniżej. komentator ma rację że powinienem to opisać tutaj)

Istotą algorytmu jest:

    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

Biegi akumulacyjne nie wymagają zbyt wielu wyjaśnień, ale warto skorzystać z okazji, aby zgromadzić zarówno biegi rosnące, jak i zstępujące (odwrócone). Tutaj poprzedza elementy mniejsze od początku biegu i dodaje elementy większe lub równe końcowi biegu. (Należy pamiętać, że prepending powinien używać ścisłego less-than, aby zachować stabilność sortowania.)

Najłatwiej po prostu wkleić scalanie kod tutaj:

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

Rozważ sortowanie listy (d A g i b e c F j h) (ignorowanie uruchomień). Stany stosu przebiegają następująco:

    [ ]
    [ (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) ]

Następnie, w końcu, połącz wszystkie te listy.

Należy zauważyć, że liczba elementów (runów) na stosie[i] wynosi zero lub 2^i, a rozmiar stosu jest ograniczony przez 1 + log2 (nruns). Każdy element jest scalany raz na poziom stosu, stąd porównania O (N log m). Jest tu przemijające podobieństwo do Timsorta, chociaż Timsort utrzymuje swój stos używając czegoś w rodzaju Ciąg Fibonacciego, gdzie używa się potęg dwóch.

Nagromadzenie runów wykorzystuje dowolne już posortowane dane tak, że najlepszą złożonością jest O (n) dla już posortowanej listy (jeden bieg). Ponieważ gromadzimy zarówno biegi wstępujące, jak i zstępujące, biegi zawsze będą miały co najmniej 2 Długość. (Zmniejsza to maksymalną głębokość stosu o co najmniej jedną, płacąc za koszty znalezienia runów w pierwszej kolejności.) Najgorszy przypadek złożoności jest O (n log n), zgodnie z oczekiwaniami, dla danych, które są wysoce randomizowane.

(Um... Druga aktualizacja.)

Lub po prostu zobacz Wikipedię na oddolne połączenia .

Możesz skopiować go do tablicy, a następnie posortować.

• Kopiowanie do tablicy O (n),

• Sortowanie O (nlgn) (jeśli używasz szybkiego algorytmu jak merge sort ),

• Kopiowanie z powrotem do linked list O (n) jeśli to konieczne,

Więc będzie O (nlgn).

Zauważ, że jeśli nie znasz liczby elementów w linkowanej liście, nie będziesz znać rozmiaru tablicy. Jeśli kodujesz w Javie, możesz użyć na przykład Arraylist.

Mergesort to najlepsze, co możesz tutaj zrobić.

Pytanie brzmi LeetCode #148 i istnieje wiele rozwiązań oferowanych we wszystkich głównych językach. Mój jest następujący, ale zastanawiam się nad złożonością czasową. Aby znaleźć środkowy element, za każdym razem przemierzamy pełną listę. Pierwszy raz n elementy są iterowane, drugi raz 2 * n/2 elementy są iterowane, tak dalej i tak dalej. Wydaje się, że nadszedł O(n^2) czas.

def sort(linked_list: LinkedList[int]) -> LinkedList[int]:
    # Return n // 2 element
    def middle(head: LinkedList[int]) -> LinkedList[int]:
        if not head or not head.next:
            return head
        slow = head
        fast = head.next

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        return slow

    def merge(head1: LinkedList[int], head2: LinkedList[int]) -> LinkedList[int]:
        p1 = head1
        p2 = head2
        prev = head = None

        while p1 and p2:
            smaller = p1 if p1.val < p2.val else p2
            if not head:
                head = smaller
            if prev:
                prev.next = smaller
            prev = smaller

            if smaller == p1:
                p1 = p1.next
            else:
                p2 = p2.next

        if prev:
            prev.next = p1 or p2
        else:
            head = p1 or p2

        return head

    def merge_sort(head: LinkedList[int]) -> LinkedList[int]:
        if head and head.next:
            mid = middle(head)
            mid_next = mid.next
            # Makes it easier to stop
            mid.next = None

            return merge(merge_sort(head), merge_sort(mid_next))
        else:
            return head

    return merge_sort(linked_list)