Quicksort

Quicksort (nazývané aj rýchle triedenie) je jednoduchý triediaci algoritmus, ktorý porovnáva prvky poľa. Jeho tvorcom je Sir Charles Antony Richard Hoare. Základnou myšlienkou tohto triediaceho algoritmu je rozdelenie triedeného poľa na dve približne rovnako veľké časti (približne rovnaký počet položiek). Algoritmus si zvolí hodnotu, ktorá sa nazýva pivot, na základe ktorej bude porovnávať hodnoty a z celkového poľa hodnôt si vytvorí dve časti.V jednej časti sú hodnoty menšie ako pivot, v druhej väčšie. Postupne bude v jednotlivých častiach triediť (zoraďovať) hodnoty podľa ich veľkosti. Vždy si danú časť rozdelí na dve menšie časti podľa pivotu a triedi. Ide o rekurzívne triedenie. Ak budú obe časti poľa roztriedené, bude roztriedené i celé pole.

Problém môže nastať pri voľbe pivotu. Môže nastať situácia, že sa zvolená hodnota bude približovať mediánu (strednej hodnote). Vtedy je algoritmus najrýchlejší, pretože ľahko určí, ktoré hodnoty sú vyššie či nižšie a vie ich ľahšie utriediť. Ak nastane opačná situácia, algoritmus sa stáva pomalším a vyžaduje si aj viac pamäte.

Opäť si naprogramujeme využitie tohto triedenia. Ako prvé si zadeklarujeme pole desiatich prvkov od 1 do 10. Ďalej si musíme určiť pivot. Následne si prvky, cez ktoré prechádza cyklus rozdelíme na vyššie a nižšie a vytvoríme tým dve približne rovnaké polia. Následne sa začne samotné triedenie v jednotlivých poliach. Triedenie sa vykonáva, kým index daného prvku nie je vyšší ako pivot (index prvku z druhého poľa). Potom sa postupuje, kým nedosiahneme prvok menší ako pivot. Nasleduje rekurzia, volanie procedúry samou sebou, kým sa neroztriedia všetky prvky podľa veľkosti.