Samplesort
Samplesort er en sorteringsalgoritme som er en splitt og hersk-algoritme, og som ofte blir brukt i parallelle prosesseringssystemer.[1] 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.[2] 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 rediger
- ^ «Samplesort using the Standard Template Adaptive Parallel Library» (PDF). Texas A&M University.
- ^ «Bucket and Samplesort». Arkivert fra originalen 13. desember 2016. Besøkt 29. januar 2017.
Denne artikkelen er en spire. Du kan hjelpe Wikipedia ved å utvide den.