0

Algorytm sortowania szybkiego – Strefa juniora

Algorytm sortowania szybkiego

Cześć! Nadszedł czas na przestawienie już ostatniego algorytmy sortowania tj. sortowania szybkiego (Quick Sort). Jest to najpopularniej wykorzystywany algorytm sortowania, głównie z powodu dobrej złożoności obliczeniowej, która wynosi O(nlogn), ale również z powodu prostej implementacji. Algorytm ten znajduje się chyba we wszystkich bibliotekach standardowych.

Artykuł ten należy do cyklu przedstawiającego algorytmy rozwiązujące problem sortowania. Jeżeli temat Cię zainteresował, to koniecznie przeczytaj inne artykuły z tej tematyki, znajdziesz je w dziale algorytmów. Dodatkowo wpis ten zawiera informacje pomocne dla osoby zaczynającej swoją przygodę z programowaniem. Jeżeli jesteś taką osobą, to koniecznie odwiedź dział juniora.

Sposób działania sortowania szybkiego

Działanie algorytmu jest znacznie prostsze niż ostatnio przedstawionego sortowania kubełkowego. Opiera się ona na zasadzie „dziel i zwyciężaj” i rekurencji. Algorytm jest stosunkowo prosty:

  1. Wybierz punkt podziału tablicy. Zazwyczaj wybiera się środkowy element.
  2. Podziel tablicę na dwie części.
  3. Do pierwszej części przenieś elementy mniejsze/równe od punktu podziału, a do drugiej elementy większe od punktu podziału.
  4. Jeżeli liczba elementów tablicy wynosi 1, to przerwij sortowanie tej tablicy.
  5. Tablicę lewą posortuj, rozpoczynając od pkt. 1.
  6. Tablicę prawą posortuj, rozpoczynając od pkt. 1.

Przykład

Jako przykład posłuży nam 7 elementowa tablica:

{1,7,2,3,5,9,6}

Kroki, które musimy wykonać aby posortować tablicę za pomocą sortowania szybkiego to:

  1. Wyznaczamy punkt podziału, będzie nim indeks = (6-0) / 2 = 3.
  2. Dzielimy więc tablicę na dwie mniejsze, jako punkt podziału przyjmujemy wartość 3. Podział wygląda następująco:
    {1,2} 3 {7,5,9,6}
  3. Sortujemy lewą tablicę, indeks wynosi teraz (1 – 0)/2 = 0.
  4. Dzielimy tablice na mniejsze tablice. Wynik wygląda tak:
    {1} {2}
  5. Z racji, że każda z tablic posiada już jeden element nie dokonujemy dalszego podziału.
  6. Sortujemy teraz tablicę:
    {7,5,9,6}

    Wyznaczamy punkt podziału, będzie to element o indeksie 1, czyli wartość 5.

  7. Dzielimy tablicę na mniejsze tablice. Wynik wygląda tak:
    5 {7,9,6}
  8. Tablicy lewej nie trzeba teraz dzielić, trzeba podzielić tablicę prawą. Najpierw jednak przypomnijmy, jak wygląda obecny stan:
    {1}{2}{3}{5}{7,9,6}
  9. Przystępujemy do dzielenia tablicy:
    {7,9,6}

    Punkt podziału to liczba 9. Wynik podziału:

    {7,6}{9}
  10. Wystarczy podzielić teraz lewą tablicę, bo prawa ma jeden element. Wynik to oczywiście:
    {6} {7}
  11. Ostateczny wynik:
    {1,2,3,5,6,7,9}

Jak widać algorytm tak jak mówiłem jest prosty. Jest to oczywiście dosyć uproszczona interpretacja algorytmu i mało wydajna, jednak chciałem żebyś zrozumiał sposób działania, zanim zaczniemy optymalizować.

Implementacja algorytmu sortowania szybkiego w C#

Tradycyjnie przedstawię dwie implementacje:

  • prostą – przeznaczona dla każdego juniora,
  • uniwersalną – implementację bardziej życiową i bardziej zoptymalizowaną.

Na końcu oczywiście udowodnię działanie algorytmu za pomocą UnitTestów o standardowych danych testowych.

Tak więc, nie przedłużając wstępu, zobacz proszę prostą implementację.

Cały kod użyty w tym przykładzie znajduje się również na GitHubie.
Kod napisany jest tak, aby był jak najbardziej czytelny. Oznacza to, że pominąłem wszelkie walidacje danych wejściowych. W kodzie produkcyjnym pamiętaj, aby zawsze upewniać się, że to co dostarcza Ci użytkownik ma prawidłowy format.

Prosta implementacja

Kod prostej implementacji tak jak pisałem wcześniej jest bardzo nie optymalny, jest on tak napisany, aby był jak najłatwiejszy do zrozumienia. Kod prezentuje się następująco:

public class SimpleQuickSort
{
    public void Sort(int[] table)
    {
        List<int> output = QuickSort(table.ToList());
        for (int index = 0; index < table.Length; ++index)
        {
            table[index] = output[index];
        }
    }
 
    private List<int> QuickSort(List<int> table)
    {
        if (table.Count <= 1)
        {
            return table;
        }
        int pivot = table.Count / 2;
        List<int> listLeft = new List<int>();
        List<int> listRight = new List<int>();
        for (int i = 0; i < table.Count; ++i)
        {
            if (i == pivot)
            {
                continue;
            }
            if (table[i] > table[pivot])
            {
                listRight.Add(table[i]);
            }
            else
            {
                listLeft.Add(table[i]);
            }
        }
        List<int> result = new List<int>();
        result.AddRange(QuickSort(listLeft));
        result.Add(table[pivot]);
        result.AddRange(QuickSort(listRight));
        return result;
    }
}

Jak widzisz funkcja jest dosyć długa, przyczyną jest wykonywanie zbyt dużej ilości operacji, zostanie to naprawione w uniwersalnej implementacji.

Analizę zacznijmy jednak od tego kodu. Na samym początku przekazana tablica konwertowana jest na listę, a ta z kolei wędruje do funkcji wewnętrznej. Funkcja QuickSort na samym początku sprawdza warunek stopu tj. jeżeli przekazana lista nie zawiera lub zawiera tylko jeden element, to od razu jest zwracana jako wynik. Następnie jako punkt podziału wybierany jest środkowy element listy. Tworzone są dwie nowe listy przeznaczone na elementy większe i mniejsze/równe od elementu podziału. Elementy są rozdzielane z pominięciem elementu podziału (on zostaje na swoim miejscu). Następnie utworzone tablice są przekazywane do rekurencyjnie wywoływanej funkcji. Na samym końcu funkcja składa wszystkie dane w odpowiedniej kolejności: lewa, punkt podziału, prawa. Lista lewa i prawa na pewno są posortowane, a punkt podziału na pewno jest między nimi.

Skoro prosta implementacja została już omówiona, przejdźmy od razu do bardziej skomplikowanego przykładu.

Implementacja uniwersalna

W tej implementacji pozbyłem się tworzenia niepotrzebnych obiektów, wykorzystałem działanie jedynie na elementach tablicy. Kod może wydawać się „dziwny”, ale został on dokładnie omówiony poniżej. Implementacja prezentuje się następująco:

public class QuickSort : ISortAlgorithm
{
    public void Sort(IComparable[] table)
    {
        QuickSortIntern(table, 0, table.Length - 1);
    }
 
    private void QuickSortIntern(IComparable[] elements, int left, int right)
    {
        if (left >= right)
        {
            return;
        }
        int onLeft = left;
        int onRight = right;
        IComparable comparableElement = elements[(onRight + onLeft) >> 1]; // (right + left) / 2
        do
        {
            while (elements[onLeft].CompareTo(comparableElement) < 0) ++onLeft;
            while (elements[onRight].CompareTo(comparableElement) > 0) --onRight;
            if (onLeft <= onRight)
            {
                IComparable temp = elements[onLeft];
                elements[onLeft] = elements[onRight];
                elements[onRight] = temp;
                ++onLeft;
                --onRight;
            }
        }
        while (onLeft <= onRight);
        QuickSortIntern(elements, left, onRight);
        QuickSortIntern(elements, onLeft, right);
    }
}

Działanie jak wcześniej opiera się na wewnętrznej funkcji wołanej rekurencyjne. Jednak teraz posiada ona dwa dodatkowe parametry i nie oddaje wyniku. Parametrami są indeksy w tablicy, która określają pod-tablicę czyli fragment tablicy głównej, który trzeba posortować. Powodem takiego podejścia jest to, że cały czas działamy na tej samej tablicy, zamieniamy ewentualnie elementy miejscami.

Na samym początku funkcji wewnętrznej jest sprawdzane czy przekazane indeksy w ogóle mają sens tj. prawy musi być większy od lewego. Następnie tworzone są dwie zmienne lokalne, które będą przydatne w enumeracji. Zmienne te mają początkowo wartość zadanych indeksów. Dodatkowo wyznaczany jest element, która znajduje się pośrodku „podtablicy” (operacja >> 1 to oczywiście przesuniecie bitowe, tożsame z dzieleniem przez 2). I tak dochodzimy do głównej pętli, która może wydawać się najbardziej skomplikowana.

Zaczynamy sprawdzać elementy od lewej strony, jeżeli sprawdzany element jest mniejszy od elementu porównawczego to przesuwamy pomocniczy indeks onLeft o 1 w prawo. Operacja ta jest powtarzana do czasu, aż warunek jest spełniony. Podobnie robimy od prawej strony, tyle że korzystamy z indeksu onRight i przesuwamy go w lewo, jeżeli porównywany element jest większy od elementu porównawczego.

Po tych pętlach sprawdzany jest warunek, jeżeli onLeft jest mniejszy/równy onRight to dokonywana jest zamiana elementów w tablicy. Indeksy są odpowiednio modyfikowane i następuje kolejny obrót pętli. Pętla ta trwa do czasu, kiedy indeks onLeft jest mniejszy/równy onRight. Jeżeli jest inaczej, oznacza to, że pod-tablica już została podzielona. Na samym końcu sortowane są utworzone pod-tablice tj. wyznaczane przez obliczone indeksy.

Algorytm ten jest szybki ale możliwe, że masz problemy z zrozumieniem. Przeanalizujmy zatem działanie na przykładzie:

T = {1,7,2,3,5,9,6}

Opiszę tylko jednej przebieg funkcji, powinno Ci to wystarczyć aby załapać ;).

  1. T przekazywana jest do sortowania.
  2. Do funkcji wewnętrznej przekazywana jest T oraz left = 0, right = T.Length -1 = 6.
  3. Indeksy pomocnicze są odpowiednio ustawiane onLeft = 0, onRight = 6.
  4. Element do porównania wyznaczany jest jako T[0+6 >> 1] = T[3] = 3.
  5. Rozpoczyna się główna pętla do…while.
  6. Sprawdzany jest warunek T[onLeft = 0] < 3 → 1 < 3 → TRUE. Indeks onLeft jest inkrementowany.
  7. Sprawdzany jest warunek T[onLeft = 1] < 3 → 7 < 3 → FALSE.
  8. Sprawdzany jest warunek T[onRight = 6] > 3 → 6 > 3 → TRUE. Indeks onRight jest dekrementowany.
  9. Sprawdzany jest warunek T[onRight = 5] > 3 → 9 > 3 → TRUE. Indeks onRight jest dekrementowany.
  10. Sprawdzany jest warunek T[onRight = 4] > 3 → 4 > 3 → TRUE. Indeks onRight jest dekrementowany.
  11. Sprawdzany jest warunek T[onRight = 3] > 3 → 3 > 3 → FALSE.
  12. Sprawdzany jest warunek onLeft <= onRight → 1 <=3 → TRUE. Elementy T[onLeft] = 7 oraz T[onRight] = 3 są zamieniane miejscami. Indeks onLeft jest inkrementowany, onRight jest dekrementowany. Stan obecny wygląda następująco:
    T= {1,3,2,7,5,9,6}, onLeft =2, onRight = 2, left = 0, right = 6
    czyli jak widzisz, wszystkie elementy mniejsze/równe elementu porównawczemu tj. 3, znajdują się w lewej części tablicy, pozostałe w prawej.
  13. Teraz wyznaczone przez indeksy pod-tablice tj. {1,3,2} i {7,5,9,6} są sortowane ponownie.

Testowanie algorytmu

Nadszedł czas na napisanie testów sprawdzających implementację algorytmu sortowania szybkiego (oczywiście UT powstały wcześniej, TDD co nie? ;)). W testach korzystam z standardowych danych testowych (opisanych tutaj).

Kod testujący wygląda następująco:

[TestMethod]
public void SimpleQuickSort()
{
    SimpleQuickSort sort = new SimpleQuickSort();
    int[] test1 = SortData.SimpleExample1Input;
    sort.Sort(test1);
    Assert.IsTrue(Helpers.Equals(SortData.SimpleExample1Output, test1));
 
    int[] test2 = SortData.SimpleExample2Input;
    sort.Sort(test2);
    Assert.IsTrue(Helpers.Equals(SortData.SimpleExample2Output, test2));
}
 
[TestMethod]
public void QuickSort()
{
    QuickSort sort = new QuickSort();
    ComparableInt[] test1 = SortData.Example1Input;
    sort.Sort(test1);
    Assert.IsTrue(Helpers.Equals(SortData.Example1Output, test1));
}

Przyzwyczaiłeś się pewnie już do zielonego koloru testów, tak też jest w tym wypadku. Wszystko działa jak należy.

Podsumowanie

Tym algorytmem zamykam dział algorytmów sortujących (no nie do końca to jest prawda, ale to jeszcze zobaczysz…). Algorytm sortowania szybkiego jest najlepszym z algorytmów przedstawionych przeze mnie, a tym samym nie jest trudny w implementacji. Oczywiście przedstawioną implementację można dodatkowo optymalizować, ta nie jest odporna np. na za głęboką rekurencję. Jednak to pozostawiam jako zadanie dla Ciebie, jak chcesz abym przedstawił takie rozwiązanie to daj mi znać w komentarzu.
Pozdro!

Patryk Bogdański

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *

This site uses Akismet to reduce spam. Learn how your comment data is processed.