Difference between revisions 11761130 and 11761535 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)

== Analysis ==

The correctness of the algorithm follows from the fact that in the last step (with ''h'' = 1) an ordinary insertion sort is performed on the whole array. 
But since data are presorted by the preceding steps (''h'' = 3, 7, 
231, ...), 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.

(contracted; show full)
([[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 ==


=== Using a list of shell sizes ===⏎
⏎
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 4356424, 1355339, 543749, 213331, 84801, 27901,
                    119689, 861, 336, 112, 484711, 1968, 815, 277, 97, 231, 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>

=== Using a list of shell sizes in C Edit By Z80user ===

table[]    is table to sort
table_size is ...
<pre>
int tabla[]= {10,9,8,7,6,5,4,3,2,1};
int cols[]= {1391376,463792,198768,86961,33936,13776,4592,1968,861,336,112,48,21,7,3,1};
int table_size=10;                         // change it
int n,m,h,j,v;

for (n=0;n<16;n++)
    {
    h=cols[n];
    for (m=0;m<table_size;m++)
        {
        v=tabla[m];
        j=m;
        while (j>=h && tabla[j-h]>v)
            {
            tabla[j]^=tabla[j-h]; // Swap data 
            tabla[j-h]^=tabla[j]; // I Think java also need this change
            tabla[j]^=tabla[j-h]; // but i don`t have compiler of java
            j=j-h;
            }
        }
    tabla[j]=v;
    }
</pre>The squares of Fibonacci numbers (1, 4, 9, 25, ...) make an even better sequence.
Implementation is left as an exercise to the reader.

==References==
[Kn]  D.E. Knuth: Sorting and Searching, vol. 3 of The Art of Computer Programming. Addison-Wesley (1973)<br>
[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]]
[[lt:Kevalo r&#363;&#353;iavimo algoritmas]]
[[nl:Shellsort]]
[[ja:&#12471;&#12455;&#12523;&#12477;&#12540;&#12488;]]
[[zh:&#24076;&#23572;&#25490;&#24207;]]
[[Category:Sort algorithms]]