Wprowadzenie do algorytmu dziel i zwyciężaj

1. Wstęp

Wyobraź sobie, że masz nieposortowaną listę liczb i chcesz je ułożyć rosnąco.
Możesz to zrobić powoli (np. sortowanie bąbelkowe), ale jest sposób dużo szybszy – sortowanie szybkie (QuickSort).

To algorytm, który bazuje na zasadzie dziel i zwyciężaj: zamiast układać całość naraz, dzielimy problem na mniejsze kawałki, a potem składamy wynik.

2. Idea QuickSort

Wybieramy element główny – nazywamy go pivotem (np. pierwszy element w liście).
Dzielimy tablicę na dwie części:
- elementy mniejsze lub równe pivotowi,
- elementy większe od pivota.
Pivot jest już „na swoim miejscu” – nigdzie się nie ruszy.
Rekurencyjnie powtarzamy sortowanie w lewej i prawej części.
Składamy wynik: [mniejsze] + [pivot] + [większe].

3. Przykład z życia

Masz klasę uczniów i chcesz ustawić ich według wzrostu.

Wybierasz jednego ucznia jako pivot.
Mówisz: „wszyscy niżsi ustawcie się po lewej, wszyscy wyżsi po prawej”.
Pivot stoi już we właściwym miejscu.
Teraz robisz to samo w grupie „niższych” i w grupie „wyższych”.
Powtarzasz, aż wszyscy będą w kolejności.

4. QuickSort krok po kroku

Weźmy tablicę:
[38, 27, 43, 3, 9, 82, 10]

Pivot = 38
- mniejsze/równe: [27, 3, 9, 10]
- większe: [43, 82]
  → [27, 3, 9, 10] + [38] + [43, 82]
Sortujemy lewą część [27, 3, 9, 10]
Pivot = 27
- mniejsze/równe: [3, 9, 10]
- większe: []
  → [3, 9, 10] + [27]
Sortujemy [3, 9, 10]
Pivot = 3
- mniejsze/równe: []
- większe: [9, 10]
  → [3] + [9, 10]
Sortujemy [9, 10]
Pivot = 9
- mniejsze/równe: []
- większe: [10]
  → [9] + [10]
Prawa część [43, 82]
Pivot = 43
- mniejsze/równe: []
- większe: [82]
  → [43] + [82]

Składamy wszystko:
[3, 9, 10, 27] + [38] + [43, 82]
→ [3, 9, 10, 27, 38, 43, 82]

5. Kod w Pythonie (wersja dla ucznia – prosta)

def quick_sort(tablica):
    # Jeśli tablica ma 1 lub 0 elementów, jest już posortowana
    if len(tablica) <= 1:
        return tablica
    
    # Wybieramy pierwszy element jako pivot
    pivot = tablica[0]

    # Dzielimy elementy na dwie grupy:
    mniejsze = [x for x in tablica[1:] if x <= pivot]  # wszystkie <= pivot
    wieksze  = [x for x in tablica[1:] if x > pivot]   # wszystkie > pivot

    # Sortujemy obie grupy i składamy wynik
    return quick_sort(mniejsze) + [pivot] + quick_sort(wieksze)

# Przykład działania
tablica = [38, 27, 43, 3, 9, 82, 10]
print("Przed:", tablica)
print("Po   :", quick_sort(tablica))

Wyjaśnienie w komentarzach

if len(tablica) <= 1: – jeśli lista ma 0 lub 1 element, to już jest posortowana.
pivot = tablica[0] – wybieramy pierwszy element jako punkt odniesienia.
mniejsze = [...] – wszystkie elementy mniejsze lub równe pivotowi.
wieksze = [...] – wszystkie elementy większe od pivota.
Funkcja rekurencyjnie wywołuje sama siebie, aż zostaną pojedyncze liczby.

6. Co trzeba wiedzieć na poziomie matury?

QuickSort to algorytm dziel i zwyciężaj.
Działa średnio w czasie O(n log n), ale w najgorszym przypadku (źle dobrane pivoty) spada do O(n²).
Potrzebuje mało pamięci – działa „w miejscu” w wersji bardziej zaawansowanej.
Pivot można wybierać różnie (pierwszy, ostatni, losowy, median-of-three).
Nie jest stabilny (czyli nie zachowuje kolejności elementów równych).

7. Podsumowanie

QuickSort to szybki i sprytny sposób sortowania.
Najpierw wybieramy pivot, potem dzielimy tablicę na dwie części i sortujemy je osobno.
Na koniec składamy wynik.

Pamiętaj:

Bąbelkowe – proste, ale wolne.
MergeSort – zawsze O(n log n), ale potrzebuje dodatkowej pamięci.
QuickSort – zwykle najszybszy w praktyce, ale ma ryzyko O(n²).

Ćwiczenia – Sortowanie szybkie (QuickSort)

Ćwiczenie 1 – Podział tablicy

Masz tablicę:
[12, 5, 7, 20, 15]
Pivot = 12.

Podziel tablicę na dwie części:

mniejsze lub równe pivotowi,
większe od pivota.

Zapisz wynik:

Lewa część = …
Prawa część = …

Ćwiczenie 2 – Jedno pełne wywołanie

Tablica: [30, 25, 40, 10, 35]
Pivot = pierwszy element (30).

Podziel tablicę na lewą i prawą część.
Ustal nową kolejność elementów po tym kroku.
Zapisz wynik.

Ćwiczenie 3 – QuickSort krok po kroku

Posortuj tablicę [9, 2, 7, 1] za pomocą QuickSort.
Przyjmuj zawsze pierwszy element jako pivot.

Dla każdego kroku wypisz:

Pivot,
Lewa część,
Prawa część.

Na końcu podaj wynik posortowany.

Ćwiczenie 4 – Analiza złożoności

Odpowiedz krótko na pytania:

Jaka jest średnia złożoność QuickSort?
Jaka jest złożoność w najgorszym przypadku?
Co to znaczy, że algorytm jest „rekurencyjny”?
Dlaczego wybór pivota ma znaczenie?