quicksort
Főnév
quicksort (tsz. quicksorts)
A Quicksort egy rendkívül hatékony, elosztás-alapú, rekurzív rendezési algoritmus, amelyet Tony Hoare fejlesztett ki 1959-ben. A gyakorlati alkalmazásokban az egyik leggyorsabb rendezési algoritmus, átlagos időkomplexitása: O(n log n), de a legrosszabb esetben O(n²) is lehet. Ennek ellenére a gyors működése, egyszerű implementációja és a helyben végzett rendezés miatt (in-place, extra memóriaigény nélkül) széles körben használják.
🌟 Alapötlet
A Quicksort az ún. oszd meg és uralkodj (divide and conquer) elvet követi:
- Pivot kiválasztás: kiválaszt egy elemet a tömbből (ez a pivot).
- Felosztás (partíciózás): a tömb elemeit úgy rendezi át, hogy a pivotnál kisebbek balra, a nagyobbak jobbra kerülnek.
- Rekurzió: a pivot körül kialakult két részhalmazt külön-külön rendezi újra a fenti lépések szerint.
📐 Működés részletesen
1. Pivot kiválasztása
Ez kritikus lépés. A választási stratégia befolyásolja a hatékonyságot.
- Első elem
- Utolsó elem
- Középső elem
- Véletlenszerű elem
- Medián a három közül (első, középső, utolsó) – ez gyakran a legjobb kompromisszum
2. Partíció
A partíciózás során minden elemet összehasonlítunk a pivottal. Ha kisebb, mint a pivot, bal oldalra kerül, ha nagyobb, akkor jobbra.
Például, ha a pivot a 8, és a tömb: [4, 9, 2, 8, 1, 6], a partíció után így nézhet ki: [4, 2, 1, 6, 8, 9] – a 8 helyére kerül, a bal oldalán kisebbek, a jobb oldalán nagyobbak vannak.
3. Rekurzív hívás
A Quicksort újra meghívja magát a bal és jobb részhalmazra, amíg az egyes részhalmazok mérete 0 vagy 1 nem lesz – ekkor már rendezettnek tekinthető.
📊 Időkomplexitás
| Eset | Időkomplexitás |
|---|---|
| Legjobb (pivot a középen) | O(n log n) |
| Átlagos | O(n log n) |
| Legrosszabb (rossz pivot választás, pl. rendezett sorozat) | O(n²) |
🧠 Helyigény
- In-place működik: O(log n) extra helyigény a rekurzív hívások miatt
- Nem igényel további tömböt, szemben például a mergesorttal
🔁 Iteratív verzió
Létezik iteratív megvalósítása is verem segítségével, amely explicit módon kezeli az osztási lépéseket, kiküszöbölve a rekurziót – ezzel elkerülhető a rekurzív stack overflow.
✅ Előnyök
- Átlagosan nagyon gyors
- In-place működés (nincs szükség plusz memóriára)
- Könnyen implementálható
- Jó teljesítmény cache-eken
❌ Hátrányok
- Nem stabil (az azonos értékek sorrendje változhat)
- Legrosszabb esetben lassú (ha mindig a legkisebb vagy legnagyobb elemet választjuk pivotnak)
🔧 C++ példa
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // utolsó elem a pivot
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
++i;
std::swap(arr[i], arr[j]);
}
}
std::swap(arr[i + 1], arr[high]);
return i + 1;
}
void quicksort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quicksort(arr, low, pi - 1);
quicksort(arr, pi + 1, high);
}
}
📌 Stabil vs nem stabil
A Quicksort nem stabil algoritmus. Például ha két azonos értékű, de más kontextusú elem van (pl. névvel párosítva), a sorrendjük a rendezés után megváltozhat.
🧪 Pivotstratégia hatása
Például egy már rendezett sorozaton, ahol mindig az első elemet választjuk pivotnak, a Quicksort teljesítménye O(n²) lesz.
Ha viszont random pivotot választunk vagy a „három közül a középsőt”, akkor az esélyes, hogy közel az optimális O(n log n) lesz.
📈 Összehasonlítás más algoritmusokkal
| Algoritmus | Átlagos idő | Helyigény | Stabil? |
|---|---|---|---|
| Quicksort | O(n log n) | O(log n) | ❌ |
| Mergesort | O(n log n) | O(n) | ✔️ |
| Heapsort | O(n log n) | O(1) | ❌ |
| Bubblesort | O(n²) | O(1) | ✔️ |
💡 Optimalizálások
- Tail Recursion Elimination: a rekurzió helyett iteráció a nagyobb intervallumra
- Median-of-three pivot kiválasztás
- Kis méretű tömbökre váltás Insertion Sort-ra
- Dual-pivot Quicksort: két pivotot használ – gyorsabb lehet sok esetben
📚 Történeti háttér
Tony Hoare fejlesztette ki, miközben a szovjet Unión belül dolgozott egy fordítóprogramon. A cél az volt, hogy hatékonyan rendezze a kulcsszavakat. A Quicksort sikere gyorsan ismertté tette, és azóta is az egyik legismertebb algoritmus a számítástudományban.
🔁 Példa lépésenként
Tömb: [10, 7, 8, 9, 1, 5]
- Pivot: 5
- Partíció:
[1, 5, 8, 9, 10, 7] - Bal oldal:
[1]→ már rendezett - Jobb oldal:
[8, 9, 10, 7]→ rekurzió új pivottal
Végül: [1, 5, 7, 8, 9, 10]
🧮 Példák használatra
- STL
std::sort()(C++): általában introsortot használ (quicksort + heapsort hibrid) - Java
Arrays.sort(): primitív típusokra dual-pivot quicksortot használ - Python
sort()éssorted(): Timsortot használ (quicksort nem stabil, ezért nem hasznos stabil rendezéshez)
🔚 Összegzés
A Quicksort egy gyors, praktikus és széles körben alkalmazott rendező algoritmus, amely jól alkalmazható a legtöbb valós alkalmazásban. Nagy mennyiségű adatra is hatékony, főleg ha jól választjuk meg a pivotot és kombináljuk más algoritmusokkal.