Quicksort

Vyberie jednu hodnotu, tzv. pivot, a menšie hodnoty presunie naľavo od neho, väčšie napravo. Potom to isté urobí s každou stranou.

najlepší Ω(n log n)
priemerný Θ(n log n)
najhorší O(n²)
pamäť O(log n)
nestabilný
bez pamäte navyše

Čo to znamená?

Najlepší prípad: ako rastie čas s veľkosťou zoznamu n, keď je vstup pre tento algoritmus najľahší.
Priemerný: obvyklý rast času s n. Pri n² trvá dvakrát viac hodnôt asi štyrikrát dlhšie; n log n rastie oveľa pomalšie.
Najhorší: rast času na najťažšom vstupe. Dôležitý, keď sa triedenie nesmie nikdy spomaliť.
Pamäť: koľko pamäte navyše treba okrem zoznamu. 1 znamená pár premenných, n kópiu zoznamu.
Stabilný: dve rovnaké hodnoty si zachovajú pôvodné poradie. Dôležité pri triedení záznamov podľa jedného poľa.
Bez pamäte navyše: triedi priamo vnútri zoznamu, bez druhého zoznamu.

porovnávanie
presun
pivot
na konečnom mieste

0 / 187 krokov

Porovnania Výmeny

Stlačte Prehrať: čiary ukazujú, ako počas triedenia rastú náklady

Rýchlosť 8 krokov/s

Medzerník: prehrať alebo pozastaviť. Šípky vľavo/vpravo: krok. Home a End: preskočiť.

Skúste: Zvoľte obrátený zoznam. Pivot je vždy najmenšia alebo najväčšia zo zvyšných hodnôt, takže jedna strana je prázdna a náklady rastú k n².

Ako to funguje

Pivotom je tu posledná hodnota úseku. Zľava doprava sa každá hodnota, ktorá nie je väčšia ako pivot, vymení na ľavú stranu. Potom sa pivot postaví medzi obe strany a tam už zostane. Každá strana sa nakoniec zoradí rovnako.

Kedy sa hodí

V praxi jeden z najrýchlejších spôsobov triedenia a takmer nepotrebuje pamäť navyše. Keď však opakovane vyberá zlý pivot, napríklad na už zoradenom zozname, spomalí sa. Preto sa v praxi pivot vyberá starostlivejšie.