Shellsortering

Fra Wikipedia, den frie encyklopedi
Hopp til: navigasjon, søk

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 | rediger kilde]

  1. ^ Shell, D. L. (1959). «A High-Speed Sorting Procedure» (PDF). Communications of the ACM. 2 (7): 30–32. doi:10.1145/368370.368387. 
  2. ^ «Shell sort». National Institute of Standards and Technology. Besøkt 17. juli 2007. 
  3. ^ 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.