Algoritmer og Datastrukturer 1

Eksperimentelle erfaringer med Sortering

Denne side viser eksperimentelle data for forskelige sorterings algoritmer. De algoritmerne der er implementeret er:

• InsertionSort
• MergeSort, der kun bruger to arrays, hvor man skifter mellem de to arrays til at gemme resultaterne af de rekursive kald
• HeapSort
• QuickSort, der altid vælger det sidste element som pivot
• QuickSort, der altid vælger det midterste element som pivot (i det følgende QuickSort special)

For at optimere de rekursive sorterings algoritmer QuickSort og MergeSort, skiftes der for små problemstørrelser til InsertionSort. Nedenstående plots, threshold.pdf, viser udførselstiden (y-aksen) for MergeSort og QuickSort når problemstørrelsen hvor man skifter over til InsertSort varieres (x-aksen). Desuden vises plots for antal sammenligninger, "cache faults", og "branch mispredictions" (de sidste to er nogle hardware egenskaber der påvirker udførselstiden væsentligt). Alle eksperimenterne svarer til sorteringer af 300.000 tilfældige elementer.

• threshold.pdf

Det ses på henholdsvis side 1 og 5 af threshold.pdf at for både MergeSort og QuickSort opnås den bedste udførselstid når man skifter over til InsertionSort ved problemer af størrelse 10-15 elementer. I de efterfølgende eksperimenter sker skriftet ved 10 elementer.

I nedenstående plots ses en sammenligning af udførselstiden (y-aksen) for InsertionSort, MergeSort, HeapSort, og QuickSort når problemstørrelsen vorkser (x-aksen). Desuden vises plots for antal sammenligninger, "cache faults", og "branch mispredictions" for de fire algoritmer.

Målt	Med InsertionSort	Uden InsertionSort
Tid	time5.pdf	time4.pdf
Sammenligninger	comps5.pdf	comps4.pdf
Cache faults	cache5.pdf	cache4.pdf
Branch mispredictions	mispred5.pdf	mispred4.pdf

Af time5.pdf fremgår det klart at InsertionSort's O(n²) udførselstid gør InsertionSort meget langsommere end de øvre algoritmer der har en udførselstid på O(n log n).

Blandt algoritmerne med O(n log n) udførselstid fremgår det tydeligt af time4.pdf at HeapSort er den langsomste. MergeSort og QuickSort har ca. den samme udførselstid, selvom QuickSort udfører ca 25% flere sammenligninger end MergeSort, jvf comps4.pdf. På mispred4.pdf ses at MergeSort også medfører 60% færre branch mispredictions end QuickSort, hvilket også skulle være med til at gøre QuickSort langsommere. At QuickSort så ikke taber så meget til MergeSort, skyldes at antal cache faults for QuickSort er væsentligt lavere end for MergeSort, jvf cache4.pdf, hvilket skyldes at QuickSort ikke kopierer data mellem to arrays modsat MergeSort der flytter data mellem to arrays under fletningerne i de rekursive kald.

Eksperimenterne viser klart at InsertionSort ikke kan anvendes for store data mængder. Heapsort er en konstant faktor langsommere end MergeSort og QuickSort. MergeSort og QuickSort har begge ca. samme udførselstid - men p.g.a forskellige egenskaber ved algoritmerne.

Tak

Ovenstående eksperimenter er udført af Gabriel Moruz i februar 2006. Implementation var i C og eksperimenterne blev lavet på en Athlon 2GHz med 1Gb RAM.

---