Lekce 9 - Velké srovnání základních třídících algoritmů

V minulé lekci, Counting sort, jsme si ukázali algoritmus Counting sort i se zdrojovými kódy.

Třídění je základní funkčností většiny počítačových programů i her, která se provádí velmi často. Setkáváme se s ní pokaždé, když počítač řadí kontakty podle abecedy, když hra vykresluje 2d scénu (nejprve si seřadí objekty podle vzdálenosti od kamery a až potom je může začít odzadu vykreslovat) nebo když zkrátka potřebujeme setřídit nějaké množství dat podle určitých kritérií, abychom z nich vytvořili nějaké statistiky. Můžeme tedy třídit např. žáky podle prospěchu, zaměstnance podle platu, kandidáty podle počtu hlasů atp. Třídění je spolu s vyhledáváním stěžejní vlastností také velkých obchodních informačních systémů. Jeho rychlost je tedy naprosto klíčová a závisí (kromě rychlosti počítače) na časové složitosti zvoleného třídícího algoritmu a také na velikosti a struktuře zpracovávaných dat. Pokud budeme znát principy a časové složitosti třídících algoritmů, můžeme dosáhnout obrovských časových úspor v našich programech. I hodinová operace se špatně zvoleným algoritmem se může jeho záměnou proměnit na záležitost několika málo vteřin.

Následující práce se zabývá porovnáním výkonu (benchmarkem) šesti třídících algoritmů. Cílem je přinést relativní porovnání rychlosti algoritmů na stejném stroji a stejných testovacích datech, která budou dostatečně objemná a různorodá. Měla by potvrdit očekávané chování a ohodnotit algoritmy podle času, který tříděním strávily, resp. zjistit, které algoritmy je vhodné použít na určitý typ dat a které nikoli.

Popis podmínek testování

V rámci této práce jsem testoval 6 třídících algoritmů založených na vzájemném porovnávání prvků. Následuje jejich seznam a hrubý popis funkčnosti, implementace a časové složitosti:

...konec náhledu článku...
Pokračuj dál