Teoria IT: Podstawy algorytmów — sortowanie

Dzisiejszy  wpis z serii #teo­ri­aIT poświę­cony jest algo­ryt­mom sortowania. 

Algo­ryt­my sor­towa­nia to jedne z najczęś­ciej wyko­rzysty­wanych algo­ryt­mów w pro­gramowa­niu, choć współcześnie częs­to nie bezpośred­nio. Mimo tego choć­by pobież­na zna­jo­mość zasady ich dzi­ała­nia oraz cech / ograniczeń pozwala pode­j­mować świadome decyz­je pod­czas imple­men­tacji oraz rozu­mieć lep­iej doku­men­tac­je gotowych rozwiązań oraz ich ograniczenia.

Więk­szość opisów odwołu­je się do pojęć ‚więk­szy’ / ‚mniejszy’, które nie mają zas­tosowa­nia w odniesie­niu do złożonych obiek­tów — chodzi jed­nak o ideę, moż­na to rozu­mieć jako ‚x jest przed y w posor­towanym zbiorze’ oraz ‚x jest za y w posor­towanym zbiorze’; słowa większy/mniejszy są użyte dla ułatwienia analogii ze światem liczb i uproszczenia przykładów.

Sposób opisu

Ponieważ w różnych zas­tosowa­ni­ach różne algo­ryt­my mogą okazać się lep­sze lub gorsze, przy opisie sto­su­je się kil­ka kry­ter­iów. Dwa najważniejsze to złożoność obliczeniowa (jak ilość oper­acji rośnie wraz ze wzrostem iloś­ci danych wejś­ciowych) oraz złożoność pamię­ciowa (w jaki sposób pamięć potrzeb­na do real­iza­cji algo­ryt­mu rośnie wraz ze wzrostem iloś­ci danych wejś­ciowych). W przy­pad­ku powtórzenia sor­towa­nia dla dużej licz­by losowych przy­pad­ków, czas oraz wyko­rzys­tana pamięć będą reprezen­tować taką właśnie charakterystykę.

Poza tymi para­me­tra­mi opisu­je się dodatkowo przy­padek pozy­ty­wny oraz przy­padek negaty­wny i złożoność obliczeniową w tych przy­pad­kach (złożoność pamię­ciowa najczęś­ciej jest taka sama i jest pomi­jana). Są to dane wejś­ciowe, w których algo­rytm będzie szyb­szy lub wol­niejszy od ‚uśred­nionego’ przy­pad­ku. Jest to ważne, ponieważ rzeczy­wiste dane częs­to nie są losowe (w matem­aty­cznym znacze­niu tego słowa) i mają określoną charak­terystykę. Ta wiedza w połącze­niu ze zna­jo­moś­cią algo­ryt­mów pozwala wybrać ten, który będzie opty­mal­ny w określonym przy­pad­ku, o ile taka opty­mal­iza­c­ja jest konieczna.

Algorytmy sortowania

Poniższe zestaw­ie­nie obe­j­mu­je najpop­u­larniejsze i najbardziej znane algo­ryt­my. Oczy­wiś­cie ist­nieje ich dużo więcej, moż­na także ‘mieszać’ różne pode­jś­cia w zależnoś­ci od potrzeb, ale poniższe są pewnym kanonem wiedzy, który warto znać.

Sortowanie bąbelkowe (Bubble sort)

Nazwa pochodzi od obra­zowego przed­staw­ienia zasady dzi­ała­nia — w każdym ‚prze­biegu’ kole­j­na wartość w kole­jnoś­ci ‚wypły­wa’ jak bąbelek powi­etrza na powierzch­nie wody.

W algo­ryt­mie tym w celu posor­towa­nia n ele­men­tów wykonu­je­my n‑1 prze­biegów. W każdym prze­biegu zaczy­namy od początku zbioru, bierze­my dwa ele­men­ty i zamieni­amy je miejs­ca­mi tak, aby więk­szy był ‚wyżej’ (lub z więk­szym indek­sem itp). W pier­wszym kroku robimy to dla ele­men­tów 1 i 2, w drugim kroku dla 2 i 3 itd. Każdy prze­bieg ‚wycią­ga’ do góry kole­jny ele­ment w kole­jnoś­ci, po wyko­na­niu wszys­t­kich prze­biegów nasz zbiór jest posortowany.

Algo­rytm ten jest najm­niej opty­mal­ny z tych pod­sta­wowych i bard­zo nieefek­ty­wny obliczeniowo — złożoność to O(n^2). Ma on jed­nak złożoność pamię­ciową O(1) (oznacza to, że poza miejscem potrzeb­nym do prze­chowywa­nia sor­towanego zbioru, nie wyma­ga dodatkowej pamięci).

Zaletą jest try­wial­na imple­men­tac­ja i przewidy­wal­na ilość oper­acji, iden­ty­cz­na dla przy­pad­ku optymisty­cznego jak i pesymistycznego.

Przykład­owy kod:

public void bubbleSort(int[] kolekcja) {
    for (int i = 0; i<kolekcja.length; i++) {
        for (int j = 1; j<kolekcja.length; j++) {
            if (kolekcja[j]<kolekcja[j-1]) {
                int wieksza = kolekcja[j-1];
                kolekcja[j-1] = kolekcja[j];
                kolekcja[j] = wieksza;
            }
        }
    }
}

Możli­we jest wprowadze­nie opty­mal­iza­cji, które nie zmieni­a­ją złożonoś­ci, ale przyspiesza­ją dzi­ałanie algo­ryt­mu w każdym przypadku:

• w i’tym prze­biegu moż­na go zakończyć po n‑i krokach, ponieważ pozostałe ele­men­ty są już posor­towane; skró­ci to czas dzi­ała­nia algo­ryt­mu o połowę.

Sortowanie szybkie (Quicksort)

Algo­rytm ten jest najpop­u­larniejszy, jeśli chodzi o ilość zas­tosowań, ponieważ w ogól­nym i uśred­nionym przy­pad­ku jest on najbardziej opty­mal­ny, a jed­nocześnie prosty w imple­men­tacji. Jego wadą jest negaty­wny przy­padek, kiedy to złożoność wynosi n^2 .

Algo­rytm jest rekursy­wny, tj. odwołu­je się do samego siebie i jest przykła­dem pode­jś­cia dziel i zwyciężaj (divide and con­quer). W każdym kroku ze zbioru ele­men­tów wybier­amy dowol­ny ele­ment (nazy­wany piv­ot; może to być po pros­tu pier­wszy z brzegu lub losowy, dla nieu­porząd­kowanych danych nie ma to znaczenia) a następ­nie dzie­limy pozostałe ele­men­ty na dwie grupy — te mniejsze od wybranego ele­men­tu (‚przed nim’) oraz więk­sze od niego (‚za nim’). Każdą z tych grup sor­tu­je­my w ten sam sposób.

Algo­rytm ten jest sto­sunkowo prosty w imple­men­tacji, a jego wyda­jność jest zde­cy­dowanie wystar­cza­ją­ca w ogól­nym przy­pad­ku. Uśred­niona złożoność obliczeniowa to O(n*log n), pamię­ciowa O(log n), ale w naj­gorszym przy­pad­ku złożoność obliczeniowa może wynieść O(n^2) — jest to zależne zarówno od danych wejś­ciowych jak i sposobu doboru punk­tu pivot.

Przykład­owa imple­men­tac­ja (nieop­ty­mal­na, możli­we jest wyko­rzys­tanie tylko jed­nej struk­tu­ry, tutaj tworzymy nowe dla zwięk­szenia czytelności):

public List<Integer> quicksort(List<Integer> kolekcja) {
    if (kolekcja.size()<=1) {return kolekcja;}
    List<Integer> wynik = new ArrayList<Integer>();
    List<Integer> mniejsze = new ArrayList<Integer>();
    List<Integer> wieksze = new ArrayList<Integer>();
    Integer pivot = kolekcja.remove(kolekcja.length/2);
    for (Integer obiekt : kolekcja) {
        if (obiekt<pivot) {
            mniejsze.add(obiekt);
        } else {
            wieksze.add(obiekt);
        }
    }
    mniejsze = quicksort(mniejsze);
    wieksze = quicksort(wieksze);
    wynik.addAll(mniejsze);
    wynik.add(pivot);
    wynik.addAll(wieksze);
}

Możli­wa jest opty­mal­iza­c­ja w niek­tórych przy­pad­kach, np. sprawdza­jąc warun­ki wstęp­ne lub zamieni­a­jąc sor­towanie zbiorów o określonym rozmi­arze na np. sor­towanie kubełkowe, ale nie powodu­ją one przyspieszenia w każdym przypadku.

Sortowanie przez zliczanie (bucket sort; czasem nazywane także sortowaniem kubełkowym)

Ten rodzaj sor­towa­nia jest najszyb­szy obliczeniowo, ale ma bard­zo dużą złożoność pamię­ciową rzę­du O(m), gdzie m to ilość możli­wych wartoś­ci, bliższe opty­mal­nego jest O(n), gdzie n to licz­ba różnych wartoś­ci wejś­cia. W wer­sji ‚ortodoksyjnej’ pole­ga na stworze­niu mapy pomiędzy możli­wy­mi wartoś­ci­a­mi, a iloś­cią ich wys­tąpień w zbiorze, po czym odt­worze­niu zbioru na tej podstawie.

Ponieważ takie pode­jś­cie jest możli­we właś­ci­wie tylko dla liczb i to w określonym zakre­sie, częs­to stosowane jest połącze­nie tego pode­jś­cia oraz innego algo­ryt­mu — sor­towanie przez zliczanie służy do pogrupowa­nia wstęp­nego, a następ­nie w każdej grupie korzys­ta­jąc z innego algo­ryt­mu wykonu­je­my właś­ci­we sor­towane. Przykła­dem może być sor­towanie ciągów znaków — grupu­je­my je najpierw wg pier­wszej litery w 26 grup i każdą z nich sor­tu­je­my osob­no, następ­nie scala­jąc wyniki.

Przykład­owa imple­men­tac­ja (wer­s­ja ‚dosłow­na’ — z odt­warzaniem wartoś­ci; założe­nie: wejś­cie to tylko licz­by z zakre­su 0‑ZAKRES_WARTOSCI_MAX):

public int[] przezZliczanie(int[] kolekcja) {
    int[] zliczenia = new int[ZAKRES_WARTOSCI_MAX];
    for (int obiekt : kolekcja) {
        zliczenia[obiekt]++;
    }
    //generujemy wynik
    int wynik = new int[kolekcja.length];
    for (int i=0, j=0; i<ZAKRES_WARTOSCI_MAX; i++) {
        while (zliczenia[i]>0) {
            wynik[j] = i;
            j++;
        }
    }
    return wynik;
}

Algo­rytm ten kon­cep­cyjnie jest podob­ny do hashowa­nia (więcej zna­jdziesz w mate­ri­ale kon­trakt hash­Code equals), ale wyma­ga możli­woś­ci rekon­strukcji obiek­tu na pod­staw­ie wartoś­ci hash (co w prak­ty­cznych zas­tosowa­ni­ach jest mało użyteczne).

Sortowanie przez scalanie (Merge sort)

Jest to kole­jny przykład pode­jś­cia dziel i rządź — w tym wypad­ku pole­ga on na podziale zbioru na n równych podzbiorów (najczęś­ciej jed­noele­men­towych) a następ­nie scala­niu ich ze sobą uzysku­jąc więk­sze, posor­towane podzbio­ry. Najprost­sza imple­men­tac­ja jest rekuren­cyj­na, ale nie wyni­ka to bezpośred­nio z samego algo­ryt­mu — scalanie może się odby­wać iter­a­cyjnie, dołącza­jąc kole­jne podzbio­ry do jed­nego ‚posor­towanego’. Dużą zaletą tego algo­ryt­mu jest możli­wość zrównole­gle­nia — oper­ac­je sor­towa­nia moż­na wykony­wać na kilku wątkach lub nawet na wielu różnych maszy­nach w tym samym czasie.

Przykład­owa imple­men­tac­ja (ponown­ie, nie jest to imple­men­tac­ja opty­mal­na, ale zgod­na z definicją i obrazu­ją­ca koncepcje).

public int[] scalDwie(int[] pierwsza, int[] druga) {
    int[] wynik = new int[pierwsza.length + druga.length];
    int indeksWynik = 0;
    int indeksPierwszy = 0, indeksDrugi = 0;
    while (indeksPierwszy<pierwsza.length || indeksDrugi<druga.length) {
        if ((indeksPierwszy<pierwsza.length && 
                pierwsza[indeksPierwszy] < druga[indeksDrugi]) || indeksDrugi==druga.length) {
            wynik[indeksWynik] = pierwsza[indeksPierwszy];
            indeksPierwszy++;
        } else {
            wynik[indeksWynik] = druga[indeksDrugi];
            indeksDrugi++;
        }
        indeksWynik++;
    }
    return wynik;
}

public int[] sortowaniePrzezScalanie(int[] kolekcja) {
    int podzial = kolekcja.length/2;
    int[] prawa = sortowaniePrzezScalanie(Arrays.copyOfRange(kolekcja, 0, podzial));
    int[] lewa = sortowaniePrzezScalanie(Arrays.copyOfRange(kolekcja, podzial, kolekcja.length));
    return scalDwie(prawa, lewa);
}

Sortowanie kopcowe (heap sort; funkcjonuje także nazwa sortowanie przez kopcowanie)

Sor­towanie przez kop­cow­anie (częś­ciej spo­tykaną nazwą, także w pol­skiej lit­er­aturze, jest heap sort) to kole­jny z algo­ryt­mów mają­cy prak­ty­czne zas­tosowanie — jego wyda­jność jest najczęś­ciej min­i­mal­nie mniejsza niż Quick­Sort, ale wyda­jność pesymisty­cz­na jest zde­cy­dowanie lep­sza. Pole­ga on na budowa­niu kop­ca — czyli struk­tu­ry, w której ele­men­ty są posor­towane w określonym porząd­ku — a następ­nie iter­a­cyjnym dodawa­niu kole­jnych ele­men­tów zbioru. Po każdym doda­niu konieczne jest przy­wróce­nie właś­ci­woś­ci kop­ca, tzn. uporząd­kowanie elementów.

Kopiec jest struk­turą podob­ną do drze­wa — pod kątem złożonoś­ci wstaw­ie­nie jed­nego ele­men­tu wyma­ga maksy­mal­nie log(n) oper­acji. Dlat­ego złożoność w pesymisty­cznym przy­pad­ku wynosi tyle samo, co w ogól­nym przy­pad­ku i jest rów­na nlog n. Z punk­tu widzenia tego algo­ryt­mu nie ma pesymisty­cznych przy­pad­ków, nie ma też optymisty­cznych przy­pad­ków — jego złożoność jest przewidy­wal­na co czyni go prefer­owanym w niek­tórych zas­tosowa­ni­ach, szczegól­nie przy obliczeni­ach cza­su rzeczy­wis­tego (np. w sterowa­niu proce­sa­mi pro­duk­cyjny­mi, sys­temach kry­ty­cznych takich jak podsys­te­my w samolotach itp). Algo­rytm ten ma złożoność pamię­ciową O(1), obliczeniową O(n log n).

Poniższy przykład wyko­rzys­tu­je tablicę do reprezen­tacji kopca.

public void sort(int arr[])
{ 
    buildHeap(arr); 
    for (int i = arr.length-1; i > 0; i--)
    {
       swap(arr, 0, i);
       buildMaxHeap(arr, 0, i-1);
    }
} 

/* Budujemy stertę */ 
public static void buildHeap(int arr[])
{
    for (int i = (arr.length-1)/2; i >= 0; i--)
    buildMaxHeap(arr, i, arr.length-1); 
}

/* Podmieniamy największy element w stercie */ 
public static void buildMaxHeap(int arr[], int i, int N)
    { 
    int left = 2*i ;
    int right = 2*i + 1;
    int max = i;
    if (left <= N && arr[left] > arr[i])
    max = left;
    if (right <= N && arr[right] > arr[max]) 
    max = right; 
    if (max != i)
    {
       swap(arr, i, max);
       buildMaxHeap(arr, max, N);
    }
} 

/* Zamieniamy dwa elementy w tablicy */
public static void swap(int arr[], int i, int j)
{
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp; 
}

Ciekawostka

Cieka­wost­ka: w 2007 roku naukow­cy w ramach cieka­wost­ki przeanal­i­zowali najm­niej efek­ty­wne algo­ryt­my sor­towa­nia, który oczy­wiś­cie nie będzie marnował prze­biegów. Z czegoś, co miało być żartem, wyniknęły całkiem poważne bada­nia mają­ca realne zas­tosowanie w anal­izie danych. Dla zain­tere­sowanych pole­camy artykuł na Wikipedii na tem­at Bogosort.

Podsumowanie

Poz­nałaś dzisi­aj najważniejsze algo­ryt­my sor­tu­jące — bub­ble sort, merge sort, quick sort, heap sort, buck­et sort. W zde­cy­dowanej więk­szoś­ci przy­pad­ków nie powin­naś ich imple­men­tować samodziel­nie — lep­iej sko­rzys­tać z gotowych imple­men­tacji. Ich zna­jo­mość jest jed­nak waż­na, aby móc pod­jąć świadomą decyzję w pewnych specy­ficznych sytu­ac­jach, a także aby być w stanie osza­cow­ać ich wpływ na Two­ją imple­men­tację. Poniżej pod­sumowanie omówionych algorytmów.