Shellsort is a simple extension of insertion sort which gains speed
by allowing exchanges of elements that are far apart.
The idea is to rearrange the array to give it the property that every
**h**^{th} element (starting anywhere) yields a
sorted array. Such an array is said to be **h-sorted**.

By **h**-sorting for some large values of
**h**, we can move elements in the array long distances
and thus make it easier to **h**-sort for smaller values
of **h**. Using such a procedure for any sequence of values
**h** which ends in 1 will produce a sorted array.

1subtypeindexispositiverange1..N;2typesort_arrayisarray(index)ofinteger;34procedureshellsort (arr:inoutsort_array)5is6N : index := arr'LENGTH;7v, k : integer;8h : integer := 1;9begin1011-- build the first h value1213discreteh1 := 1in1..N14newh1 := 3*h1+115loop16h1 := 3*h1+1;17h := h1;18endloop;1920-- h-sort the array for h = ..., 121, 40, 13, 4 and finally 12122discretei := hinreverse2..h23newi := i/324loop25i := i/3;2627forjini+1..Nloop28v := arr(j);29k := j;3031discretel := k-iinreverse1..k-i32newl := l-i33loop34ifarr(k-i) <= vthen35exit;36endif;37arr(k) := arr(k-i);38k := k-i;39l := l-i;40ifk <= ithen41exit;42endif;43endloop;44arr(k) := v;45endloop;46endloop;47endshellsort;

[ Sourcefile ]

In our implementation, we use the increment sequence

h_{M} = 1, h_{M-1} = h_{M} * 3 + 1

which yields the following sequence:

..., 1093, 364, 121, 40, 13, 4, 1

The first discrete loop *(lines 13 to 18)* is used
to calculate the first value of h. (In fact,
because the discrete loop is exited when the value of h_{1}
is greater than N, it has to be divided by 3 to get the
starting h).

The second discrete loop runs over the above introduced increment sequence and performs the h-sorting of the array. (By building the new value of the loop variable immediately in the first statement of the loop body, we skip the first value in the increment sequence which is anyway to high, as mentioned above.)

Let us begin with a quote from Sedgewick's Algorithms [Sed88]:

[...] no one has been able to analyze the algorithm. [...] Not even the functional form of the running time for Shellsort is known.

But nevertheless, Sedgewick proposes the following property:

Shellsort never does more than N^{3/2}comparisons (for the above used increment sequence).

[Ott93, p. 88] [Sed88, p. 107]

[ Samples Overview | Bibliography | WOOP Project ]