Sortowanie szybkie (Quick Sort)

1. Idea algorytmu

Quick Sort to jeden z najszybszych algorytmów sortowania w praktyce. Używa strategii "dziel i zwyciężaj":

  1. Wybierz pivot (element odniesienia)
  2. Partycjonuj: Podziel listę na dwie części:
  3. Elementy mniejsze od pivota (po lewej)
  4. Elementy większe od pivota (po prawej)
  5. Rekurencyjnie posortuj obie części

Wizualizacja:

[38, 27, 43, 3, 9, 82, 10]
          ↑ pivot = 43

Partycjonowanie:
[38, 27, 3, 9, 10] | 43 | [82]
      mniejsze          większe

Rekurencyjnie sortuj obie strony:
[3, 9, 10, 27, 38] | 43 | [82]

Wynik: [3, 9, 10, 27, 38, 43, 82]

2. Implementacja podstawowa (Lomuto partition)

Uwaga: Ta wersja jest prosta, ale używa O(n) dodatkowej pamięci.

3. Implementacja in-place (efektywniejsza)

4. Wizualizacja partycjonowania

Przykład: partition([38, 27, 43, 3, 9, 82, 10], 0, 6)

arr = [38, 27, 43, 3, 9, 82, 10]
pivot = 10 (ostatni element)
i = -1

j=0: arr[0]=38 > 10 → NIC
     [38, 27, 43, 3, 9, 82, 10], i=-1

j=1: arr[1]=27 > 10 → NIC
     [38, 27, 43, 3, 9, 82, 10], i=-1

j=2: arr[2]=43 > 10 → NIC
     [38, 27, 43, 3, 9, 82, 10], i=-1

j=3: arr[3]=3 <= 10 → i++, ZAMIANA arr[0] ↔ arr[3]
     [3, 27, 43, 38, 9, 82, 10], i=0

j=4: arr[4]=9 <= 10 → i++, ZAMIANA arr[1] ↔ arr[4]
     [3, 9, 43, 38, 27, 82, 10], i=1

j=5: arr[5]=82 > 10 → NIC
     [3, 9, 43, 38, 27, 82, 10], i=1

Koniec: Umieść pivot na miejscu i+1
     [3, 9, 10, 38, 27, 82, 43]
            ↑ pivot na indeksie 2

Zwróć: 2 (indeks pivota)

Po partycjonowaniu: Wszystko po lewej <= 10, wszystko po prawej > 10.

5. Wizualizacja z debugiem

6. Złożoność czasowa

Najlepszy i średni przypadek: O(n log n) ✅

Gdy pivot dzieli listę mniej więcej na pół:

Wysokość drzewa rekurencji ≈ log(n)
Każdy poziom przetwarza n elementów
Razem: O(n log n)

Najgorszy przypadek: O(n²) ❌

Gdy pivot jest zawsze najmniejszy lub największy (lista już posortowana!):

Rozwiązanie: Losowy wybór pivota lub mediana z trzech.

7. Optymalizacja: Losowy pivot

Zalety: Średnio O(n log n) nawet dla posortowanych danych.

8. Optymalizacja: Median-of-three

Zamiast losowego – wybierz medianę z pierwszego, środkowego i ostatniego:

9. Hoare partition (alternatywny schemat)

Hoare partition to oryginalny schemat partycjonowania (szybszy niż Lomuto):

Zalety Hoare: - Mniej zamian niż Lomuto - Szybszy w praktyce

10. Złożoność pamięciowa

Standardowy (in-place): O(log n)

Najgorszy przypadek: O(n)

Gdy partycjonowanie zawsze niezrównoważone (np. już posortowane).

Optymalizacja: Tail recursion optimization (nie w Pythonie).

11. Stabilność: NIE ❌

Quick sort nie jest stabilny – może zmienić kolejność równych elementów.

Przykład:

Dlaczego? Zamiany na długim dystansie niszczą stabilność.

12. Optymalizacja: Hybrydowe podejście (Introsort)

Dla małych partycji (<10-20) – użyj insertion sort:

Zalety: - Szybsze dla małych partycji (niski overhead insertion sort) - Używane w C++ std::sort (Introsort)

13. Quick Select – znajdowanie k-tego najmniejszego

Quick sort można użyć do znajdowania k-tego elementu w O(n) średnio!

Złożoność: O(n) średnio, O(n²) najgorsza.

14. Benchmark

15. Podsumowanie

Quick Sort:

  • Złożoność czasowa:
  • Najlepszy: O(n log n)
  • Średni: O(n log n) ← Najszybszy w praktyce!
  • Najgorszy: O(n²) (rzadko z losowym pivotem)
  • Złożoność pamięciowa: O(log n) (stos wywołań)
  • Stabilny: NIE ❌
  • In-place: TAK ✅

Zalety: - Najszybszy średnio ze wszystkich algorytmów sortowania - In-place (O(log n) pamięci) - Cache-friendly (dobra lokalność danych) - Prosty do zaimplementowania - Parallelizable (łatwy do zrównoleglenia)

Wady: - O(n²) w najgorszym przypadku (bez optymalizacji) - Niestabilny - Wymaga dobrego wyboru pivota

Optymalizacje: 1. Losowy pivot – unikaj O(n²) 2. Median-of-three – lepszy pivot 3. Insertion sort dla małych partycji 4. Hoare partition – mniej zamian 5. Tail recursion – oszczędność stosu (nie w Pythonie)

vs Merge Sort: - Quick: szybszy średnio, Merge: gwarantowane O(n log n) - Quick: niestabilny, Merge: stabilny - Quick: O(log n) pamięci, Merge: O(n) pamięci - Quick: in-place ✅

vs Heap Sort: - Quick: szybszy w praktyce - Quick: O(log n) pamięci, Heap: O(1) pamięci - Heap: gwarantowane O(n log n)

Kiedy używać:

✅ Ogólne sortowanie – najszybszy średnio ✅ Gdy wydajność krytyczna (duże dane) ✅ Gdy pamięć ograniczona (in-place) ✅ Quick Select – znajdowanie k-tego elementu

❌ Gdy gwarantowana wydajność wymagana (użyj merge/heap sort) ❌ Gdy stabilność wymagana (użyj merge sort)

Zastosowania w praktyce:

  1. C++ std::sort – Introsort (hybrydowy z quick sort)
  2. Unix qsort() – klasyczny quick sort
  3. Bazy danych – sortowanie w pamięci
  4. Quick Select – mediana, percentyle

Co dalej warto poznać:

  • Heap Sort (gwarantowane O(n log n), in-place)
  • Introsort (hybrydowy: quick + heap + insertion)
  • Dual-pivot Quick Sort (Java 7+)
  • Parallel Quick Sort
Wróć do spisu lekcji