Programátoři Blog (nejen) o programování

Zkousel jsem si naimplementovat nektere tridici algoritmy a porovnat je.

• Tridil jsem pole nahodnych celych cisel a pocital jsem kolikrat porovnavam nejakou hodnotu v poli a kolikrat prohazuju dva prvky v poli. Na ose x je velikost pole, na ose y pocet provedenych operaci.
• Algoritmy jsou implementovany co nejjednoduseji a nepochybne jsem do nich zanesl i nejake chyby, takze to neberte vazne, o nicem to nevypovida.
• Pro srovnani je tam i standardni Cckovsky qsort(), ktery je uz trochu na jine urovni;) zdrojak napriklad zde.
• K vykresleni grafu jsem pouzil gnuplot
• Kdyby se chtel nekdo zasmat mym zdrojakum, jsou k dispozici

Pocet porovnani prvku pole:

• Bubble sort a selection sort se prekryvaji.
• Prekryva se i merge sort s libc qsortem (z grafu se zda, ze je merge sort velmi rychly, nicmene to je zpusobeno tim, ze "moje" implementace ma O(N) pametovou narocnost. ostatni maji O(1) az na qsort, ktery by mel byt O(logN) nebo tak nejak. pokud jsem to pochopil spravne tak ten libc qsort je taky O(1)).

Pocet prohozeni prvku pole:

• Tady se prekryva bubble sort s shaker sortem.
• libc qsort() na grafu neni videt, jelikoz tento udaj nemam jak zjistit
• V tomto smeru je jasnym vitezem selection sort, ktery potrebuje jenom tolik swap-u, kolik je v poli prvku;)

Detail s mensimi poli:

• Merge sort a libc qsort se opet prekryvaji. Zrejme se qsortu vzdycky podari jako pivot vybrat median.

Vetsi pole:

• Pokud predtim nebyl, tak tady je dobre videt parabolicky tvar grafu O(N²) algoritmu;)

O(NlogN) algoritmy:

• muj qsort je nejaky krivy;)