Softpanorama (slightly skeptical) Open Source Software Educational Society

May the source be with you, but remember the KISS principle ;-) Softpanorama Search

Shellsort

Shellsort is the oldest fast sorting algorithms. It was proposed by Shell (1959)  and still in many cases holds its own against other competitors due to its simplicity and the ability to use partially ordered sequences. Knuth found that the shall sort efficiency is close to N(log N)² and N^1.25. A more complicated function of the form is involved for some sequences. But please note that shell sort usually works very well on real data, better then on random sequences. For this reason it is often preferred to quicksort that is fragile algorithms that can perform quadratic on some practically important cases. The other alternative is mergesort and heapsort. Both sort a file of N elements in time proportional to N log N, no matter what the input.

We can consider shell sort to be an elegant extension of insertion sort that gains speed by allowing exchanges of elements that are far apart. It sorts slices with a particular step h. Such a file is said to be h-sorted. If we first h-sort a file using a large value of h, elements move long distances and the efficiency of h-sorting for smaller values of  h improves.  When you get to the h=1 you implement a regular insertion sort and thus get a sorted file.

But the details of this elegant idea are non-trivial. First of all the result of h-sorting a file that is already k-sorted is a file became both h-and k-sorted. While any sequence of values of h will work as long as ends with h₁ = 1, some sequences  are clearly better than others.

• The obvious choice is to use the half of the size of the array, then quarter, etc, but it is a bad choice. Using stain powers of 2 (1, 2, 4, 8, 16, 32, 64, etc is even worth.
• Hibbard suggested a better sequence; 1, 3, 7,...2^k - 1. 
• The sequence 1, 4, 13, 40, 121, 364,1093, 3280, 9841 ... was recommended by Knuth in 1969. It is easy to compute (start with 1, generate the next increment by multiplying by 3 and adding 1) and leads to a relatively efficient sort, even for moderately large files.
•  Robert Sedgewick proposed sequence 1, 8, 23, 77, 281, 1073, 4193, 16577..., ( 4ⁱ⁺¹ + 3·2ⁱ + 1 ) for i > 0 that he claims is faster then Knuth's 20-30%
• Some subsets of Fibonacci numbers and prime numbers might be good candidates too.

Recommended Links

---

In case of broken links please try to use Google search. If you find the page please notify us about new location

9.4 Shellsort

• Invented by David Shell. Also called as Diminishing Increments sort.

  REF.

  Shell. A High-speed Sorting Procedure.
  Communications of the ACM, Volume 2, Number 7, pp. 30-32,1959.

   

• The algorithm works by comparing elements that are distant; the distance between comparisons decreases as the algorithm runs until the last phase, in which adjacent elements are compared.
• Uses an increment sequence, h₁, h₂,..., h_t. Any increment sequence will do as long as h₁ = 1, however some choices are better than others.
• After a phase, using some increment h_k, for every i, we have
  a[i] a[i + h_k]   whenever   i + h_k n
  That is, all elements spaced h apart are sorted and the sequence is said to be
  h_k - sorted
• The following shows an array after some phases in shellsort.

  OriginalArray	81	94	11	96	12	35	17	95	28	58	41	75	15
  After5-Sort	35	17	11	28	12	41	75	15	96	58	81	94	95
  After3-Sort	28	12	11	35	15	41	58	17	94	75	81	96	95
  After1-Sort	11	12	15	17	28	35	41	58	75	81	94	95	96

• An important property of Shellsort:
  • A sequence which is h_k - sorted that is then h_{k - 1} - sorted will remain h_k - sorted.
  This means that work done by early phases is not undone by later phases.

   

• The action of an h_k - sorted is to perform an insertion sort on h_k independent subarrays.

   

• Shell suggested the increment sequence
  h_t = k;h_k =
  For various reasons, this turns out to be a poor choice of increments. Hibbard suggested a better sequence; 1, 3, 7,...2^k - 1.
• Worst-case running time of Shellsort, using shell's increments, has been shown to be O(n²)
• Worst-case running time of Shellsort, using Hibbard's increments, has been shown to be O(n^1.5)
• Sedgewick has proposed several increment sequences that give an O(n worst-case running time.
• Showing the average -case complexity of shellsort has proved to be a formidable theoretical challenge.
• Far more details, refer [weiss94, chapter 7, 256-260] and [knuth 73].

Shellsort

Shellsort is one of the oldest sorting algorithms, named after its inventor D.L. Shell (1959) [Sh]. It is fast, easy to understand and easy to implement. However, its complexity analysis is a little more sophisticated. Idea The idea of Shellsort is the following: arrange the data sequence in a two-dimensional array sort the columns of the array The effect is that the data sequence is partially sorted.

The process above is repeated, but each time with a narrower array, i.e. with a smaller number of columns. In the last step, the array consists of only one column.

In each step, the sortedness of the sequence is increased, until in the last step it is completely sorted. However, the number of sorting operations necessary in each step is limited, due to the presortedness of the sequence obtained in the preceding steps.

Example: Let  3 7 9 0 5 1 6 8 4 2 0 6 1 5 7 3 4 9 8 2  be the data sequence to be sorted. First, it is arranged in an array with 7 columns (left), then the columns are sorted (right):  

3 7 9 0 5 1 6 8 4 2 0 6 1 5 7 3 4 9 8 2

3 3 2 0 5 1 5 7 4 4 0 6 1 6 8 7 9 9 8 2

Data elements 8 and 9 have now already come to the end of the sequence, but a small element (2) is also still there. In the next step, the sequence is arranged in 3 columns, which are again sorted:

3 3 2 0 5 1 5 7 4 4 0 6 1 6 8 7 9 9 8 2

0 0 1 1 2 2 3 3 4 4 5 6 5 6 8 7 7 9 8 9

 Now the sequence is almost completely sorted. When arranging it in one column in the last step, it is only a 6, an 8 and a 9 that have to move a little bit to their correct position.

Implementation

Actually, the data sequence is not arranged in a two-dimensional array, but held in a one-dimensional array that is indexed appropriately. For instance, data elements at positions 0, 5, 10, 15 etc. would form the first column of an array with 5 columns.

The "columns" obtained by indexing in this way are sorted with Insertion Sort, since this method has a good performance with presorted sequences.

The following 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 1391376 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 2h) etc.  

Algorithm Shellsort

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; } } }

Shellsort Applet

This applet illustrates Shellsort with various increment sequences. Select an increment sequence (they are arranged roughly from best to worst). Then select either random or reverse input. (Worst-case input is planned for the future). Then enter N.

You can run the program to see how each phase rearranges the data. Each click of the button executes the next phase and generates a picture made popular in several animation systems (and also Bob Sedgewick's books). A diagonal line is sorted input. You need a sufficiently small N (at most 325 in a typical window) and you need to check the stop after each pass box. A running count of comparisons and data moves is kept. You can also let the program run and get these counts by not checking the box. But then you don't get the picture.

Future plans will include additional and also arbitrary increment sequences, worst-case data, and perhaps an animation (instead of step by step clicking) if I ever figure out this language.

Shellsort This page contains some run time data. It' unclear how the test sets were generated. If they are random they are perfect for quicksrt and this is not a fair exaqmple

Analysis of Shellsort and Related Algorithms by Robert Sedgewick Presented at Fourth Annual European Symposium on Algorithms. Barcelona, September, 1996

This paper surveys the theoretical and empirical studies that have been done over the past four decades on the Shellsort algorithm and its variants. The discussion includes: upper bounds, including linkages to number-theoretic properties of the algorithm; lower bounds on Shellsort and Shellsort-based networks; average-case results; proposed probabilistic sorting networks based on the algorithm; and a list of open problems.

• Extended Abstract ( .ps .pdf)
• C code (shellsort)
• C code (performance driver)
• Java animations of algorithms

Comments, questions, suggestions:

   mail rs@cs.princeton.edu 

Improving Shellsort Through Evolution

Shellsort is an in-place sorting algorithm. It is described in many data structures books, including [] and []. The implementation I used is shell.lisp. Notice that the comparison function (lessp) & the copy function (copyfn) are parameters so that other functions in the program may use this implementation of Shellsort to track the cost of a sequence of increments.

In a sense, Shellsort is a parameterized family of sorting algorithms. The parameter is a sequence of integral increments. Each increment is used for one pass through the list being sorted. The increments begin with their largest & decrease in size each time through the algorithm. The final increment must be 1.

The efficiency of Shellsort depends on the sequence of increments. The efficiency has proven difficult to analyze. The most efficient sequence of increments known was proposed by Sedgewick.

Shellsort (implementation in several languages)