Geek tričko zdarma Python týden
Tričko zdarma! Stačí před dobitím bodů použít kód TRIKO15. Více informací zde
Pouze tento sleva až 80% na kurzy Python

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

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...

Prémiový článek

Prémiový článek

Na itnetwork.cz se nachází největší a nejucelenější česká databáze s výukovými články, jejímž cílem je umožnit kvalitní vzdělání v oblasti IT úplně každému. Měsíčně zobrazíme k milionu článků a sklidíme desítky děkovných emailů, kde nám sdělujete, že jsme vám pomohli k lepšímu zaměstnání nebo vzdělání.

Ačkoli se snažíme držet většinu obsahu úplně zadarmo, udržovat síť v provozu a aktuální stojí obrovské úsilí. Proto je nějaký obsah, jako cvičení nebo odbornějšíčlánky, přístupný pouze za body. Nebojte, nestojí to skoro nic :)

Popis článku

Požadovaný článek má následující obsah:

Velké srovnání základních třídících algoritmů selection sort, bubble sort, merge sort, heap sort, quick sort.

Omezená nabídka: Nauč se vše a ušetři

Koupit články a funkce postupně a po jednom 20 bodů
Koupit celý kurz se všemi články a funkcemi za exkluzivní cenu 17 bodů
Na svém účtu máš aktuálně 0 bodů
Koupí tohoto výhodného balíčku získáš přístup ke všem 11 článkům s kontrolou a certifikací a ještě navíc ušetříš 8 Kč. Nabídka je omezená pouze pro první články z kurzu a obsahuje exkluzivní slevu 15%.
17 bodů získáš za přidání svého článku na síť nebo odpovídá 50 Kč 43 Kč

Koupit pouze tento článek

Pozor, pokud si koupíš pouze tento článek, ztratíš nárok na speciální slevu 15% na balíček všech článků.

Pro přístup k článku potřebuješ 10 bodů
Na svém účtu máš aktuálně 0 bodů
10 bodů získáš za přidání svého článku na síť nebo odpovídá 25 Kč

Koupí článku k němu získáš neomezený přístup a to napořád. Posuneš své znalosti zas kousek dopředu a zároveň nám pomůžeš udržovat celý projekt při životě a pomáhat vám tak k lepší budoucnosti.

Obsah článku spadá pod licenci Premium, koupí článku souhlasíš se smluvními podmínkami.

Body získáš, když podpoříš naši síť. To můžeš udělat buď zasláním symbolické částky na podporu provozu nebo přidáním obsahu na síť.

Dobít body můžeš okamžitě např.:

Kartou SMS Převodem
Kartou SMS Převodem

 

Článek pro vás napsal David Čápka
Avatar
Autor pracuje jako softwarový architekt a pedagog na projektu ITnetwork.cz (a jeho zahraničních verzích). Velmi si váží svobody podnikání v naší zemi a věří, že když se člověk neštítí práce, tak dokáže úplně cokoli.
Unicorn College Autor sítě se informační technologie naučil na Unicorn College - prestižní soukromé vysoké škole IT a ekonomie.
Předchozí článek
Counting sort
Všechny články v sekci
Třídící/řadící algoritmy
Miniatura
Následující článek
Kartičky k procvičení třídících algoritmů
Aktivity (2)