Sortowanie szybkie

🎯 Po co Ci to?

Skoro scalanie jest optymalne — po co komu jeszcze jedno sortowanie? Bo w 1959 roku Tony Hoare (26-letni stażysta pracujący nad tłumaczeniem maszynowym w Moskwie!) wymyślił algorytm, który tę samą klasę $n \log n$ osiąga bez dodatkowej pamięci, mniejszą stałą i tak elegancko, że nazwano go po prostu „szybkim". Quicksort to prawdopodobnie najczęściej wykonywany algorytm w historii komputerów — i zarazem przewrotna lekcja: jego najgorszy przypadek jest kwadratowy, a mimo to świat mu ufa. Zrozumieć dlaczego — to zrozumieć, jak inżynierowie myślą o ryzyku.

✅ Czego się nauczysz

Po tej jednostce potrafisz:

  • wykonać podział względem osi (partycjonowanie) i zapisać quicksort;
  • wyjaśnić, skąd $n \log n$ w typowym przypadku i $n^2$ w pechowym — i co pecha wywołuje;
  • porównać scalanie z szybkim: gwarancje, pamięć, stałe — i dobrać właściwe.

📘 Wyjaśnienie

Pomysł: dziel i zwyciężaj na odwrót. Scalanie tnie mechanicznie na pół i całą pracę wykonuje przy sklejaniu. Quicksort odwraca ciężar: całą pracę wykonuje przy cięciu, a sklejanie ma za darmo. Wybierz element-oś (pivot), a potem podziel listę na mniejsze od osi, oś, większe od osi:

def szybkie(L):
    if len(L) <= 1:
        return L
    os = L[len(L) // 2]                       # oś: element ze środka
    mniejsze = [x for x in L if x < os]
    rowne    = [x for x in L if x == os]
    wieksze  = [x for x in L if x > os]
    return szybkie(mniejsze) + rowne + szybkie(wieksze)

Po podziale każdy element grupy „mniejsze" stoi (docelowo) przed każdym z „większych" — żadne porównanie między grupami nie będzie już nigdy potrzebne. Posortuj grupy osobno (rekurencja!), sklej plusem — gotowe. Ta wersja (czytelna, z budowaniem list) oddaje ideę; wersja przemysłowa robi podział w miejscu, sprytnie zamieniając elementy wokół osi bez żadnej dodatkowej listy — i to jest jej przewaga pamięciowa nad scalaniem. Mechanika podziału w miejscu to wdzięczne (i pouczające) ćwiczenie — w 🛠️ zmierzysz się z jego ideą.

Koszt: loteria osi. Jeśli oś za każdym razem dzieli listę mniej więcej po połowie — drzewo rekurencji wygląda jak drzewo scalania: $\log n$ poziomów, $n$ pracy podziałów na poziom, razem $n \log n$. Ale jeśli oś trafia skrajnie (najmniejszy lub największy element) — podział daje grupy $0$ i $n-1$: drzewo degeneruje się do patyka, poziomów jest $n$, koszt $n^2$. Kiedy oś trafia skrajnie? Przy naiwnym wyborze „pierwszy element" — na danych… już posortowanych! Najzwyklejsze dane świata były najgorszym przypadkiem wczesnych implementacji (i bronią ataków: złośliwie ułożone dane potrafiły kłaść serwery). Stąd praktyka: oś ze środka (jak u nas), mediana z trzech, albo losowa — wtedy pechowe dane trzeba by wylosować, a prawdopodobieństwo katastrofy maleje wykładniczo. Quicksort to zakład: „prawie na pewno $n \log n$, ze śladowym ryzykiem $n^2$" — i świat ten zakład przyjmuje, bo stała jest mała, pamięć własna, a ryzyko kontrolowane losowością.

💭 Pomyśl: Dlaczego grupa rowne (elementy równe osi) jest wydzielona osobno i NIE jest sortowana rekurencyjnie? Co by się stało z listą [7, 7, 7, 7, 7], gdyby równe wpadały do „mniejszych"?

Sprawdź odpowiedź

Równe osi już są „na swoim miejscu" — między mniejszymi a większymi; sortować ich nie trzeba. Gdyby mniejsze łapało x <= os, to dla [7,7,7,7,7] podział dawałby grupy $4$ i $0$ za każdym razem (oś zabiera jedną sztukę, reszta w komplecie do jednej grupy) — patyk, $n^2$, na najbardziej niewinnych danych z możliwych. Lista samych duplikatów to klasyczne dane brzegowe quicksorta; trójpodział (mniejsze/równe/większe) załatwia je w jednym poziomie. Brzegi, brzegi, zawsze brzegi.

🧮 Prześledź

szybkie([3, 8, 2, 5, 9, 1]) — oś to element ze środka listy (indeks 3, czyli 5). Rozpisz podział i oba wywołania rekurencyjne (w nich też wskaż osie).

Sprawdź odpowiedź

Oś 5: mniejsze [3,2,1], równe [5], większe [8,9]. Rekurencja na [3,2,1]: oś (indeks 1) = 2 → [1], [2], [3] → [1,2,3]. Rekurencja na [8,9]: oś (indeks 1) = 9 → [8], [9], [] → [8,9]. Sklejka: [1,2,3] + [5] + [8,9] = [1,2,3,5,8,9] ✓. Zauważ w [8,9] podział $1/0$ — mini-patyk; przy dwóch elementach nieszkodliwy, ale to miniatura mechanizmu, który na dużą skalę robi $n^2$.

⚠️ Uwaga, pułapka

Nie myl osi (pivota) z medianą. Mediana dzieliłaby idealnie — ale jej znalezienie samo kosztuje; oś to tani kandydat na medianę i cała gra polega na tym, żeby wybierać go dobrze średnio, nie idealnie zawsze. Druga pułapka: nasza czytelna wersja buduje nowe listy (pamięć jak w scalaniu!) — o przewadze pamięciowej quicksorta wolno mówić dopiero przy podziale w miejscu. Ucz się na wersji czytelnej, cytuj właściwości wersji przemysłowej — i wiedz, o której właśnie mówisz.

🌍 Powiązania

Podział względem osi żyje też poza sortowaniem: „znajdź $k$-ty najmniejszy element" (mediana zarobków! dolny kwartyl wyników!) nie wymaga sortowania całości — wystarczy podział i rekurencja w jedną stronę (tę, gdzie leży szukany), co daje koszt liniowy średnio. Ten algorytm (quickselect) to młodszy brat quicksorta i częsty gość zadań maturalnych „o wybieraniu". A sama figura „podziel względem progu" wróci w dziale 9 przy drzewach poszukiwań.

🛠️ Teraz Ty

Bez komputera: prześledź szybkie na [4, 4, 4, 8, 1] (oś ze środka) — jak trójpodział radzi sobie z duplikatami? Z komputerem: zaimplementuj wersję czytelną; potem spróbuj idei podziału w miejscu na tablicy: dwa palce od końców, lewy szuka elementu > osi, prawy < osi, zamiana, aż palce się miną (nie martw się, jeśli zajmie to kilka podejść — granice indeksów w podziale w miejscu to słynne pole minowe; śledź na kartce!). Na deser: derby scalanie vs szybkie na liście losowej i posortowanej, $n = 10^5$, liczniki porównań.

📐 Definicje tej lekcji

  • Oś (pivot) i podział (partycjonowanie) — element odniesienia; rozdzielenie listy na mniejsze/równe/większe.
  • Sortowanie szybkie — podział + rekurencja na grupach + darmowa sklejka; średnio $O(n \log n)$ z małą stałą, pechowo $O(n^2)$.
  • Obrona osi — środek/mediana z trzech/losowość: pech przestaje być osiągalny dla złośliwych danych.

📌 Najważniejsze w pigułce

  • Quicksort tnie mądrze, żeby sklejać za darmo — lustrzane odbicie scalania.
  • Klasa zależy od jakości podziałów: połówki → $n \log n$; skrajne osie → patyk i $n^2$; duplikaty leczy trójpodział.
  • Zakład quicksorta: świetna średnia i stała za śladowe, kontrolowane ryzyko — scalanie zostaje tam, gdzie trzeba gwarancji.

🎒 Zadania

  1. Dla listy [1, 2, 3, 4, 5, 6, 7] i reguły „oś = pierwszy element" rozpisz drzewo wywołań quicksorta. Ile poziomów ma drzewo i jaka klasa kosztu z tego wynika?
Wskazówka i odpowiedź

Oś 1: podział [] / [1] / [2..7]; oś 2: [] / [2] / [3..7]… — patyk o $n$ poziomach, na każdym praca liniowa względem resztki: $7+6+\dots+1 = 28$ operacji, klasa $n^2$. Posortowane dane + naiwna oś = najgorszy przypadek na najczęstszych danych świata. Teraz powtórz z osią ze środka: 4 → [1,2,3]/[4]/[5,6,7] — dwa poziomy i po sprawie. Wybór osi to nie detal, to być albo nie być algorytmu.

  1. Które sortowanie wybierzesz: (a) system giełdowy z twardym limitem czasu odpowiedzi, (b) sortowanie miliona losowych pomiarów na własnym laptopie, (c) lista 30 nazwisk w skrypcie na kolanie? Uzasadnij przez gwarancje/stałe/pamięć.
Wskazówka i odpowiedź

(a) scalanie (albo pochodne) — twardy limit czasu wymaga gwarancji najgorszego przypadku; „prawie na pewno szybko" nie przejdzie audytu. (b) szybkie — losowe dane to jego żywioł, mała stała i pamięć w miejscu na milionie się liczą. (c) obojętne/wstawianie — trzydzieści elementów posortuje nawet bąbelkowe, wygrywa prostota. Zawodowa dojrzałość to nie znać „najlepszy algorytm", tylko dobrać zakład do stawki.

  1. Biblioteczne sorted() Pythona używa hybrydy (scalanie + wstawianie na krótkich fragmentach, z wykrywaniem gotowych posortowanych serii). Wyjaśnij, czemu hybryda bije czyste algorytmy — złóż odpowiedź z faktów z 6.4, 6.6 i 6.5/3.
Wskazówka i odpowiedź

Wstawianie ma malutką stałą i liniowość na prawie-posortowanych — więc krótkie fragmenty i gotowe serie sortuje taniej niż jakakolwiek rekurencja (6.4, 6.5/3: klasa przegrywa ze stałą przy małych $n$). Scalanie daje gwarancję $n \log n$ i stabilność na dużej skali (6.6). Hybryda skleja mocne strony: dołem rzemiosło o małej stałej, górą struktura o dobrej klasie — a wykrywanie serii honoruje porządek, który dane już mają. Realne biblioteki to portfele zakładów, nie monokultury.

🔍 Sprawdź, czy umiesz

  • Wykonać trójpodział względem osi i sklejkę na kartce.
  • Wskazać, co robi z drzewem rekurencji dobra i zła oś — i podać obronę.
  • Zestawić scalanie z szybkim w trzech wierszach: klasa, pamięć, gwarancje.

Ucz się tej jednostki z asystentem