Samplesort

Samplesort er en sorteringsalgoritme som er en splitt og hersk-algoritme, og som ofte blir brukt i parallelle prosesseringssystemer. Konvensjonelle splitt-og-hersk algoritmer deler listen eller tabellen opp i under-intervaller, som blir sortert enkeltvis og deretter konkatinert med hverandre. Hvis tabellen er ikke-uniformt distribuert, kan ytelsen til disse sorteringsalgoritmene svekkes betydelig. Samplesort velger et utvalg av størrelse s fra sekvensen av n elementer, og bestemmer under-intervallenes størrelse ved å sortere utvalget i m like store intervaller. Samplesort ble i 1970 beskrevet i en avandling, "Samplesort: A Sampling Approach to Minimal Storage Tree Sorting", av W. D. Frazer og A. C. McKellar.

Referanser

Kategori:Sorteringsalgoritmer