Shellsortering
Shellsortering er en form for på-stedet sammenligningsortering som kan betraktes som en generalisering av enten boblesortering eller innstikksortering. Metoden starter ved å sortere par av elementer som er langt fra hverandre, og deretter progressivt redusere gapet mellom de sammenlignede elementer. Ved å begynne på elementer som er langt fra hverandre, kan den flytte enkelte elementer som er utenfor rekkefølge inn i sin rette posisjon raskere enn en enkel naboutveksling. Donald Shell publiserte den første versjonen i 1959. Kjøretiden til algoritmen er svært avhengig av gapsekvensen den bruker. For mange praktiske verdier, er deres tidskompleksitet et åpent problem.[1][2][3]
Referanser rediger
- ^ Shell, D. L. (1959). «A High-Speed Sorting Procedure» (PDF). Communications of the ACM. 2 (7): 30–32. doi:10.1145/368370.368387. Arkivert fra originalen (PDF) 30. august 2017. Besøkt 29. januar 2017.
- ^ «Shell sort». National Institute of Standards and Technology. Besøkt 17. juli 2007.
- ^ Knuth, Donald E. (1997). «Shell's method». The Art of Computer Programming. Volume 3: Sorting and Searching (2nd utg.). Reading, Massachusetts: Addison-Wesley. s. 83–95. ISBN 0-201-89685-0.