Jaki jest najszybszy algorytm sortowania połączonej listy?

Ciekaw jestem, czy O (n log n) jest najlepsze, co może zrobić lista połączona.

Rozsądnie jest oczekiwać, że nie możesz zrobić nic lepszego niż O (N log N) w czasie wykonywania .

Jednak interesującą częścią jest zbadanie, czy można go posortować na miejscu , stabilnie , jego najgorsze zachowanie i tak dalej.

Simon Tatham, znany z Putty, wyjaśnia, jak posortować listę połączoną za pomocą sortowania przez scalanie . Kończy następującymi komentarzami:

Jak każdy szanujący się algorytm sortowania, ma on czas działania O (N log N). Ponieważ jest to Mergesort, czas wykonywania w najgorszym przypadku nadal wynosi O (N log N); nie ma przypadków patologicznych.

Wymagania dotyczące pamięci pomocniczej są małe i stałe (tj. Kilka zmiennych w ramach procedury sortowania). Dzięki z natury innym zachowaniom połączonych list z tablic, ta implementacja Mergesort pozwala uniknąć kosztu pamięci dyskowej O (N), który zwykle wiąże się z algorytmem.

Istnieje również przykładowa implementacja w języku C, która działa zarówno dla list połączonych pojedynczo, jak i podwójnie.

Jak wspomina @ Jørgen Fogh poniżej, notacja duże-O może ukrywać pewne stałe czynniki, które mogą powodować lepsze działanie jednego algorytmu z powodu lokalizacji pamięci, z powodu małej liczby elementów itp.

W zależności od wielu czynników, w rzeczywistości może być 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 lepszą wydajność pamięci podręcznej niż lista połączona. Jeśli węzły na liście są rozproszone w pamięci, możesz generować błędy pamięci podręcznej w każdym miejscu. Z drugiej strony, jeśli tablica jest duża, i tak otrzymasz błędy pamięci podręcznej.

Mergesort działa równolegle lepiej, więc może to być lepszy wybór, jeśli tego chcesz. Jest to również znacznie szybsze, jeśli wykonujesz to bezpośrednio na połączonej liście.

Ponieważ oba algorytmy działają w O (n * log n), podjęcie świadomej decyzji wymagałoby profilowania ich obu na komputerze, na którym chciałbyś je uruchomić.

--- EDYTOWAĆ

Postanowiłem sprawdzić moją hipotezę i napisałem program w języku C, który mierzył czas (za pomocą clock()) sortowania połączonej listy int. Próbowałem z połączoną listą, do której przydzielono każdy węzeł, malloc()i połączoną listą, w której 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 qsort, który obejmował skopiowanie wszystkiego, od pofragmentowanej listy do tablicy i ponowne skopiowanie wyniku. Każdy algorytm został uruchomiony na tych samych 10 zestawach danych, a wyniki uśredniono.

Oto wyniki:

N = 1000:

Lista pofragmentowana z sortowaniem przez scalanie: 0,000000 sekund

Tablica z qsort: 0,000000 sekund

Lista spakowana z sortowaniem przez scalanie: 0,000000 sekund

N = 100000:

Lista pofragmentowana z sortowaniem przez scalanie: 0,039000 sekund

Tablica z qsort: 0,025000 sekund

Lista spakowana z sortowaniem przez scalanie: 0,009000 sekund

N = 1000000:

Lista pofragmentowana z sortowaniem przez scalanie: 1,162000 sekund

Tablica z qsort: 0,420000 sekund

Lista spakowana z sortowaniem przez scalanie: 0,112000 sekund

N = 100000000:

Lista pofragmentowana z sortowaniem przez scalanie: 364,797000 sekund

Tablica z qsort: 61,166000 sekund

Lista spakowana z sortowaniem przez scalanie: 16,525000 sekund

Wniosek:

Przynajmniej na moim komputerze, kopiowanie do tablicy jest tego warte, aby poprawić wydajność pamięci podręcznej, ponieważ rzadko masz całkowicie spakowaną listę połączoną w prawdziwym życiu. Należy zauważyć, że moja maszyna ma 2,8 GHz Phenom II, ale tylko 0,6 GHz RAM, więc pamięć podręczna jest bardzo ważna.

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 Wikipedię .

Inne rodzaje, które wykorzystują to, że na liście jest dużo identycznych elementów (takie jak sortowanie zliczające) lub pewne oczekiwane rozmieszczenie elementów na liście, są szybsze, chociaż nie przychodzi mi do głowy żaden, który działałby szczególnie dobrze na połączonej liście.

To jest fajny mały artykuł na ten temat. Jego empiryczny wniosek jest taki, że najlepszy jest Treeort, a następnie Quicksort i Mergesort. Sortowanie osadu, sortowanie bąbelkowe, sortowanie przez selekcję działają bardzo źle.

BADANIE PORÓWNAWCZE ALGORYTMÓW SORTOWANIA LIST POWIĄZANYCH przez Ching-Kuang Shene

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

Jak wielokrotnie stwierdzono, dolną granicą sortowania opartego na porównaniu dla danych ogólnych będzie O (n log n). Aby krótko podsumować te argumenty, jest n! różne sposoby sortowania listy. Dowolne drzewo porównawcze, które ma n! (co jest w O (n ^ n)) możliwe ostateczne sortowanie będzie wymagało co najmniej log (n!) jako swojej wysokości: daje to O (log (n ^ n)) dolną granicę, która wynosi O (n log n).

Tak więc dla danych ogólnych na połączonej liście najlepszym możliwym sortowaniem, które będzie działać na dowolnych danych, które mogą porównywać dwa obiekty, będzie O (n log n). Jeśli jednak masz bardziej ograniczoną domenę rzeczy do pracy, możesz skrócić czas potrzebny (przynajmniej proporcjonalnie do n). Na przykład, jeśli pracujesz z liczbami całkowitymi nie większymi niż pewna wartość, możesz użyć Sortowanie zliczania lub Sortowanie według radix , ponieważ używają one określonych obiektów, które sortujesz, aby zmniejszyć złożoność proporcjonalnie do n. Uważaj jednak, te dodają kilka innych rzeczy do złożoności, których możesz nie brać pod uwagę (na przykład sortowanie zliczania i sortowanie radiksu dodają czynniki, które są oparte na rozmiarze sortowanych liczb, O (n + k ), gdzie k to na przykład wielkość największej liczby dla sortowania zliczania).

Ponadto, jeśli zdarzy ci się mieć obiekty, które mają doskonały hash (lub przynajmniej hash, który odwzorowuje wszystkie wartości inaczej), możesz spróbować użyć liczenia lub sortowania radix w ich funkcjach skrótu.

Sortowanie pozycyjne jest szczególnie nadaje się do połączonej listy, ponieważ jest to łatwe do wykonania tablicę wskaźników głowy odpowiadających każdej możliwej wartości cyfry.

Sortowanie przez scalanie nie wymaga dostępu O (1) i ma wartość O (n ln n). Żaden znany algorytm sortowania danych ogólnych nie jest lepszy niż O (n ln n).

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

Inną klasą danych specjalnych jest rodzaj porównania prawie posortowanej listy z k elementami nieuporządkowanymi. Można to posortować w operacjach O (kn).

Kopiowanie listy do tablicy iz powrotem byłoby O (N), więc można użyć dowolnego algorytmu sortowania, jeśli przestrzeń nie jest problemem.

Na przykład, biorąc pod uwagę połączoną listę zawierającą uint_8, ten kod posortuje ją w czasie O (N) przy użyciu 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 listy pominiętych , 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 - zostało udowodnione, że sortowanie w szerokim znaczeniu tego słowa (styl łączenie / sortowanie itp.) Nie może być niższe. Korzystanie z listy połączonej nie zapewni lepszego czasu działania.

Jedynym algorytmem działającym w O (n) jest algorytm „hakerski”, który polega na liczeniu wartości, a nie na ich sortowaniu.

Oto implementacja, która przeszukuje listę tylko raz, zbiera przebiegi, a następnie planuje scalenia w taki sam sposób, jak to robi scalesort.

Złożoność wynosi O (n log m), gdzie n to liczba elementów, a m to liczba serii. Najlepszym przypadkiem jest O (n) (jeśli dane są już posortowane), a najgorszym przypadkiem jest O (n log n), zgodnie z oczekiwaniami.

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

(zaktualizowane poniżej. Komentator dobrze zauważa, że ​​powinienem to opisać tutaj)

Istota algorytmu to:

    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

Kumulacja biegów nie wymaga wielu wyjaśnień, ale dobrze jest skorzystać z okazji, aby skumulować zarówno biegi wznoszące, jak i opadające (odwrócone). W tym przypadku dołącza elementy mniejsze niż początek rozdziału i dołącza elementy większe lub równe na końcu rozdziału. (Należy pamiętać, że poprzedzanie powinno używać ściśle mniejszego niż, aby zachować stabilność sortowania).

Najłatwiej jest po prostu wkleić tutaj kod scalający:

    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 (dagibecfjh) (ignorowanie przebiegów). Stany stosu są następujące:

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

Na koniec połącz wszystkie te listy.

Zauważ, że liczba elementów (przebiegów) na stosie [i] wynosi zero lub 2 ^ i, a rozmiar stosu jest ograniczony przez 1 + log2 (nruns). Każdy element jest łączony raz na poziom stosu, stąd porównania O (n log · m). Występuje tutaj przemijające podobieństwo do Timsort, chociaż Timsort utrzymuje swój stos za pomocą czegoś w rodzaju sekwencji Fibonacciego, w której używa się potęgi dwóch.

Kumulacja przebiegów wykorzystuje wszelkie już posortowane dane, tak że najlepsza złożoność przypadku wynosi O (n) dla już posortowanej listy (jeden przebieg). Ponieważ gromadzimy zarówno biegi wznoszące, jak i opadające, przebiegi zawsze będą miały co najmniej długość 2. (Zmniejsza to maksymalną głębokość stosu o co najmniej jeden, płacąc przede wszystkim za koszt znalezienia przebiegów). Najgorszy przypadek to złożoność O (n log n), zgodnie z oczekiwaniami, dla danych, które są wysoce randomizowane.

(Um ... Druga aktualizacja.)

Lub po prostu zobacz wikipedię o oddolnym sortowaniu .

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

• Kopiowanie do tablicy O (n),

• sortowanie O (nlgn) (jeśli używasz szybkiego algorytmu, takiego jak sortowanie przez scalanie),

• kopiowanie z powrotem do połączonej listy O (n), jeśli to konieczne,

więc to będzie O (nlgn).

zwróć uwagę, że jeśli nie znasz liczby elementów w połączonej liście, nie będziesz znać rozmiaru tablicy. Jeśli piszesz w Javie, możesz na przykład użyć 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 przechodzimy przez całą listę. nElementy za pierwszym razem są iterowane, 2 * n/2elementy za drugim razem są iterowane, tak dalej i tak dalej. Wydaje się, że O(n^2)nadszedł 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)