Difference between revisions 18654952 and 18718041 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) ... (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 recom
mends 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} \\
(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;]]