ShellSort, named after its inventor, Donald Shell, relies upon
the fact that insertion sort does very well if the array is
nearly sorted. Another way of saying this, is that insertion sort does
well if it does not have to move each item "too far".
The idea is to repeatedly do
insertion sort on all elements at fixed, decreasing distances apart:
hk, hk-1, ..., h1= 1.
The choice of increments turns out to be crucial.
It turns out that a good choice of increments are these:
h1 = 1, h2 = 3, h3 = 7, ..., hk= 2k–1
These increments are termed the Hibbard increments. The original
increments suggested by the algorithm's inventor were simple powers
of 2, but the Hibbard increments do provably much better.
Psuedo-code
The psuedo-code for shellSort using the Hibbard increments is this:
find k0 so that 2k0- 1 < size
for (k = k0; k > 0; --k) { // work from larger incements to smaller
inc = 2k- 1
for (i = 0; i < inc; ++i) {
Sort the elements ( a[i], a[i+inc], a[i+2*inc], ...) with insertionSort
}
}
The fact that the last increment in the sequence is 1 means
that regular insertion sort is done at the last step and therefore
the array is guaranteed to be sorted by this procedure.
The point is that when the increments are larger, there are
fewer elements and they will be moved further than simply interchanging
adjacent elements.
At the last step, we do regular insertion sort and hopefully the
array is "nearly sorted" which makes insertion sort come close to
its best case behavior of running in linear time.
The notion that this is an improvement initially seems far-fetched. There are
two enclosing for loops to get to an insertion sort, thus
this algorithm has 4 enclosing for loops,
with insertion-sort as the basis.
Code
In our actual Java code, we permit the user to specify the increments
which the algorithms uses. If none are specified the Hibbard increments
are used by default.
Here is the code:
( click to show )
Actual code
To get a sense of how this is working,
You can test shell sort in mainShowSorts
by simply setting the
which = show.Algorithms.SHELL
You can compare the behavior using a different set of
increments by creating your own List
of increments. For example, to use Shell's original increments
(1, 2, 4, 8, ...), add this code prior to the call.
which = show.Algorithms.SHELL;
size = 9;
A = new Integer[size];
for (int i = 0; i < A.length; ++i) {
A[i] = 9 - i;
}
LinkedList<Integer> shellIncrements = new LinkedList<Integer>();
for (int inc = 1; inc < A.length; inc = 2 * inc) {
shellIncrements.add(inc);
}
show.Algorithms.setShellSortIncrements(shellIncrements);
Empricial Comparisons
The two valuable empirical measures of an sorting algorithm are
how long it takes to execute (real time) and home many operations,
i.e. comparisons and data movements, that it requires (abstract time).
The following two main programs are written to compare up to 3
different sorting algorithms.
One has to change the contents of the "Sorts" inner class
and set appropriate values of NUM (array size) and NUM_TRIALS.
Both are illustrated using selectionSort, insertionSort and shellSort.
Timing Comparison: mainTimeSorts
( click to show )
Counting Comparison: mainCountSorts
( click to show )
ShellSort Analysis
It is relatively easy to argue that this new version is still
O(n2):
let hk stand for the kth increment,
which corresponds to the variable gap in
our implementation
let n = the array size
the two inner loops perform an insertion sort on at most
n/hk elements, costing
O((n/hk)2)
the next loop out goes hk times, costing
O(hk*(n/hk)2)
= O(n2/hk)
Using the order constant, C, and considering the
the outermost loop, this then becomes an upper bound:
∑k=1,2,… C * (n2/hk) = C * n2 * ∑k=1,2,… (1/hk)
= C * n2 * ∑k=1,2,… (1/(2k–1))
= C * n2 * ( 1 + ∑k=2,… (1/(2k–1)) )
≤ C * n2 * ( 1 + ∑k=2,… (1/(2k–1)) ) ( 2k–1 > 2k–1 )
≤ C * n2 * ( 1 + 1 ) = 2 * C * n2
In particular, we can guarantee quadratic time when the increments are based on
a power sequence, such as straight powers of 2. However, the Hibbard increments are special
in that these values guarantee a sub-quadratic worst-case time of
O(n3/2).
As can be expected, the proof of this fact is quite a bit more difficult.
The textbook remarks that the average case time is unknown although
conjectured to be
O(n6/5). The textbook
also mentions other increment sequences which have been studied and
seen to produce even better performance.
Stability
Shell sort is stable precisely because insertion sort is stable,
and we simply do repeated insertion sorts on the array.