Programisto, nie zapominaj o algorytmach! #5

Jednym z kluczowych problemów algorytmicznych jest sortowanie. Za każdym razem, gdy oglądamy newsy na naszym ulubionym portalu są one posortowane od najnowszego do najstarszego. W dzisiejszym artykule przyjrzymy się właśnie algorytmom sortowania.

Wprowadźmy najpierw dwa bardzo istotne terminy:

Sortowanie będziemy nazywać działającym w miejscu, jeśli algorytm wymaga stałej ilości pamięci dodatkowej (niezależnej od wielkości sortowanych danych).

Sortowanie będziemy nazywać stabilnym, jeżeli dla elementów o takiej samej wartości, zostanie zachowana ich kolejność po sortowaniu.

Przed Po
Sortowanie stabilne [5, 4, 4, 9] [4, 4, 5, 9]
Sortowanie niestabilne [5, 4, 4, 9] [4, 4, 5, 9]

Zwróćmy uwagę, że w przypadku sortowania niestabilnego zamieniona została kolejność dwóch czwórek (dla algorytmu są one nieodróżnialne, my im nadaliśmy dodatkową własność koloru).

Definicja

Formalnie problem sortowania wygląda następująco:
Dane wejściowe: skończony ciąg n liczb (an)=〈a0,a1,a2,…,an                                               Wynik: permutacja P ciągu (an), taka, że P((an))=(ãn), gdzie ã0≤ã1≤ã2≤⋯≤ãn

Innymi słowy oczekujemy, że sortowanie przestawi nam elementy ciągu wejściowego tak, że każdy następny będzie większy (lub równy) od poprzedniego.

Uwaga – rozważać będziemy algorytmy sortowania najbardziej ogólnego przeznaczenia, czyli takie, które nakładają jak najmniejsze warunki na dane, na których operują.

Sortowanie bąbelkowe

To chyba najprostszy z algorytmów sortowania. Zobaczmy go na przykładzie zapisanym w pseudokodzie:

 

procedure bubbleSort( A : list of sortable items )
   n = length(A)
   repeat 
     swapped = false
     for i = 1 to n-1 inclusive do
       /* if this pair is out of order */
       if A[i-1] > A[i] then
         /* swap them and remember something changed */
         swap( A[i-1], A[i] )
         swapped = true
       end if
     end for
   until not swapped
end procedure

Średnia złożoność tego algorytmu wynosi – jest to cena jaką ponosimy za prostą budowę. Zaletą jest natomiast fakt, że przy posortowanej tablicy złożoność wynosi n – aczkolwiek jest to dosyć marne pocieszenie.

Merge sort

Merge sort, czyli sortowanie przez scalanie to algorytm działający zgodnie z zasadą dziel i rządź – jest to zatem algorytm rekurencyjny. Składa się z dwóch podstawowych procedur – podziału tablicy, a następnie łączenia już posortowanych tablic w większą część. Przy użyciu prostej obserwacji, że tablica jednoelementowa jest zawsze posortowana (z definicji) algorytm ten dzieli nam tablicę na jednoelementowe kawałki, a następnie łączy je w kolejności.

Sam algorytm łączenia jest bardzo ciekawy – w żadnym momencie nie cofa się on w tablicy, co było wykorzystywane przy komputerach, które operowały na taśmach z danymi przy łączeniu dwóch posortowanych taśm.

Zobaczmy algorytm na przykładzie zapisanym w pseudokodzie:

mergesort(T, p, r):
    if p < r:
        q → (p+r)/2
 	  mergesort(T, p, q)
        mergesort(T, q+1, r)
        merge(T, p, q, r)


Algorytm ten ma złożoność średnią i pesymistyczną równą nlog n. Jednak uwagi na swój charakter (nie sortuje w miejscu i wymaga sporo pamięci) nie jest najczęściej używanym algorytmem.

Quick sort

Quicksort, czyli sortowanie szybkie to obecnie najczęściej stosowany algorytm sortowania. Zbudowany jest znowu według zasady dziel i zwyciężaj. Najpierw wybieramy jeden element tzw. pivot. Następnie wszystkie elementy większe od pivota przenosimy na lewo od niego w tablicy, natomiast mniejsze na prawo. Następnie na tych dwóch podtablicach (większej od pivota i mniejsze od niego) wywołujemy rekurencyjnie algorytm quick sort.

Quicksort jest obecnie wykorzystywany np. w Javie czy w bazie PostgreSQL jako standardowy algorytm sortujący. Zobaczmy go na przykładzie, zapisanym w pseudokodzie:

 

algorithm quicksort(A, lo, hi) is
    if lo < hi then
        p := partition(A, lo, hi)
        quicksort(A, lo, p – 1)
        quicksort(A, p + 1, hi)

algorithm partition(A, lo, hi) is
    pivot := A[hi]
    i := lo - 1    
    for j := lo to hi - 1 do
        if A[j] ≤ pivot then
            i := i + 1
            swap A[i] with A[j]
    swap A[i+1] with A[hi]
    return i + 1

W algorytmie kluczowy jest wybór pivota – w najprostszej postaci możemy wybierać ten element arbitralnie (np. największy jak wyżej czy losowy). Więcej informacji na ten temat znajdziecie w artykule.

Quick sort ma złożoność obliczeniową średnią nlog n , natomiast pesymistyczną – jednak jest ona spotykana dosyć rzadko. Algorytm ten działa w miejscu i może być napisany w wersji stabilnej (kosztem wydajności). Realnie jest średnio dwa-trzy razy szybszy od merge sort (mimo tej samej złożoności asymptotycznej – pomijane w równaniach stałe robią tutaj różnicę).

A na koniec…

…finalna ciekawostka – udowodniono, że nie da się posortować danych (w przypadku tak ogólnym) szybciej (asymptotycznie) niż nlog n – jest to tzw. dolne ograniczenie tego problemu. Więcej informacji na ten temat możecie znaleźć w artykule Carnegie Mellon University.

 

Site Footer

Sliding Sidebar