Algorytmy sortowania (bąbelkowe, przez wstawianie, szybkie)

Po co się tego uczymy?

Sortowanie to jeden z najczęściej wykonywanych algorytmów w informatyce — listy produktów wg ceny, wyniki wyszukiwania wg trafności, ranking graczy. Podstawa programowa (INF.04.3.4) wymaga znajomości konkretnych algorytmów sortowania, a nie tylko wywołania gotowej metody Array.Sort() — bo na egzaminie trzeba umieć wytłumaczyć i zaimplementować, JAK działają "od środka".

Teoria

Sortowanie bąbelkowe (bubble sort) — najprostsze koncepcyjnie, ale najmniej wydajne (O(n²)). W jednym przebiegu porównujemy sąsiednie pary elementów i zamieniamy miejscami, jeśli są w złej kolejności. Największy element "wypływa" jak bąbelek na koniec tablicy w każdym przebiegu. Powtarzamy przebiegi, aż cała tablica będzie posortowana.

Sortowanie przez wstawianie (insertion sort) — budujemy posortowaną część tablicy od lewej strony, element po elemencie. Każdy nowy element "wstawiamy" we właściwe miejsce w już posortowanej części, przesuwając większe elementy w prawo. Też O(n²), ale w praktyce szybsze od bąbelkowego i bardzo efektywne dla niemal już posortowanych danych.

Sortowanie szybkie (quicksort) — metoda "dziel i zwyciężaj": wybieramy element zwany pivotem, dzielimy resztę tablicy na dwie części (mniejsze od pivota i większe od pivota), po czym rekurencyjnie sortujemy każdą część osobno. W typowym przypadku ma złożoność O(n log n) — znacznie lepszą niż bąbelkowe czy przez wstawianie dla dużych zbiorów danych.

W realnych programach niemal zawsze używa się gotowych, wbudowanych metod (Array.Sort(), List<T>.Sort() w C#) — są one zoptymalizowane lepiej, niż napisalibyśmy to sami. Implementowanie własnych algorytmów sortowania jest ćwiczeniem, które uczy MYŚLENIA algorytmicznego i rozumienia złożoności obliczeniowej, a nie czymś, co robi się w prawdziwym projekcie na co dzień.

Schemat

Sortowanie bąbelkowe — jeden przebieg tablicy [5, 2, 8, 1]:

Porównaj (5,2): 5>2 -> zamiana   [2, 5, 8, 1]
Porównaj (5,8): 5<8 -> bez zmian [2, 5, 8, 1]
Porównaj (8,1): 8>1 -> zamiana   [2, 5, 1, 8]
                                  ^ największy "wypłynął" na koniec jak bąbelek

Powtarzamy przebiegi, aż żadna zamiana nie będzie już potrzebna.

Sortowanie przez wstawianie — budujemy posortowaną część od lewej:

[5 | 2, 8, 1]   posortowana część: [5]
[2, 5 | 8, 1]   wstaw 2 we właściwe miejsce: [2, 5]
[2, 5, 8 | 1]   8 już pasuje na końcu:       [2, 5, 8]
[1, 2, 5, 8]    wstaw 1 na początek:         [1, 2, 5, 8]

Przykład z życia

Sklep internetowy sortujący produkty "od najtańszych", Excel sortujący wiersze wg kolumny, telefon sortujący kontakty alfabetycznie — wszystko to korzysta z algorytmów sortowania. Różnica w wydajności ma znaczenie przy dużych zbiorach: sortowanie miliona rekordów w bazie danych algorytmem O(n²) zajęłoby zauważalnie dłużej niż dobrym algorytmem O(n log n), dlatego bazy danych i biblioteki standardowe języków programowania inwestują w wydajne implementacje.

Kod (C#)

using System;

class Program
{
    // Sortowanie bąbelkowe - O(n^2)
    static void SortowanieBabelkowe(int[] tab)
    {
        for (int przebieg = ; przebieg < tab.Length - 1; przebieg++)
        {
            for (int i = ; i < tab.Length - 1 - przebieg; i++)
            {
                if (tab[i] > tab[i + 1])
                {
                    (tab[i], tab[i + 1]) = (tab[i + 1], tab[i]); // zamiana miejscami
                }
            }
        }
    }

    // Sortowanie przez wstawianie - O(n^2), szybkie dla prawie posortowanych danych
    static void SortowaniePrzezWstawianie(int[] tab)
    {
        for (int i = 1; i < tab.Length; i++)
        {
            int aktualny = tab[i];
            int j = i - 1;

            // Przesuwamy większe elementy w prawo, robiąc miejsce dla "aktualny"
            while (j >=  && tab[j] > aktualny)
            {
                tab[j + 1] = tab[j];
                j--;
            }
            tab[j + 1] = aktualny;
        }
    }

    // Sortowanie szybkie (quicksort) - O(n log n) w typowym przypadku
    static void SortowanieSzybkie(int[] tab, int lewy, int prawy)
    {
        if (lewy >= prawy) return;

        int pivot = tab[prawy];
        int i = lewy - 1;

        for (int j = lewy; j < prawy; j++)
        {
            if (tab[j] < pivot)
            {
                i++;
                (tab[i], tab[j]) = (tab[j], tab[i]);
            }
        }
        (tab[i + 1], tab[prawy]) = (tab[prawy], tab[i + 1]);
        int granica = i + 1;

        SortowanieSzybkie(tab, lewy, granica - 1);   // sortuj lewą część
        SortowanieSzybkie(tab, granica + 1, prawy);  // sortuj prawą część
    }

    static void Main()
    {
        int[] dane1 = { 5, 2, 8, 1, 9, 3 };
        SortowanieBabelkowe(dane1);
        Console.WriteLine("Bąbelkowe: " + string.Join(", ", dane1));

        int[] dane2 = { 5, 2, 8, 1, 9, 3 };
        SortowaniePrzezWstawianie(dane2);
        Console.WriteLine("Przez wstawianie: " + string.Join(", ", dane2));

        int[] dane3 = { 5, 2, 8, 1, 9, 3 };
        SortowanieSzybkie(dane3, , dane3.Length - 1);
        Console.WriteLine("Szybkie: " + string.Join(", ", dane3));
    }
}

Komentarz i wyjaśnienie kodu

Bąbelkowe: zewnętrzna pętla liczy przebiegi, wewnętrzna porównuje sąsiadów i zamienia ich krotką (tab[i], tab[i + 1]) = (tab[i + 1], tab[i]) — to wygodna składnia C# do zamiany dwóch zmiennych miejscami bez zmiennej pomocniczej. Zakres wewnętrznej pętli maleje z każdym przebiegiem (- przebieg), bo końcówka tablicy jest już posortowana.

Przez wstawianie: dla każdego elementu tab[i] pętla while przesuwa w prawo wszystkie elementy z posortowanej części, które są większe od niego, robiąc mu miejsce, po czym wstawia go na zwolnione miejsce.

Szybkie (quicksort): wybiera ostatni element jako pivot, następnie w jednej pętli przesuwa wszystkie elementy mniejsze od pivota na lewą stronę, a na końcu wstawia pivot dokładnie pomiędzy mniejszą a większą część. Potem funkcja wywołuje SAMĄ SIEBIE (rekurencja z lekcji 20!) dla lewej i prawej części osobno — to właśnie znaczy "dziel i zwyciężaj".

Ćwiczenie samodzielne

Dodaj licznik operacji (zamian/porównań) do SortowanieBabelkowe i SortowanieSzybkie, uruchom oba dla tej samej losowej tablicy 20 elementów i porównaj liczby — który algorytm wykonał mniej operacji?

Plac zabaw — wypróbuj online

Poniższy kod wykonuje się od razu w Twojej przeglądarce — nic nie trzeba instalować. Zmień kod i kliknij „Uruchom”.

CSHARP

using System;

class Program
{
    // Sortowanie bąbelkowe - O(n^2)
    static void SortowanieBabelkowe(int[] tab)
    {
        for (int przebieg = 0; przebieg < tab.Length - 1; przebieg++)
        {
            for (int i = 0; i < tab.Length - 1 - przebieg; i++)
            {
                if (tab[i] > tab[i + 1])
                {
                    (tab[i], tab[i + 1]) = (tab[i + 1], tab[i]); // zamiana miejscami
                }
            }
        }
    }

// Sortowanie przez wstawianie - O(n^2), szybkie dla prawie posortowanych danych
    static void SortowaniePrzezWstawianie(int[] tab)
    {
        for (int i = 1; i < tab.Length; i++)
        {
            int aktualny = tab[i];
            int j = i - 1;

// Przesuwamy większe elementy w prawo, robiąc miejsce dla "aktualny"
            while (j >= 0 && tab[j] > aktualny)
            {
                tab[j + 1] = tab[j];
                j--;
            }
            tab[j + 1] = aktualny;
        }
    }

// Sortowanie szybkie (quicksort) - O(n log n) w typowym przypadku
    static void SortowanieSzybkie(int[] tab, int lewy, int prawy)
    {
        if (lewy >= prawy) return;

int pivot = tab[prawy];
        int i = lewy - 1;

for (int j = lewy; j < prawy; j++)
        {
            if (tab[j] < pivot)
            {
                i++;
                (tab[i], tab[j]) = (tab[j], tab[i]);
            }
        }
        (tab[i + 1], tab[prawy]) = (tab[prawy], tab[i + 1]);
        int granica = i + 1;

SortowanieSzybkie(tab, lewy, granica - 1);   // sortuj lewą część
        SortowanieSzybkie(tab, granica + 1, prawy);  // sortuj prawą część
    }

static void Main()
    {
        int[] dane1 = { 5, 2, 8, 1, 9, 3 };
        SortowanieBabelkowe(dane1);
        Console.WriteLine("Bąbelkowe: " + string.Join(", ", dane1));

int[] dane2 = { 5, 2, 8, 1, 9, 3 };
        SortowaniePrzezWstawianie(dane2);
        Console.WriteLine("Przez wstawianie: " + string.Join(", ", dane2));

int[] dane3 = { 5, 2, 8, 1, 9, 3 };
        SortowanieSzybkie(dane3, 0, dane3.Length - 1);
        Console.WriteLine("Szybkie: " + string.Join(", ", dane3));
    }
}

Zadania do pracy własnej

Zmodyfikuj sortowanie bąbelkowe, żeby sortowało malejąco zamiast rosnąco (zmień jeden znak porównania).
Dodaj do sortowania bąbelkowego "flagę optymalizacji": jeśli w danym przebiegu nie było ŻADNEJ zamiany, tablica jest już posortowana i można zakończyć wcześniej, nie czekając na wszystkie przebiegi.
Napisz funkcję SortowanieScalajace (merge sort) — kolejny algorytm typu "dziel i zwyciężaj", tym razem dzielący tablicę na połowy, sortujący każdą osobno (rekurencyjnie), a potem scalający dwie posortowane połówki w jedną. Porównaj jego wydajność z quicksortem dla dużej tablicy (100 000 elementów).

Typowe błędy

Błąd "o jeden" w zakresie pętli — najczęstszy błąd w sortowaniu bąbelkowym: porównywanie tab[i] z tab[i+1] przy i idącym aż do tab.Length spowoduje IndexOutOfRangeException, bo tab[i+1] wyjdzie poza tablicę. Zawsze pętla musi kończyć się na Length - 1.

Pisanie własnego sortowania w kodzie produkcyjnym — w prawdziwym projekcie prawie zawsze używa się Array.Sort() lub List<T>.Sort(), które są szybsze i przetestowane. Własne implementacje piszemy do nauki, nie do użytku.

Nieprawidłowy wybór pivota w quicksorcie — jeśli dane są już posortowane i zawsze wybieramy ostatni element jako pivot, quicksort degraduje się do O(n²) zamiast O(n log n). To subtelny, ale ważny szczegół.

Nawiązanie do egzaminu zawodowego

To realizacja INF.04.3.4 — "stosuje algorytmy sortowania i wyszukiwania: bąbelkowe, zachłanne, przez wstawianie, szybkie, dziel i zwyciężaj". Zrozumienie złożoności z lekcji 24 pozwala świadomie ocenić, dlaczego quicksort jest zwykle lepszym wyborem od sortowania bąbelkowego dla dużych zbiorów danych.