next up previous
Next: Pole indexů, pořadí Up: Řazení (třídění) Previous: Heapsort

Quicksort

Vybereme v poli jeden prvek, tak zvaný pivot, pole rozdělíme na dvě podpole a přeházíme prvky tak, aby v jednom podpoli byly prvky menší než pivot a ve druhém větší než pivot. Pivot už tedy máme zařazený na správném místě. Nyní stejný postup aplikujeme na obě podpole až do té doby než dostaneme úseky se 7 nebo méně prvky. Tyto úseky je již efektivnější třídit přímým vkládáním.

Pozn. Pokud dělící prvky vybíráme odleva a pole je již seřazené, má algoritmus $\sim N^2$ operací. Pro pole náhodných prvků je ovšem nejrychlejší.

Pozn. Pokud je nebezpečí, že pole může být seřazené, je lépe dělící prvky vybírat náhodně.



Jiri Limpouch
2000-03-29