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 hth 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.
1 subtype index is positive range 1..N; 2 type sort_array is array(index) of integer; 3 4 procedure shellsort (arr: in out sort_array) 5 is 6 N : index := arr'LENGTH; 7 v, k : integer; 8 h : integer := 1; 9 begin 10 11 -- build the first h value 12 13 discrete h1 := 1 in 1..N 14 new h1 := 3*h1+1 15 loop 16 h1 := 3*h1+1; 17 h := h1; 18 end loop; 19 20 -- h-sort the array for h = ..., 121, 40, 13, 4 and finally 1 21 22 discrete i := h in reverse 2..h 23 new i := i/3 24 loop 25 i := i/3; 26 27 for j in i+1..N loop 28 v := arr(j); 29 k := j; 30 31 discrete l := k-i in reverse 1..k-i 32 new l := l-i 33 loop 34 if arr(k-i) <= v then 35 exit; 36 end if; 37 arr(k) := arr(k-i); 38 k := k-i; 39 l := l-i; 40 if k <= i then 41 exit; 42 end if; 43 end loop; 44 arr(k) := v; 45 end loop; 46 end loop; 47 end shellsort;
[ Sourcefile ]
In our implementation, we use the increment sequence
hM = 1, hM-1 = hM * 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 h1 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 N3/2 comparisons (for the above used increment sequence).
[Ott93, p. 88] [Sed88, p. 107]
[ Samples Overview | Bibliography | WOOP Project ]