Teoria IT: Podstawy algorytmów – sortowanie

By 18 grudnia 2015Teoria IT

Dzisiejszy  wpis z serii #teoriaIT poświęcony jest algorytmom sortowania.

Algorytmy sortowania to jedne z najczęściej wykorzystywanych algorytmów w programowaniu, choć współcześnie często nie bezpośrednio. Mimo tego choćby pobieżna znajomość zasady ich działania oraz cech / ograniczeń pozwala podejmować świadome decyzje podczas implementacji oraz rozumieć lepiej dokumentacje gotowych rozwiązań oraz ich ograniczenia.

Większość opisów odwołuje się do pojęć ‚większy’ / ‚mniejszy’, które nie mają zastosowania w odniesieniu do złożonych obiektów – chodzi jednak o ideę, można to rozumieć jako ‚x jest przed y w posortowanym zbiorze’ oraz ‚x jest za y w posortowanym 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 zastosowaniach różne algorytmy mogą okazać się lepsze lub gorsze, przy opisie stosuje się kilka kryteriów. Dwa najważniejsze to złożoność obliczeniowa (jak ilość operacji rośnie wraz ze wzrostem ilości danych wejściowych) oraz złożoność pamięciowa (w jaki sposób pamięć potrzebna do realizacji algorytmu rośnie wraz ze wzrostem ilości danych wejściowych). W przypadku powtórzenia sortowania dla dużej liczby losowych przypadków, czas oraz wykorzystana pamięć będą reprezentować taką właśnie charakterystykę.

Poza tymi parametrami opisuje się dodatkowo przypadek pozytywny oraz przypadek negatywny i złożoność obliczeniową w tych przypadkach (złożoność pamięciowa najczęściej jest taka sama i jest pomijana). Są to dane wejściowe, w których algorytm będzie szybszy lub wolniejszy od ‚uśrednionego’ przypadku. Jest to ważne, ponieważ rzeczywiste dane często nie są losowe (w matematycznym znaczeniu tego słowa) i mają określoną charakterystykę. Ta wiedza w połączeniu ze znajomością algorytmów pozwala wybrać ten, który będzie optymalny w określonym przypadku, o ile taka optymalizacja jest konieczna.

Algorytmy sortowania

Poniższe zestawienie obejmuje najpopularniejsze i najbardziej znane algorytmy. Oczywiście istnieje ich dużo więcej, można także ‚mieszać’ różne podejś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 obrazowego przedstawienia zasady działania – w każdym ‚przebiegu’ kolejna wartość w kolejności ‚wypływa’ jak bąbelek powietrza na powierzchnie wody.

W algorytmie tym w celu posortowania n elementów wykonujemy n-1 przebiegów. W każdym przebiegu zaczynamy od początku zbioru, bierzemy dwa elementy i zamieniamy je miejscami tak, aby większy był ‚wyżej’ (lub z większym indeksem itp). W pierwszym kroku robimy to dla elementów 1 i 2, w drugim kroku dla 2 i 3 itd. Każdy przebieg ‚wyciąga’ do góry kolejny element w kolejności, po wykonaniu wszystkich przebiegów nasz zbiór jest posortowany.

Algorytm ten jest najmniej optymalny z tych podstawowych i bardzo nieefektywny obliczeniowo – złożoność to O(n^2). Ma on jednak złożoność pamięciową O(1) (oznacza to, że poza miejscem potrzebnym do przechowywania sortowanego zbioru, nie wymaga dodatkowej pamięci).

Zaletą jest trywialna implementacja i przewidywalna ilość operacji, identyczna dla przypadku optymistycznego jak i pesymistycznego.

Przykładowy 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żliwe jest wprowadzenie optymalizacji, które nie zmieniają złożoności, ale przyspieszają działanie algorytmu w każdym przypadku:

  • w i’tym przebiegu można go zakończyć po n-i krokach, ponieważ pozostałe elementy są już posortowane; skróci to czas działania algorytmu o połowę.

Sortowanie szybkie (Quicksort)

Algorytm ten jest najpopularniejszy, jeśli chodzi o ilość zastosowań, ponieważ w ogólnym i uśrednionym przypadku jest on najbardziej optymalny, a jednocześnie prosty w implementacji. Jego wadą jest negatywny przypadek, kiedy to złożoność wynosi n^2 .

Algorytm jest rekursywny, tj. odwołuje się do samego siebie i jest przykładem podejścia dziel i zwyciężaj (divide and conquer). W każdym kroku ze zbioru elementów wybieramy dowolny element (nazywany pivot; może to być po prostu pierwszy z brzegu lub losowy, dla nieuporządkowanych danych nie ma to znaczenia) a następnie dzielimy pozostałe elementy na dwie grupy – te mniejsze od wybranego elementu (‚przed nim’) oraz większe od niego (‚za nim’). Każdą z tych grup sortujemy w ten sam sposób.

Algorytm ten jest stosunkowo prosty w implementacji, a jego wydajność jest zdecydowanie wystarczająca w ogólnym przypadku. Uśredniona złożoność obliczeniowa to O(n*log n), pamięciowa O(log n), ale w najgorszym przypadku złożoność obliczeniowa może wynieść O(n^2) – jest to zależne zarówno od danych wejściowych jak i sposobu doboru punktu pivot.

Przykładowa implementacja (nieoptymalna, możliwe jest wykorzystanie tylko jednej struktury, tutaj tworzymy nowe dla zwiększenia 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żliwa jest optymalizacja w niektórych przypadkach, np. sprawdzając warunki wstępne lub zamieniając sortowanie zbiorów o określonym rozmiarze na np. sortowanie kubełkowe, ale nie powodują one przyspieszenia w każdym przypadku.

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

Ten rodzaj sortowania jest najszybszy obliczeniowo, ale ma bardzo dużą złożoność pamięciową rzędu O(m), gdzie m to ilość możliwych wartości, bliższe optymalnego jest O(n), gdzie n to liczba różnych wartości wejścia. W wersji ‚ortodoksyjnej’ polega na stworzeniu mapy pomiędzy możliwymi wartościami, a ilością ich wystąpień w zbiorze, po czym odtworzeniu zbioru na tej podstawie.

Ponieważ takie podejście jest możliwe właściwie tylko dla liczb i to w określonym zakresie, często stosowane jest połączenie tego podejścia oraz innego algorytmu – sortowanie przez zliczanie służy do pogrupowania wstępnego, a następnie w każdej grupie korzystając z innego algorytmu wykonujemy właściwe sortowane. Przykładem może być sortowanie ciągów znaków – grupujemy je najpierw wg pierwszej litery w 26 grup i każdą z nich sortujemy osobno, następnie scalając wyniki.

Przykładowa implementacja (wersja ‚dosłowna’ – z odtwarzaniem wartości; założenie: wejście to tylko liczby z zakresu 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;
}

Algorytm ten koncepcyjnie jest podobny do hashowania (więcej znajdziesz w materiale kontrakt hashCode equals), ale wymaga możliwości rekonstrukcji obiektu na podstawie wartości hash (co w praktycznych zastosowaniach jest mało użyteczne).

Sortowanie przez scalanie (Merge sort)

Jest to kolejny przykład podejścia dziel i rządź – w tym wypadku polega on na podziale zbioru na n równych podzbiorów (najczęściej jednoelementowych) a następnie scalaniu ich ze sobą uzyskując większe, posortowane podzbiory. Najprostsza implementacja jest rekurencyjna, ale nie wynika to bezpośrednio z samego algorytmu – scalanie może się odbywać iteracyjnie, dołączając kolejne podzbiory do jednego ‚posortowanego’. Dużą zaletą tego algorytmu jest możliwość zrównoleglenia – operacje sortowania można wykonywać na kilku wątkach lub nawet na wielu różnych maszynach w tym samym czasie.

Przykładowa implementacja (ponownie, nie jest to implementacja optymalna, ale zgodna z definicją i obrazują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)

Sortowanie przez kopcowanie (częściej spotykaną nazwą, także w polskiej literaturze, jest heap sort) to kolejny z algorytmów mający praktyczne zastosowanie – jego wydajność jest najczęściej minimalnie mniejsza niż QuickSort, ale wydajność pesymistyczna jest zdecydowanie lepsza. Polega on na budowaniu kopca – czyli struktury, w której elementy są posortowane w określonym porządku – a następnie iteracyjnym dodawaniu kolejnych elementów zbioru. Po każdym dodaniu konieczne jest przywrócenie właściwości kopca, tzn. uporządkowanie elementów.

Kopiec jest strukturą podobną do drzewa – pod kątem złożoności wstawienie jednego elementu wymaga maksymalnie log(n) operacji. Dlatego złożoność w pesymistycznym przypadku wynosi tyle samo, co w ogólnym przypadku i jest równa nlog n. Z punktu widzenia tego algorytmu nie ma pesymistycznych przypadków, nie ma też optymistycznych przypadków – jego złożoność jest przewidywalna co czyni go preferowanym w niektórych zastosowaniach, szczególnie przy obliczeniach czasu rzeczywistego (np. w sterowaniu procesami produkcyjnymi, systemach krytycznych takich jak podsystemy w samolotach itp). Algorytm ten ma złożoność pamięciową O(1), obliczeniową O(n log n).

Poniższy przykład wykorzystuje tablicę do reprezentacji 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

Ciekawostka: w 2007 roku naukowcy w ramach ciekawostki przeanalizowali najmniej efektywne algorytmy sortowania, który oczywiście nie będzie marnował przebiegów. Z czegoś, co miało być żartem, wyniknęły całkiem poważne badania mająca realne zastosowanie w analizie danych. Dla zainteresowanych polecamy artykuł na Wikipedii na temat Bogosort.

Podsumowanie

Poznałaś dzisiaj najważniejsze algorytmy sortujące – bubble sort, merge sort, quick sort, heap sort, bucket sort. W zdecydowanej większości przypadków nie powinnaś ich implementować samodzielnie – lepiej skorzystać z gotowych implementacji. Ich znajomość jest jednak ważna, aby móc podjąć świadomą decyzję w pewnych specyficznych sytuacjach, a także aby być w stanie oszacować ich wpływ na Twoją implementację. Poniżej podsumowanie omówionych algorytmów.

Algorytm Złożoność obliczeniowa
przypadek ogólny
Złożoność obliczeniowa
przypadek optymistyczny
Złożoność obliczeniowa
przypadek pesymistyczny
Złożoność pamięciowa
nie licząc wejścia
Zastosowanie praktyczne
Bubble sort  O(n^2)  O(n^2)  O(n^2)  O(1)  brak
Quick sort  O(n*log n)  O(n*log n)  O(n^2)  O(log n)  ogólny przypadek
Merge sort  O(n*log n)  O(n*log n)  O(n*log n)  O(n)  sortowanie rozproszone
Bucket sort  O(n+k)  O(n+k)  O(n^2)  O(n * k)  sortowanie wstępne, szybkie (jeśli pamięć nie jest problemem)
Heap sort O(n*log n)  O(n)  O(n*log n)  O(1)  ogólny przypadek, z gwarancją w najgorszym przypadku
  •  
  •  
  •  
  •  
  •  
  • Tomek

    Wiem, że się czepiam, ale nie ma czegoś takiego jak bardziej optymalny. Optymalny czyli najlepszy, może być jedynie bliższy optymalnego. Poza tym, świetny artykuł ;)

    • Dzięki za takie czepialstwo i czujność, oczywiście masz rację, ale potocznie przyjęło się tak mówić, stąd i wkradło się to do naszego tekstu. Poprawiamy i dziękujemy!

  • Papi

    Czemu w QuickSorcie na końcu dodajemy jeszcze pivot? Nie jest on przypadkiem zawarty już w liście większe(która zawiera większe bądź równe)? Pzdr

    • Faktycznie, to nasze niedopatrzenie – zamiast get() nad pętlą powinno być remove() (już poprawione w lekcji) – dzięki za czujność!

      Odpowiadając bardziej ogólnie, dlaczego nie uwzględniamy też punktu ‚pivot’ w sortowaniu – wynika to z tego, że znamy już jego pozycję (pomiędzy dwoma posortowanymi listami), dzięki czemu minimalnie przyspieszamy sortowanie nie uwzględniając tego punktu w zbiorach.

  • MarekAG

    Trochę po niewczasie trafiłem na ten artykuł, ale może komuś się to przyda:

    W tabelce jest błąd. Złożoność optymistyczna heapsort powinna być taka sama jak pesymistyczna. Czyli O(n*log n).

    P.S.
    Świetny blog ;)

    • Jedna z wariacji heapsortu – tzw. smoothsort – osiąga złożoność optymistyczną bliską O(n) w przypadku posortowanych ciągów. Z uwagi na złożoność implementacji jest nieczęsto stosowany, ale formalnie jest też odmianą algorytmu heapsort. Stąd w tabelce znalazła się wartość O(n) :)

      Dzięki za miłe słowa i uważne czytanie ;)

  • Dominik

    Błędy:
    QuickSort:
    Integer pivot = kolekcja.remove(kolekcja.length/2); // Nie length, a size()
    Brak return wynik;