gyorsrendezés

Gyorsrendezés (quicksort) egy oszd meg és uralkodj alapú rendezési algoritmus. A folyamat lényege, hogy kiválasztunk egy pivotnak nevezett elemet, majd a tömböt úgy partitíáljuk, hogy a pivotnál kisebbek vagy egyenlők a bal oldalra, a nagyobbak pedig a jobb oldalra kerülnek; a pivot a végleges helyére kerül. Ezt követően a bal és a jobb részhalmazokon rekurzívan hajtjuk végre a rendezést, amíg minden rész ki nem tűnik.

Átlagos futási ideje O(n log n). A legjobb és tipikusan az átlagos eset is ezt éri el; a legrosszabb eset O(n^2), például ha a pivot mindig a legkisebb vagy legnagyobb elem. A megoldások többsége in-place, így extra memória szintje általában a rekurziós verem miatt O(log n) körüli, rosszabb esetben pedig O(n).

Változatok és optimalizációk: a teljesítményt jelentősen befolyásolja a pivot kiválasztása (például véletlenszerű pivot vagy medián-hármas). Különböző partíciós sémák léteznek, például Hoare- és Lomuto-partíció, amelyek más-más viselkedést adnak. A duplikátumok hatékonyabb kezelésére gyakran alkalmaznak háromutas partíciót. Alapértelmezésben a gyorsrendezés nem stabil, de stabil változatok is léteznek extra memória igényével.

Történelem és felhasználás: a gyorsrendezést 1960-ban Tony Hoare brit számítógép-tudós dolgozta ki. Széles körben használják a számítógépes könyvtárak rendező eljárásaiként, mert általában gyors és cache-kész a teljesítménye, különösen nagy adathalmazokon.