Difference between revisions 7825054 and 7885294 on enwiki

'''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)
   \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 is the [[Fibonacci number|Fibonacci Sequence]] (1, 2, 3, 5, 8, 13, 21, ... ), which increases step size in a natural progression.
⏎
⏎
== Implementations ==

The following [[Java_programming_language|Java]] program sorts an array ''a'' from index position 0 through ''n''-1. The number of columns used for arranging data in each step is in array ''cols''. Thus, data are arranged in 1,391,376 columns in the first step and in one column in the last step. Note that essentially nothing is done if the number of columns ''h'' is larger than the number of data elements ''n''. Each column is sorted by insertion sort. First, data of the second row, beginning at ''i'' = ''h'', are sorted to the correct position in their column, then data of the third row (when ''i'' reaches value 2''h'') and so on.

=== Using a list of shell sizes ===

<pre>
void shellsort (int[] a, int n) {
    int i, j, k, h, v;
    int[] cols= {1391376, 463792, 198768, 86961, 33936, 13776, 4592,
                    1968, 861, 336, 112, 48, 21, 7, 3, 1};
    for (k=0; k<16; k++) {
        h=cols[k];
        for (i=h; i<n; i++) {
            v=a[i];
            j=i;
            while (j>=h && a[j-h]>v) {
                a[j]=a[j-h];
                j=j-h;
            }
            a[j]=v;
        }
    }
}</pre>

=== Using fibonacci numbers ===

<pre>
void shellsort (int[] a, int n) {
    int h=1, hh=1;

    while(hh<n) {
       // eg, h = 5, hh = 8
       hh=hh+h; // hh = 8 + 5 = 13
       h=hh-h;  // h = 13 - 5 = 8
    }

    while(hh > 1) {
        int i, j, v;
        for (i=h; i<n; i++) {
            v=a[i];
            j=i;
            while (j>=h && a[j-h]>v) {
                a[j]=a[j-h];
                j=j-h;
            }
            a[j]=v;
        }

        // eg, h = 8, hh = 13

        h = hh - h; // h = 13 - 8 = 5
        hh = hh - h; // hh = 13 - 5 = 8
    }
}</pre>

==References==
[Se]  R. Sedgewick: Algorithms. Addison-Wesley (1988)<br>
[Sh]  D.L. Shell: A high-speed sorting procedure. Communications of the ACM 2 (7), 30-32 (1959)

== External links ==
*[http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/shell/shellen.htm Detailed analysis of Shell sort]
* [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]]