Algoritmy usporadúvania

Na nasledujúcich troch grafoch je vidieť zobrazenie závislosti času usporadúvania náhodne vygenerovanej postupnosti od počtu prvkov pre rôzne algoritmy. Na prvom grafe je typ prvkov usporadúvanej postupnosti celé čísla, na druhom reálne čísla a na treťom sú to reťazce. Z grafov je možné vyčítať, ktorý zo zobrazených algoritmov je pre usporadúvanie postupnosti prvkov daného typu najvhodnejší. Grafy majú na osi X aj Y logaritmickú mierku. Logaritmická mierka bola použitá pre dobrú prehľadnosť grafu.
Na všetkých grafoch môžeme vidieť, že algoritmus Bubble sort pracuje najpomalšie, pričom pri postupnostiach so 100 celými číslami a pri postupnostiach so 100 reálnymi číslami je najhorší algoritmus Merge sort. Druhým najhorším algoritmom podľa grafov je Shell sort. Pre všetky možné typy usporadúvaných prvkov je najlepším algoritmom Quick sort. Pri celých číslach je druhým najlepším algoritmom Radix sort a pri reálnych číslach a reťazcoch, kde sa Radix sort nepoužíva je na druhom mieste Merge sort. Pri usporadúvaní postupnosti celých čísel sa algoritmy Select sort a Insert sort na danom grafe prekrývajú, pri usporadúvaní reálnych čísel je algoritmus Select sort pomalší než Insert sort a pri usporadúvaní reťazcov je pomalší Insert sort.

Na nasledujúcich dvoch obrázkoch môžeme vidieť porovnanie jednotlivých algoritmov z pohľadu priemerného počtu porovnaní vykonaných pri usporadúvaní náhodne vygenerovanej postupnosti s 100 a 10 000 prvkami. Prvý graf znázorňuje priemerný počet porovnaní vykonaný algoritmami pri usporadúvaní postupnosti 100 celých čísel a druhý pri usporadúvaní postupnosti 10 000 celých čísel. Keďže pri usporadúvaní postupnosti s 10 000 prvkami rekurzívnym algoritmom Quick sort systém vyhlásil pretečenie zásobníka, je v druhom grafe použitá priemerná hodnota počtu porovnaní vykonaných nerekurzívnym algoritmom Quick sort. Rekurzívnosť algoritmu Quick sort vykonaný počet porovnaní neovplyvňuje. V grafoch chýba algoritmus Radix sort, lebo ako už vieme jedná sa o nekomparačný algoritmus.
Na oboch grafoch môžeme vidieť, že najviac porovnaní vykonáva algoritmus Bubble sort a najmenej Merge sort. Za algoritmom Bubble sort nasleduje Shell sort, Select sort, ďalej Insert sort a Quick sort.

Na nasledujúcich dvoch obrázkoch môžeme vidieť porovnanie jednotlivých algoritmov z pohľadu priemerného počtu presunov vykonaných pri usporadúvaní náhodne vygenerovanej postupnosti s 100 a 10 000 prvkami. Prvý graf znázorňuje priemerný počet presunov vykonaný algoritmami pri usporadúvaní postupnosti 100 celých čísel a druhý pri usporadúvaní postupnosti 10 000 celých čísel. Keďže pri usporadúvaní postupnosti s 10 000 prvkami rekurzívnym algoritmom Quick sort systém vyhlásil pretečenie zásobníka, je v druhom grafe použitá priemerná hodnota počtu presunov vykonaných nerekurzívnym algoritmom Quick sort. Rekurzívnosť algoritmu Quick sort vykonaný počet presunov neovplyvňuje.
Na oboch grafoch môžeme vidieť, že najviac presunov vykonáva algoritmus Bubble sort a najmenej Quick sort. Za algoritmom Bubble sort nasleduje Insert sort, Shell sort, ďalej Select sort a Merge sort.

Na nasledujúcich dvoch obrázkoch môžeme vidieť porovnanie jednotlivých algoritmov z pohľadu priemernej doby usporadúvania pri usporadúvaní náhodne vygenerovanej postupnosti s 100 a 10 000 prvkami. Prvý graf znázorňuje priemernú dobu usporadúvania pri usporadúvaní postupnosti 100 celých čísel a druhý pri usporadúvaní postupnosti 10 000 celých čísel. Keďže pri usporadúvaní postupnosti s 10 000 prvkami rekurzívnym algoritmom Quick sort systém vyhlásil pretečenie zásobníka, je v druhom grafe použitá priemerná doba usporadúvania nameraná pri použití nerekurzívnej podoby algoritmu Quick sort.
Na grafoch je vidieť, že priemerná doba usporadúvania je na priemernom počte porovnaní a presunov zavislá. Poradie algoritmov na nasledujúcich grafoch odráža približne poradie algoritmov na grafoch predchádzajúcich. S istými odchýlkami má v priemere najväčšiu dobu usporadúvania algoritmus Bubble sort a najmenšiu Quick sort.
Zvláštnosťou je priemerná doba usporadúvania postupnosti algoritmom Merge sort. Ako môžeme vidieť na prvom grafe priemerná doba usporadúvania postupnosti so 100 prvkami je pri použití algoritmu Merge sort najvyššia spomedzi všetkých algoritmov aj napriek tomu, že priemerný počet porovnaní a presunov pri použití algoritmu Merge sort nebol najvyšší. Vysoká hodnota priemernej doby usporadúvania je spôsobená rekurzívnymi volaniami, ktoré algoritmus vykonáva. Do priemernej doby usporadúvania algoritmom Merge sort bol zarátaný takisto čas rozdelenia postupnosti na dve podpostupnosti, kedy sa počet porovnaní a presunov nezvyšuje, čo je ďalším dôvodom, prečo predchádzajúce grafy ukazujúce priemerný počet porovnaní a presunov nezdôvodňujú vysokú priemernú dobu usporadúvania algoritmom Merge sort. Rovnaký jav by sme očakávali aj pri usporadúvaní postupnosti s 10 000 prvkami. Avšak na druhom grafe môžeme vidieť, že pri usporadúvaní postupnosti s 10 000 prvkami nie je priemerná doba usporadúvania algoritmom Merge sort ani zďaleka najvyššia. Je to spôsobené skutočnosťou, že pri postupnostiach s viac ako 100 prvkami je čas rekurzívnych volaní a čas rozdeľovania postupnosti zanedbateľný a prejavuje sa efektívnosť algoritmu Merge sort.