Redigerer Shellsortering

'''Shellsortering''' er en form for [[På-stedet algoritme|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]].<ref name="Shell">{{Cite journal
  |url=http://penguin.ewu.edu/cscd300/Topic/AdvSorting/p30-shell.pdf
  |last=Shell
  |first=D. L.
  |title=A High-Speed Sorting Procedure
  |journal=Communications of the ACM
  |volume=2
  |issue=7
  |year=1959
  |pages=30–32
  |doi=10.1145/368370.368387
  |accessdate=2017-01-29
  |archivedate=2017-08-30
  |archiveurl=https://web.archive.org/web/20170830020037/http://penguin.ewu.edu/cscd300/Topic/AdvSorting/p30-shell.pdf
  }}</ref><ref>{{Cite web
  |title=Shell sort
  |publisher=National Institute of Standards and Technology
  |url=https://xlinux.nist.gov/dads/HTML/shellsort.html
  |accessdate=2007-07-17 }}</ref><ref name="Knuth">{{Cite book
  |last=Knuth
  |first=Donald E. |author-link=Donald Knuth
  |title=The Art of Computer Programming. Volume 3: Sorting and Searching
  |edition=2nd
  |publisher=Addison-Wesley
  |location=Reading, Massachusetts
  |year=1997
  |pages=83–95
  |chapter=Shell's method
  |isbn=0-201-89685-0}}</ref>


==Referanser==
<references/>

[[Kategori:Sorteringsalgoritmer]]