Złożoność obliczeniowa i sortowanie szybkie

Czego się dziś nauczysz

Przygotowanie: lekcje 01–27. Przewidywany czas: 45–90 minut z zadaniami. Przykłady wymagają .NET 8 lub nowszego, z włączonymi ImplicitUsings i Nullable.

Ile pracy wykonuje algorytm

Czas działania mierzony stoperem zależy od komputera, od tego, co jeszcze jest uruchomione, i od wersji .NET. Dlatego algorytmy porównujemy inaczej: liczymy operacje w zależności od rozmiaru danych, oznaczanego zwykle literą n.

Weź wyszukiwanie liniowe z poprzedniej lekcji. Dla tablicy stu elementów w najgorszym przypadku wykonuje sto porównań, dla tysiąca — tysiąc. Liczba porównań rośnie tak samo szybko jak n. Mówimy, że algorytm ma złożoność O(n).

Wyszukiwanie binarne po każdym kroku odrzuca połowę zakresu: 1000 → 500 → 250 → … → 1. To około dziesięć kroków dla tysiąca elementów i dwadzieścia dla miliona. Złożoność O(log n).

Dziel i zwyciężaj: sortowanie przez scalanie

Pomysł jest rekurencyjny: podziel tablicę na pół, posortuj każdą połowę (tą samą metodą!), a potem scal dwie posortowane części w jedną. Scalanie znasz z zadania z lekcji 24 bierzemy zawsze mniejszy z dwóch pierwszych elementów.

static void SortujScalaniem(int[] t, int od, int doo)
{
    if (od >= doo)
    {
        return;                       // zero albo jeden element - juz posortowane
    }

    int srodek = (od + doo) / 2;

    SortujScalaniem(t, od, srodek);       // lewa polowa
    SortujScalaniem(t, srodek + 1, doo);  // prawa polowa
    Scal(t, od, srodek, doo);             // zlaczenie dwoch posortowanych czesci
}

static void Scal(int[] t, int od, int srodek, int doo)
{
    int[] pomoc = new int[doo - od + 1];
    int i = od, j = srodek + 1, k = 0;

    while (i <= srodek && j <= doo)
    {
        pomoc[k++] = (t[i] <= t[j]) ? t[i++] : t[j++];
    }
    while (i <= srodek) pomoc[k++] = t[i++];
    while (j <= doo)    pomoc[k++] = t[j++];

    for (int x = 0; x < pomoc.Length; x++)
    {
        t[od + x] = pomoc[x];
    }
}

Podziałów jest około log₂ n, a na każdym poziomie scalamy łącznie n elementów — stąd O(n log n) w każdym przypadku, także najgorszym. Ceną jest pamięć: potrzebna jest tablica pomocnicza.

Sortowanie szybkie (quicksort)

Tu też dzielimy zadanie, ale inaczej: wybieramy jeden element — oś (ang. pivot) — i przestawiamy tablicę tak, żeby po lewej były wartości mniejsze, a po prawej większe. Oś trafia wtedy na swoje docelowe miejsce. Potem to samo robimy z lewą i prawą częścią.

static void SortujSzybko(int[] t, int od, int doo)
{
    if (od >= doo) return;

    int os = t[doo];        // os: ostatni element zakresu
    int granica = od;       // pierwsze miejsce dla wartosci mniejszej od osi

    for (int i = od; i < doo; i++)
    {
        if (t[i] < os)
        {
            (t[i], t[granica]) = (t[granica], t[i]);   // zamiana
            granica++;
        }
    }

    (t[doo], t[granica]) = (t[granica], t[doo]);       // os na swoje miejsce

    SortujSzybko(t, od, granica - 1);
    SortujSzybko(t, granica + 1, doo);
}

Sortowanie przez wstawianie

Trzeci klasyczny algorytm kwadratowy działa tak, jak porządkuje się karty w ręku: bierzesz kolejną kartę i wsuwasz ją na właściwe miejsce wśród już ułożonych.

static void SortujPrzezWstawianie(int[] t)
{
    for (int i = 1; i < t.Length; i++)
    {
        int wstawiany = t[i];
        int j = i - 1;

        // przesuwamy w prawo wszystko, co wieksze od wstawianego
        while (j >= 0 && t[j] > wstawiany)
        {
            t[j + 1] = t[j];
            j--;
        }

        t[j + 1] = wstawiany;
    }
}

Złożoność w najgorszym przypadku to O(n²), ale ten algorytm ma dwie cechy, które czynią go użytecznym mimo tego:

• Na danych prawie posortowanych działa niemal liniowo — pętla wewnętrzna prawie nic nie robi. Sortowanie przez wybór wykona tyle samo porównań zawsze.
• Jest stabilny, bo warunek t[j] > wstawiany nie przesuwa elementów równych.

Dwie rodziny algorytmów, o które pyta egzamin

Poza sortowaniem warto znać dwa pojęcia z projektowania algorytmów:

Przykład: porównanie na tych samych danych

Program losuje dane z ustalonym ziarnem, żeby każdy algorytm dostał identyczną tablicę, i liczy porównania oraz czas.

using System.Diagnostics;

class Program
{
    static long porownania;

    static int[] Losowa(int ile)
    {
        Random los = new Random(42);
        int[] t = new int[ile];
        for (int i = 0; i < ile; i++) t[i] = los.Next(0, 100000);
        return t;
    }

    static void Babelkowe(int[] t)
    {
        for (int i = 0; i < t.Length - 1; i++)
        {
            bool zamiana = false;
            for (int j = 0; j < t.Length - 1 - i; j++)
            {
                porownania++;
                if (t[j] > t[j + 1])
                {
                    (t[j], t[j + 1]) = (t[j + 1], t[j]);
                    zamiana = true;
                }
            }
            if (!zamiana) break;
        }
    }

    static void Main()
    {
        int[] dane = Losowa(20000);
        int[] kopia = (int[])dane.Clone();

        porownania = 0;
        Stopwatch zegar = Stopwatch.StartNew();
        Babelkowe(dane);
        zegar.Stop();
        Console.WriteLine($"babelkowe : {porownania,12:N0} porownan, {zegar.ElapsedMilliseconds} ms");

        zegar.Restart();
        Array.Sort(kopia);
        zegar.Stop();
        Console.WriteLine($"Array.Sort: {zegar.ElapsedMilliseconds} ms (porownan nie liczymy)");

        Console.WriteLine($"Wyniki zgodne: {dane.SequenceEqual(kopia)}");
    }
}

babelkowe :  199 990 000 porownan, 640 ms
Array.Sort: 1 ms (porownan nie liczymy)
Wyniki zgodne: True

Co dzieje się po kolei

• Liczba porównań jest bliska n²/2 — dla 20 000 elementów to około 200 milionów. Zwiększenie tablicy dwukrotnie da czterokrotnie więcej pracy.
• Stopwatch mierzy czas rzeczywisty. Wynik w milisekundach zależy od komputera — porównuj rząd wielkości, nie konkretną liczbę.
• SequenceEqual potwierdza, że oba sposoby dały ten sam wynik. Bez takiego sprawdzenia szybki algorytm z błędem wygląda po prostu na jeszcze szybszy.
• Clone daje kopię tablicy; bez niej drugi algorytm dostałby dane już posortowane i pomiar byłby bez sensu.

Użyte w tej lekcji elementy

Na co uważać

Zadania

Co trzeba zapamiętać

• Złożoność opisuje tempo wzrostu liczby operacji, a nie czas w sekundach.
• O(1), O(log n), O(n), O(n log n) i O(n²) wystarczą do opisania wszystkich algorytmów z tego kursu.
• Sortowanie przez scalanie ma O(n log n) także w najgorszym przypadku, ale potrzebuje dodatkowej pamięci.
• Sortowanie szybkie jest zwykle najszybsze, lecz przy złym wyborze osi schodzi do O(n²).
• Sortowanie stabilne zachowuje kolejność elementów o równych kluczach — bywa to wymaganie, a nie szczegół.
• Pomiar czasu ma sens tylko na identycznych danych i po rozgrzewce; do produkcji i tak używa się Array.Sort.

Dokumentacja: Microsoft Learn — temat tej lekcji.