BITEDU.PL

Sortowanie szybkie (QuickSort)

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

  1. Wybieramy element główny – nazywamy go pivotem (np. pierwszy element w liście).
  2. Dzielimy tablicę na dwie części:
    • elementy mniejsze lub równe pivotowi,
    • elementy większe od pivota.
  3. Pivot jest już „na swoim miejscu” – nigdzie się nie ruszy.
  4. Rekurencyjnie powtarzamy sortowanie w lewej i prawej części.
  5. 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]

  1. Pivot = 38
    • mniejsze/równe: [27, 3, 9, 10]
    • większe: [43, 82]
      → [27, 3, 9, 10] + [38] + [43, 82]
  2. Sortujemy lewą część [27, 3, 9, 10]
    Pivot = 27
    • mniejsze/równe: [3, 9, 10]
    • większe: []
      → [3, 9, 10] + [27]
  3. Sortujemy [3, 9, 10]
    Pivot = 3
    • mniejsze/równe: []
    • większe: [9, 10]
      → [3] + [9, 10]
  4. Sortujemy [9, 10]
    Pivot = 9
    • mniejsze/równe: []
    • większe: [10]
      → [9] + [10]
  5. 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).

  1. Podziel tablicę na lewą i prawą część.
  2. Ustal nową kolejność elementów po tym kroku.
  3. 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:

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