Difference between revisions 8522129 and 8522570 on enwiki

< previous diff
next diff >
Shell sort
'''Shell sort''' (or '''Shellsort''') is one of the oldest [[sorting algorithm|sorting algorithms]]. It was invented in 1959 by [[D. L. Shell|Donald L. Shell]] <nowiki>[</nowiki>[[#References|Sh]]<nowiki>]</nowiki>.
It is fast, easy to understand and easy to implement. 
However, its complexity analysis is a little more sophisticated.  
(contracted; show full)

([[Thomas Hibbard|Hibbard]]) With the ''h''-sequence 1, 3, 7, 15, 31, 63, 127, ..., 2<sup>''k''</sup> - 1, ... Shellsort needs O(''n''<sup>3/2</sup>) steps for sorting a sequence of length ''n''.

([[Donald Knuth|Knuth]]) With the ''h''-sequence 1, 4, 13, 40, 121, ..., 3''h''<sub>''s''-1</sub> + 1
, ... Shellsort needs ''FIXME'' = (3<sup>''s''</sup> - 1)/2, ... Shellsort needs O(''n''<sup>3/2</sup>) steps for sorting a sequence of length ''n''.

([[Robert Sedgewick|Sedgewick]]) With the ''h''-sequence 1, 5, 19, 41, 109, 209, ... (described below), Shellsort needs O(''n''<sup>4/3</sup>) steps for sorting a sequence of length ''n''.

:<math>
  h_s=
  \left\{
   \begin{matrix}
(contracted; show full)* [http://www.nist.gov/dads/HTML/shellsort.html Dictionary of Algorithms and Data Structures: Shellsort]

[[de:Shellsort]]
[[es:Ordenación Shell]]
[[nl:Shellsort]]
[[ja:&#12471;&#12455;&#12523;&#12477;&#12540;&#12488;]]

[[Category:Sort algorithms]]