Quicksort: pivot rozhoduje o všem
Quicksort vybere jeden prvek — pivot — a přerovná pole tak, aby menší byly vlevo a větší vpravo. Pak totéž na obě poloviny. Celá jeho analýza závisí na jedné otázce: jak vyrovnané ty poloviny jsou.
- Pivot padne doprostřed → dvě poloviny, log n úrovní, n log n.
- Pivot padne na kraj → jedna část je prázdná a druhá o jeden menší. Úrovní je n, a to je n².
A teď to nepříjemné: s pivotem „poslední prvek“ nastane ten druhý případ na už setříděném poli. Ne na nějakém exotickém vstupu — na tom nejběžnějším, jaký v praxi přijde. Změřeno na 512 prvcích: rekurze jde 511 úrovní hluboko, což už není otázka rychlosti, ale přetečení zásobníku.
Medián ze tří
Oprava je stará a laciná: nevzít poslední prvek, ale medián z prvního, prostředního a posledního. Na setříděném poli tím padne pivot přesně doprostřed — tedy z nejhoršího případu se stane nejlepší.
| setříděný vstup, n = 512 | poslední prvek | medián ze tří |
|---|---|---|
| změřený exponent | 1,98 | 1,17 |
| hloubka rekurze | 511 | 9 |
Ta čísla nejsou opsaná — testy v repu je pouštějí a kontrolují. A ten druhý řádek je ten důležitější: hloubka rekurze je to, co program shodí, kdežto pomalost je jen nepříjemná.
Ostatní volby pivota
| volba | nejhorší případ | poznámka |
|---|---|---|
| poslední / první | setříděné pole | nepoužívat |
| medián ze tří | speciálně vyrobený vstup | obvyklá volba |
| náhodný | nedá se vyrobit dopředu | chrání i proti útoku |
| introsort | žádný — přepne na haldu | to, co je v knihovnách C++ |
Introsort je odpověď, ke které se to nakonec sešlo: jede quicksort, počítá si hloubku rekurze, a když překročí ~2·log n, přepne na třídění haldou, které má zaručené n log n. Rychlost quicksortu v běžném případě, záruka v tom nejhorším.
Náhodný pivot má důvod, který není o rychlosti. Když je volba deterministická, dá se vstup vyrobit tak, aby na ni padl nejhorší případ — a u serveru, který třídí data od uživatelů, je to způsob útoku. Náhodný pivot to znemožní, protože útočník neví, co bude vybráno.