Algorytmy sortujące – cz. II

W drugiej części cyklu artykułów o algorytmach sortowania przedstawię dwa nieco bardziej zaawansowane algorytmy: sortowanie przez scalanie i sortowanie szybkie oparte na metodzie dziel i zwyciężaj.

Metoda dziel i zwyciężaj

Metoda ta polega na rekurencyjnym podzieleniu problemu na mniejsze instancje (dwie lub więcej) tego samego lub podobnego problemu. Następnie rozwiązujemy problem dla mniejszych instancji. Na koniec scalamy wyniki poszczególnych fragmentów otrzymując rozwiązanie wyjściowego problemu.

Sortowanie przez scalanie

Sortowanie przez scalanie ang. merge sort, to rekurencyjny algorytm sortowania danych, mający zastosowanie przy danych dostępnych sekwencyjnie, na przykład w postaci listy jednokierunkowej (tj. łączonej jednostronnie). Opracowanie algorytmu przypisuje się Johnowi von Neumannowi.

Idea

Algorytm merge sort dzielimy na trzy części:

1. dzielenie tablicy na dwa wycinki
2. wywołanie rekurencyjne algorytmu sortującego na tych wycinkach
3. scalenie dwóch posortowanych wycinków

Dzielenie tablicy odbywa się dopóki wycinek zawiera więcej niż jeden element. W rezultacie otrzymamy n wycinków jednoelementowych.

Posortujemy tablicę 8-elementową: 6 9 4 8 7 1 2 3

Etap 1 – dzielenie n-elementowej tablicy na jednoelementowe części.

Etap 2 – sortowanie i scalanie dwóch fragmentów.

Implementacja

<?php
/**
 * Funkcja scalajaca 2 fragmenty
 *
 * @param int start indeks poczatkowy
 * @param int av indeks srodkowego elementu w tablicy
 * @param int end indeks ostatniego elementu
 * @param int t sortowana tablica
 * @return void
 */
function merge($start, $av, $end, &$t) {
    for($i=$start;$i<=$end;$i++) {
        $temp[$i]=$t[$i]; // kopiuje sortowana tablice do tablicy pomocniczej
    }

    $i=$start;
    $j=$av+1;
    $k=$start;

    while($i<=$av && $j<=$end) { // w petli przenoszone sa elementy z tablicy pomocniczej do tablicy z wynikami z uwzglednieniem sortowania
        if($temp[$i]<$temp[$j]) {
            $t[$k]=$temp[$i];
            $i++;
        } else {
            $t[$k]=$temp[$j];
            $j++;
        }
        $k++;
    }
    while($i<=$av) { // przenosi elementy z nieskopiowanego podzbioru do tablicy z wynikami, w przypadku, gdy drugi podzbior jest juz pusty
        $t[$k]=$temp[$i];
        $i++;
        $k++;
    }
}
/**
 * Funkcja sortowania przez scalanie
 *
 * @param int start indeks poczatkowy
 * @param int end indeks ostatniego elementu
 * @param int t sortowana tablica
 * @return void
 */
function mergeSort($start, $end, &$t) {
    if($start<$end) {
        $av=($start+$end)/2; // wyznaczamy srodek tablicy
        $av=(int)$av;
        mergeSort($start, $av, $t); // wywolanie sortowania dla lewego kawalka
        mergeSort($av+1, $end, $t); // wywolanie sortowania dla prawego kawalka
        merge($start, $av, $end, $t); // laczenie 2 czesci
    }
}
?>

Złożoność czasowa

Kolejne wywołania funkcji mergeSort można zobrazować za pomocą drzewa (patrz schematy), które ma wysokość log2n. Na poszczególnych poziomach algorytm wykonuje scalanie fragmentów, co kosztuje łącznie O(n). Sumując, złożoność określamy na
O(n log n).

Sortowanie szybkie

Sortowanie szybkie ang. Quicksort jest kolejnym przykładem algorytmu sortowania opartym na metodzie dziel i zwyciężaj. Algorytm ten został opracowany przez Charles Antony Richard Hoare’a w 1960 roku. W przypadku typowym algorytm ten jest najszybszym algorytmem sortującym z klasy złożoności obliczeniowej O(nlogn). Z tego też powodu znajduję się w standardowej bibliotece PHP. Warto zaznaczyć, że dla pewnych zestawów danych poziom wywołań rekurencyjnych może spowodować przepełnienie stosu i zablokowanie komputera.

Idea

Wybieramy dowolny element e z listy i dzielimy listę na dwie podlisty: A – elementów mniejszych lub równych od e i B – elementów większych od e. Następnie sortujemy oddzielnie listy A i B. Na koniec listę A, element e i listę B składamy w całość otrzymując posortowaną listę.

Przykład działania pokazany za pomocą kart:

Implementacja

<?php
/**
 * Algorytm szybkiego sortowania
 *
 * @param int left indeks lewego elementu
 * @param int right indeks prawego elementu
 * @param int t sortowana tablica
 * @return void
 */
function quickSort($left, $right, &$t) {
    if($left<$right) {
        $e=$left; // element wzgledem ktore wystepuje podzial
        for($i=$left+1;$i<=$right;$i++) {
            if($t[$i]<$t[$left]) { // jezeli el. na prawo jest mniejszy od el. z indeksem 'left' zamnien je
                $e++;
                $temp=$t[$i];
                $t[$i]=$t[$e];
                $t[$e]=$temp;
            }
        }
        $temp=$t[$left]; // zamiana el. e z el. o indeksie 'left'
        $t[$left]=$t[$e];
        $t[$e]=$temp;
        quickSort($left, $e-1, $t); // wywoalanie funkcji dla tablicy na lewo od 'e'
        quickSort($e+1, $right, $t); // wywoalanie funkcji dla tablicy na prawo od 'e'
    }
}
?>

Złożoność czasowa

Na każdym poziomie rekurencji lista dzielona jest na dwie części. Przy pierwszym wywołaniu następuje porównanie n-1 elementów. Zatem średnia złożoność obliczeniowa wynosi
O(nlogn). Pesymistyczna zaś – O(n2).

Zakończenie

W tym artykule zaprezentowałem dwa najczęściej używane algorytmy sortowania oparte na metodzie dziel i zwyciężaj. Są one dość proste w implementacji, a ich złożoność czasowa pozwala na sortowanie dużych tablic. W kolejnej części cyklu zaprezentuję metody sortowania w czasie liniowym.

Powiązane tematy

• Algorytmy sortujące – cz. I