5 marca 2021

Kurs programowania - Algorytmy sortowania

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 bąbelkowe

Sortowanie bąbelkowe jest jednym z najprostszych rodzajów sortowania.

Sortowanie bąbelkowe - Bubble Sort

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, super! 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. 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");

    }
}

 

sortowanie bąbelkowe przykład

W sortowaniu bąbelkowym porównujemy kolejne pary elementów w tablicy.

Sortowanie przez wstawianie - Insertion Sort

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;
    }
}

 

sortowanie przez wstawianie

Algorytm sortowania przez wstawianie można porównać do układania kart z talii.

Sortowanie przez wybieranie - Selection Sort

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

Sortowanie przez wybieranie polega na selekcji najmniejszych elementów i przekładaniu ich na początek.

Sortowanie szybkie - Quick Sort

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

Sortowanie szybkie dzieli tablicę na dwa niezależne od siebie podzbiory, a następnie scala wynik.

Sortowanie przez scalanie - Merge Sort

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 tablice takiej samej długości, odpowiednio ustawiając w niej elementy w sposób rosnący. 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);
}

 

sortowanie przez scalanie

W odróżnieniu od scalania szybkiego, w sortowaniu przez scalanie brakuje funkcji Partition, która porządkuje dane.

Sortowanie kopcowe - Heap Sort

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:

sortowanie przez kompcowanie

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:

sortowanie przez kopcowanie

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(); //tworzenie kopca
    int n = table.Length-1;
    while(n>0)
    {
        int tmp = table[0];
        table[0] = table[n];
        table[n--] = tmp;
        DownHeap(0, n);

    }
}

 

sortowanie przez kopcowanie

Sortowanie kopcowe, czyli za pomocą kopca przypominającego wyglądem drzewo binarne, jest niezbyt popularne, jednak warto się z nim zapoznać.

Najnowsze wpisy

Jak pomóc dziecku w nauce programowania? Poradnik dla rodziców

Przeczytaj >>

Dlaczego warto uczyć dzieci programowania? – jakie umiejętności rozwija programowanie?

Przeczytaj >>

Python a C++

Przeczytaj >>

Algorytm Euklidesa w języku Python

Przeczytaj >>

10 podstawowych funkcji Excela, które trzeba znać

Przeczytaj >>

JESTEŚ AMBITNY?

Dołącz do nas jeszcze dziś i rozwijaj się w swojej ulubionej dziedzinie we współpracy z nauczycielami, którzy są autorami artykułów na naszym blogu!
POZNAJ OFERTĘ KUSÓW
© Ambitni Szkoła Informatyki 011111100101(2) | jesteś niemal gotowy!
crossmenu