Po napisani (i ked nie celkom vydareneho:) prveho clanku o triedeni som uvazoval ze vzapeti napisem nieco o dalsich sposoboch triedenia. V tom momente ma napadlo ze by nebolo zle este porovnat rychlosti priamych metod. Testy sa robili s usporiadanym,nahodne usporiadanym a opacne usporiadanym polom na cpu Cyrix 133 Mhz, 32MB ram. Vysledky su v niektorych pripadoch velmi prekvapujuce.
Na samotny benchmark som si naprogramoval jednoduchy program ktory pocita dobu od startu po koniec algoritmu.Vysledky udava v sekundach a drobne v mikrosekundach. Snazil som sa program naprogramovat co najefektivnejsie a najlepsie, takze dufam ze ovplyvnovanie vysledkov z jeho strany bude minimalne alebo skor ziadne :-). Ako velkost pola som pouzil 512,1024,4096,8192 a 16384 bajtov.
Zacneme usporiadanym polom:
Dlzka 512 bajtov:
Priame vkladanie (insert sort): 0 sec 41 ms
Binarne vkladanie (bin sort): 0 sec 329 ms
Priamy vyber (select sort): 0 sec 4182 ms
Priama vymena (bubble sort): 0 sec 9112 ms
Shakersort: 0 sec 73 ms
Ako mate moznost vidiet najhorsie obstal bubblesort a najlepsie insertsort.Prekvapenim je binsort ktory namiesto ocakavaneho zlepsenia zhorsil celkovy cas na 329 ms ale na druhej strane Shakersort je v tomto pripade vyraznym vylepsenim oproti jeho zakladnej bublinovej verzii.
Dlzka 1024 bajtov:
Priame vkladanie (insert sort): 0 sec 76 ms
Binarne vkladanie (bin sort): 0 sec 728 ms
Priamy vyber (select sort): 0 sec 16547 ms
Priama vymena (bubble sort): 0 sec 35724 ms
Shakersort: 0 sec 143 ms
Tu je zaujimave len dodat ze insert sort sa stabilne drzi pod 100ms zatial co bubblesort sa zhrosil takmer 4x.Vsimnite si tiez ze select sort je v priemere 2x rychlejsie ako samotny bubblesort.
Dlzka 4096 bajtov:
Priame vkladanie (insert sort): 0 sec 288 ms
Binarne vkladanie (bin sort): 0 sec 3515 ms
Priamy vyber (select sort): 0 sec 261444 ms
Priama vymena (bubble sort): 1 sec 569067 ms
Shakersort: 0 sec 559 ms
No tak tu uz vidno jednoznacne (ne)efektivnost niektorych algoritmov. Najhorsie obstal ako vzdy bubblesort, ale zase taky insertsort sa statnocne drzi pod 1000ms.
Dlzka 8192 bajtov:
Priame vkladanie (insert sort): 0 sec 638 ms
Binarne vkladanie (bin sort): 0 sec 7827 ms
Priamy vyber (select sort): 1 sec 167766 ms
Priama vymena (bubble sort): 3 sec 319601 ms
Shakersort: 0 sec 1228 ms
No tak toto uz su riadne rozdiely.Vidno, ze v priamej vymene kde je dominantnym prvkom vymena dvoch prvkov je prave toto s najvacsou pravdepodobnostou brzda.
Dlzka 16384 bajtov:
Priame vkladanie (insert sort): 0 sec 1417 ms
Binarne vkladanie (bin sort): 0 sec 17078 ms
Priamy vyber (select sort): 5 sec 111781 ms
Priama vymena (bubble sort): 10 sec 109292 ms
Shakersort: 0 sec 2633 ms
No ked budete potrebovat utriedit utriedene pole o dlzke 16384 bajtov tak jednoznacne pouzite insertsort, ktory je jednoznacnym vitazom nasho prveho testu! :).
Priemerne casy:
Priame vkladanie (insert sort): 0 sec 492 ms
Binarne vkladanie (bin sort): 0 sec 5895.4 ms
Priamy vyber (select sort): 1 sec 311507.6 ms
Priama vymena (bubble sort): 3 sec 8559.2 ms
Shakersort: 0 sec 927.2 ms
Nahodne usporiadane pole:
Dlzka 512 bajtov:
Priame vkladanie (insert sort): 0 sec 2978 ms
Binarne vkladanie (bin sort): 0 sec 1288 ms
Priamy vyber (select sort): 0 sec 4237 ms
Priama vymena (bubble sort): 0 sec 12603 ms
Shakersort: 0 sec 4050 ms
Tu uz pekne vidno ze vylepsenie insertsort-u v podobe binsortu je zhruba 2.3 rychlejsie.
Dlzka 1024 bajtov:
Priame vkladanie (insert sort): 0 sec 12461 ms
Binarne vkladanie (bin sort): 0 sec 4499 ms
Priamy vyber (select sort): 0 sec 16552 ms
Priama vymena (bubble sort): 0 sec 136991 ms
Shakersort: 0 sec 41131 ms
Binsort je uz 2.7x vykonejsi ako insertsort.
Dlzka 4096 bajtov:
Priame vkladanie (insert sort): 1 sec 349374 ms
Binarne vkladanie (bin sort): 0 sec 146771 ms
Priamy vyber (select sort): 1 sec 648233 ms
Priama vymena (bubble sort): 1 sec 911357 ms
Shakersort: 0 sec 654717 ms
Tak toto je velke prekvapenie pre vsetkych.Zdanlivo najefektivnejsi insertsort sa zhorsil a je druhy najhorsi v tomto teste! Zdanie klame:).Este vzdy nahodne usporiadane pole najlepsie zvlada binsort.
Dlzka 8192 bajtov:
Priame vkladanie (insert sort): 1 sec 766803 ms
Binarne vkladanie (bin sort): 0 sec 229889 ms
Priamy vyber (select sort): 1 sec 122617 ms
Priama vymena (bubble sort): 3 sec 140562 ms
Shakersort: 1 sec 99252 ms
No tak toto je zaujimave.zatial co binsort sa zhrosil o sotva polovicu. bubblesort sa zhrosil takmer 1.5x!:)
Dlzka 16384 bajtov:
Priame vkladanie (insert sort): 4 sec 480651 ms
Binarne vkladanie (bin sort): 1 sec 908045 ms
Priamy vyber (select sort): 4 sec 773997 ms
Priama vymena (bubble sort): 14 sec 204151 ms
Shakersort: 4 sec 380978 ms
K tomu niet co dodat v tomto teste teda suverene vyhral binsort a prehral ako vzdy bubblesort:).
Priemerne casy:
Priame vkladanie (insert sort): 1 sec 522453.4 ms
Binarne vkladanie (bin sort): 0 sec 458098.4 ms
Priamy vyber (select sort): 1 sec 513127.2 ms
Priama vymena (bubble sort): 3 sec 845132.8 ms
Shakersort: 1 sec 96046.14 ms
Na zaver tu mame test opacne usporiadaneho pola:
Dlzka 512 bajtov:
Priame vkladanie (insert sort): 0 sec 5993 ms
Binarne vkladanie (bin sort): 0 sec 2290 ms
Priamy vyber (select sort): 0 sec 4184 ms
Priama vymena (bubble sort): 0 sec 14278 ms
Shakersort: 0 sec 7214 ms
Dlzka 1024 bajtov:
Priame vkladanie (insert sort): 0 sec 23784 ms
Binarne vkladanie (bin sort): 0 sec 8389 ms
Priamy vyber (select sort): 0 sec 16434 ms
Priama vymena (bubble sort): 0 sec 56526 ms
Shakersort: 0 sec 28923 ms
Dlzka 4096 bajtov:
Priame vkladanie (insert sort): 0 sec 379211 ms
Binarne vkladanie (bin sort): 0 sec 123100 ms
Priamy vyber (select sort): 1 sec 260370 ms
Priama vymena (bubble sort): 1 sec 900899 ms
Shakersort: 0 sec 461552 ms
Dlzka 8192 bajtov:
Priame vkladanie (insert sort): 1 sec 580855 ms
Binarne vkladanie (bin sort): 1 sec 500322 ms
Priamy vyber (select sort): 1 sec 87810 ms
Priama vymena (bubble sort): 3 sec 700794 ms
Shakersort: 2 sec 914394 ms
Dlzka 16384 bajtov:
Priame vkladanie (insert sort): 9 sec 611838 ms
Binarne vkladanie (bin sort): 2 sec 932697 ms
Priamy vyber (select sort): 5 sec 310762 ms
Priama vymena (bubble sort): 16 sec 862903 ms
Shakersort: 8 sec 726404 ms
Priemerne casy:
Priame vkladanie (insert sort): 2 sec 320336.2 ms
Binarne vkladanie (bin sort): 0 sec 913359.6 ms
Priamy vyber (select sort): 1 sec 535822 ms
Priama vymena (bubble sort): 4 sec 507080 ms
Shakersort: 2 sec 627697.4 ms
Musim povedat ze po skonceni tohto testu som zostal trosku prekvapeny. Ocakaval som ze selectsort bude patrit k najrychlejsim, a ze binsort bude na tom zhruba rovnako ako insertsort. Suma sumarum. Z testu vypliva toto: Na triedenie (takmer) usporiadanych prvkov je najlepsie pouzit insertsort. Na triedenie nahodne usporiadanych prvkov je najlepsie pouzit binsort. Na triedenie opacne usporiadanehych prvkov je najlepsie pouzit takisto binsort.v92
