Difference between revisions 18635981 and 18654952 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)
But since data are presorted by the preceding steps (''h'' = 3, 7, 31, ...), only a few insertion sort steps are sufficient. 
The exact number depends on the sequence of ''h'' values (denoted as ''h''-sequence). The ''h''-sequence above is just one of several possible.


* ([[Vaughan Pratt|Pratt]])  With the ''h''-sequence 1, 2, 3, 4, 6, 8, 9, 12, 16, ..., 2<sup>''p''</sup>3<sup>''q''</sup>, ... Shellsort needs O(''n''·log(''n'')<sup>2</sup>) steps for sorting a sequence of length ''n''.

* ([[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'', in the worst case.  ''Empirically'' the ''average'' case seems to be O(''n''<sup>5/4</sup>).

* ([[Donald Knuth|Knuth]]) With the ''h''-sequence 1, 4, 13, 40, 121, ..., 3''h''<sub>''s''-1</sub> + 1 = (3<sup>''s''</sup> - 1)/2, ... ([[On-Line Encyclopedia of Integer Sequences|OEIS]] sequence [http://www.research.att.com/projects/OEIS?Anum=A003462 A003462])  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), ([[On-Line Encyclopedia of Integer Sequences|OEIS]] sequence [http://www.research.att.com/projects/OEIS?Anum=A033622 A033622])  Shellsort needs O(''n''<sup>4/3</sup>) steps for sorting a sequence of length ''n'', in the worst case.  ''Empirically'' the ''average'' case seems to be O(''n''<sup>7/6</sup>) – a very good asymptotic average performance.  Knuth recomends this choice, except perhaps for small values of ''n''.    

:<math>
  h_s=
  \left\{
   \begin{matrix}
    9 \cdot 2^s - 9 \cdot 2^{s/2} + 1 &     \mbox{if }s\mbox{ is even}  \\
    8 \cdot 2^s - 6 \cdot 2^{(s+1)/2} + 1 & \mbox{if }s\mbox{ is odd} \\
   \end{matrix}
  \right.
 </math>

([[Insertion sort]]) The worst case of Shell sort is the basic insertion sort (using a single ''h''-step of 1), which requires O(''n''&sup2;) comparisons and exchanges.

An easily computable ''h''-sequence for Shell sort, and a really poor one, is the [[Fibonacci number|Fibonacci Sequence]] (1, 2, 3, 5, 8, 13, 21, ... ),([[On-Line Encyclopedia of Integer Sequences|OEIS]] sequence [http://www.research.att.com/projects/OEIS?Anum=A000045 A000045])  which increases step size in a natural progression.

The best known sequence of increments in terms of the average number of comparisons made is 1, 4, 10, 23, 57, 132, 301, 701 (further increments unknown) ([[On-Line Encyclopedia of Integer Sequences|OEIS]] sequence [http://www.research.att.com/projects/OEIS?Anum=A102549 A102549]) [http://www-zo.iinf.polsl.gliwice.pl/~mciura/shellsort.pdf]. The increments were found empirically; no formula for them is known.

(contracted; show full)
[[de:Shellsort]]
[[es:Ordenación Shell Sort]]
[[it:Shell sort]]
[[lt:Kevalo r&#363;&#353;iavimo algoritmas]]
[[nl:Shellsort]]
[[ja:&#12471;&#12455;&#12523;&#12477;&#12540;&#12488;]]
[[zh:&#24076;&#23572;&#25490;&#24207;]]