W tym wpisie postaram się przybliżyć Ci jak działa sortowanie, bardziej popularne metody sortowania oraz ich złożoności i dlaczego niektóre algorytmy działają tylko w teorii.
Sortowanie danych jest bardzo częstym problemem w różnych dziedzinach informatyki.
Jednym z najprostszych i pokazywanych uczniom na samym początku nauki programowania algorytmem sortującym jest Bubble Sort, czyli sortowanie bąbelkowe. Polega ono na porównywaniu kolejnych par elementów w tablicy. Jeśli element na i-tej pozycji jest większy od tego na pozycji i+1 to następuje ich zamiana. Zobaczmy, że kiedy przejdziemy jeden raz przez wszystkie takie pary, to największy element powinien ustawić się na końcu tablicy. Zatem mamy już posortowany 1 z n elementów. Teraz robimy dokładnie to samo n-1 razy, gdzie przy każdym przejściu wszystkich par kolejny element ustawia się prawidłowo na końcu tablicy nieposortowanej części tablicy. W taki sposób będzie prezentował się Bubble Sort zapisany w C#:
void BubbleSort(int[] table)
{
int x = table.Length;
for(int i=0; i<x; i++)
{
for(int j=0; j<x-1; j++)
{
// Console.WriteLine(j);
if(table[j]>table[j+1])
{
(table[j], table[j + 1]) = (table[j + 1], table[j]);
}
}
Console.WriteLine(i.ToString() + " to go");
}
}
W sortowaniu bąbelkowym porównujemy kolejne pary elementów w tablicy.
Następnie weźmy pod lupę Insertion Sort’a, czyli Sortowanie przez wstawianie. Algorytm ten można porównać do układania kart w ręce gracza. Polega on na tym, iż wybieramy kolejny element a następnie ustawiamy go w już posortowanym fragmencie ciągu. Na przykład dla danych: [5, 3, 1, 7, 2, 12] na początku ustawi nam trójkę na początek tablicy, ponieważ jest mniejsza od piątki. Następnie element o wartości 1 zostanie ustawiony na początek. Dalej 7 pozostanie nienaruszona, ponieważ jest większa od obecnego ostatniego elementu ciągu, którym jest piątka. Następnie dwójka zostanie ustawiona między 1 i 3, a na koniec 12 zostanie nietknięta. Teraz zaprezentujmy algorytm zapisany w C#:
void InsertionSort(int[] table)
{
int pom, j;
for(int i=1; i<table.Length; i++)
{
pom = table[i];
j = i - 1;
while (j >= 0 && table[j] > pom)
table[j + 1] = table[j--];
table[j + 1] = pom;
}
}
Algorytm sortowania przez wstawianie można porównać do układania kart z talii.
Selection Sort, czyli sortowanie przez wybieranie będzie tym razem czymś łatwiejszym do zilustrowania w porównaniu z Insertion Sortem. Nazwa wybierania wzięła się z tego, że dla tego algorytmu za każdym razem wybieramy kolejne najmniejsze elementy tablicy i przekładamy je na jej przód. Tak wygląda Selection Sort w C#:
void SelectionSort(int []table)
{
for(int i=0; i<table.Length-1; i++)
{
int min = i;
for(int j=i+1; j<table.Length; j++)
{
if (table[j] < table[min])
min = j;
}
int tmp = table[i];
table[i] = table[min];
table[min] = tmp;
}
}
Sortowanie przez wybieranie polega na selekcji najmniejszych elementów i przekładaniu ich na początek.
Quick Sort, czyli sortowanie szybkie, został opracowany w 1960 roku i jest najważniejszym oraz najczęściej stosowanym algorytmem sortującym. Dla przykładu, w języku C funkcja wbudowana Sort() wykonuje sortowanie danych za pomocą Quick Sort’a. Quick Sort opiera się on na metodzie divide and conquer, czyli dziel i zwyciężaj. Polega on na podzieleniu tablicy na 2 mniejsze podzbiory, wykonania sortowania każdej z nich niezależnie od drugiej, a następnie połączenia wyniku w całość. Kluczem do tego algorytmu jest funkcja Partition, która wybiera dowolny element (pivot), a następnie ustawia wszystkie elementy mniejsze od niego na lewo, zaś większe lub równe na prawo w tablicy. Dalej należy nowo otrzymaną tablicę podzielić na dwie części i tak aż do otrzymania tablicy jednoelementowej. Zatem otrzymujemy funkcję rekurencyjną, prezentującą się w następujący sposób:
void QuickSort(int l, int r, int[] table)
{
int j = Partition(l, r);
if (j - 1 > l) QuickSort(l, j - 1, table);
if (j + 1 < r) QuickSort(j + 1, r, table);
}
Sortowanie szybkie dzieli tablicę na dwa niezależne od siebie podzbiory, a następnie scala wynik.
Kolejnym rekurencyjnym sortowaniem będzie Merge Sort, czyli sortowanie przez scalanie. Polega ono tak jak Quick Sort na podziale tablic na kolejne pomniejsze tablice, jednak w tym przypadku nie mamy żadnej funkcji Partition porządkującej dane tak jak wcześniej. W Merge Sorcie mamy funkcje scalającą Merge, która łączy nam dwie dowolne posortowane tablice tak, że wynik również jest posortowaną tablicą. Przypadek bazowy sortowania przez scalanie to tablica z jednym elementem - jest ona zawsze posortowana. Algorytm Merge Sort:
void MergeSort(int l, int r, int[] table)
{
if (l == r) return;
int mid = (l + r) / 2;
MergeSort(l, mid, table);
MergeSort(mid + 1, r, table);
Merge(table, l, mid, r);
}
W odróżnieniu od scalania szybkiego, w sortowaniu przez scalanie brakuje funkcji Partition, która porządkuje dane - zamiast tego rekurencyjnie dzielimy tablice nie zmieniając kolejności elementów, a następnie je scalamy.
Ostatnim algorytmem jakim sobie omówimy, będzie Heap Sort, czyli sortowanie kopcowe. Nie jest on popularnym algorytmem w kursach programowania, lecz mimo wszystko warto się z nim zapoznać. Jednak nim przejdziemy do opisu zacznijmy sobie od wyjaśnienia pojęcia kopiec. Kopiec to struktura danych przypominająca z wyglądu drzewo binarne. Każdy węzeł posiada element oraz następniki (1 lub 2). Elementy na ostatnim poziomie, które nie mają żadnego następnika nazywamy liśćmi. Dodatkowo kopiec jest zapełniany od lewej strony, dlatego wszystkie liście będą się znajdować na ostatnim (lub ewentualnie przedostatnim) poziomie. Jeszcze jedna własność kopca: dla każdego węzła jego następniki mają wartość nie większą od niego. To oznacza tyle, że element o największej wartości zawsze będzie się znajdował w korzeniu (na szczycie kopca). Tak wygląda przykładowy kopiec o wysokości 4 i 9 elementach:
Przykładowy kopiec o 9 elementach.
Teraz rozważmy sobie jeszcze kwestię usuwania największego elementu z kopca. Jak już wiemy jest on zawsze w korzeniu, więc nie musimy tracić czasu na szukanie. Jednak co się dzieje po usunięciu, przecież nie możemy tak po prostu pozbyć się węzła, ponieważ rozbijemy nasz kopiec. Rozwiązaniem jest zatem wstawienie ostatniego elementu (liścia na ostatnim poziomie najbardziej z prawej strony) do korzenia w miejsce elementu usuwanego. Ale zaraz, przecież dla naszego przykładu z powyższego kopca będziemy mieli na szczycie 7, której daleko do bycia największą wartością i tym samym zaburzymy strukturę kopca. Co należy zatem teraz zrobić? Odpowiedź jest całkiem prosta, musimy poprawić ten kopiec i przesunąć w dół nasz korzeń. W tym celu po prostu przechodzimy tą naszą siódemką w dół, zamieniając ją ciągle z następnikiem o większej wartości. Tym sposobem po jednym usunięciu maksymalnego elementu z kopca otrzymamy coś takiego:
Kopiec po usunięciu maksymalnego elementu.
Teraz z tą wiedzą możemy już spokojnie stworzyć sortowanie przy użyciu kopca. Polega ono na tym, iż tworzymy z naszej tablicy kopiec, a następnie jego korzeń usuwamy, wstawiając wartość w nim zapisaną na początek tablicy i powtarzamy te czynności do momentu, gdy kopiec będzie pusty. Kod Heap Sort’a prezentuje się mniej więcej w poniższy sposób:
void HeapSort(int[] table)
{
CreateHeap(table); //tworzenie kopca z tablicy table
int n = table.Length-1;
while(n>0)
{
int tmp = table[0];
table[0] = table[n];
table[n--] = tmp;
DownHeap(0, n); //naprawienie kopca
}
}
Sortowanie kopcowe, czyli za pomocą struktury danych kopca, jest niezbyt popularne, jednak warto się z nim zapoznać.
