Difference between revisions 24112776 and 24113168 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)    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
    }

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

        // e.g., h = 8, hh = 13

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

The squares of Fibonacci numbers (1, 4, 9, 25, ...) make an even better sequence.

==References==
[Kn] Donald E. Knuth: ''Sorting and Searching'', vol. 3 of ''[[The Art of Computer Programming]]'', second edition. Addison-Wesley (1998). ISBN 0-201-89685-0<br>
[Se] Robert Sedgewick: ''Algorithms''. Addison-Wesley (1988)<br>
[Sh] Donald 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]

[[Category:Sort algorithms]]

[[de:Shellsort]]
[[es:Ordenación Shell Sort]]
[[it:Shell sort]]
[[lt:Šelo rūšiavimo algoritmas]]
[[nl:Shellsort]]
[[ja:シェルソート]]
[[pt:Shell sort]]
[[zh:希尔排序]]