INF.04 · C# · lekcja 26

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

Obserwuj zmiany porządku danych

  • Zrozum
  • Sprawdź
  • Napisz sam

Po tej lekcji: obserwuj zmiany porządku danych

Dzisiaj zrobisz konkretną rzecz

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".

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.

Sprawdź w działaniu

Obserwuj zmiany porządku danych

Najpierw przewidź wynik. Zmień dane w modelu i porównaj efekt. Spróbuj także przypadku granicznego, a nie tylko pierwszego poprawnego przykładu.

Ta interakcja wymaga włączonego JavaScriptu.

Model pokazuje wybraną zasadę. Nie uruchamia ani nie ocenia wklejonego kodu C#.

1. Przygotuj i uruchom własny projekt

2. Najpierw mały przykład

Wykonaj tę próbę przed dłuższym rozwiązaniem. Wewnętrzna pętla porównuje sąsiadów. Zamiana krotką podmienia dwa elementy bez utraty wartości. Po przebiegu największa pozostała liczba stoi na końcu, więc skracamy następny przebieg.

Program.cscsharp
int[] liczby = { 4, 1, 3, 2 };
for (int koniec = liczby.Length - 1; koniec > 0; koniec--)
    for (int i = 0; i < koniec; i++)
        if (liczby[i] > liczby[i + 1])
            (liczby[i], liczby[i + 1]) = (liczby[i + 1], liczby[i]);
Console.WriteLine(string.Join(", ", liczby));
Wynik
1, 2, 3, 4
  1. Co sprawdzić? Zmień jedną wartość i przed uruchomieniem zapisz przewidywany rezultat. Porównaj go z opisem wyniku; przy błędzie wróć do konkretnej instrukcji.

Jak to działa — 1

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.

Jak to działa — 2

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ń.

3. Pełny przykład — czytaj od Main

Teraz zastąp Program.cs tym programem. Zanim uruchomisz, znajdź dane wejściowe, operację i miejsce prezentacji wyniku. W tym wariancie zachowujemy jawny Main. Nie wklejaj kilku pełnych programów do jednego pliku.

Program.cs — osobne uruchomieniecsharp
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));
    }
}
  1. Prześledź kod 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".

Sprawdź, zanim przepiszesz cały program

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ół.

Ćwiczenie z pomocą · samodzielna praca

4. Teraz Twoja zmiana

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?

Oczekiwany rezultat
Spełnij warunki polecenia. Zapisz wejście, otrzymany wynik i wyjaśnij, która część kodu za niego odpowiada.
Potrzebujesz pomocy? Rozwiązuj krok po kroku.
Krok 1 — pokaż podpowiedź

Wróć do podstawowej formy oraz objaśnienia: Wewnętrzna pętla porównuje sąsiadów. Zamiana krotką podmienia dwa elementy bez utraty wartości. Po przebiegu największa pozostała liczba stoi na końcu, więc skracamy następny przebieg.

Krok 2 — pokaż podpowiedź

Zmień tylko część potrzebną do polecenia. Zachowaj działającą wersję przed zmianą i uruchamiaj po każdym małym etapie.

Krok 3 — pokaż podpowiedź

Sprawdź przypadek zwykły i graniczny; porównaj z regułą: 1, 2, 3, 4

Otwórz tylko tyle podpowiedzi, ile potrzebujesz. Po każdym kroku wróć do zadania i sprawdź wynik.

5. Sprawdź rozumienie, nie tylko uruchomienie

Dalej na swoim koncie

Rozgrzewki, quiz i zadania są w biurku ucznia.

Teoria jest otwarta dla wszystkich. Żeby rozwiązywać zadania, zapisywać szkice i widzieć swój postęp, zaloguj się.

Zaloguj się →
Źródła i dalsza nauka