Data Structures, Algorithms, & Applications in C++
Shell Sort
Copyright 2004 Sartaj Sahni
Let a1,
...,
an be a sequence of
n elements. Elements
ai
and aj,
i <
j, are inverted iff
ai >
aj. The number of pairs
(i,j) such that
ai
and aj are inverted is the inversion number
of the element sequence.
Exercise 18.46 shows that the inversion number of an unsorted sequence
in O(n2) while that of
a sorted sequence is 0.
Consequently, sort-methods such as those of
Chapter 2, which reduce the inversion number by at most one
each time two elements are compared,
must take O(n2)
time to sort n elements.
Asymptotically faster sort methods are possible only if we
can reduce the inversion number by more than
Omega(1) following a comparison. The sort method due to
Donald Shell and known as Shell Sort compares elements
that are far apart rather than adjacent pairs of elements in an
attempt to make larger reductions in the inversion number.
For example, suppose we are sorting the sequence 5, 4, 3, 2, 1.
By comparing and swapping the adjacent pair (5, 4), as is done in bubble sort,
the inversion number is reduced by 1. However, when we compare and swap the
pair (5, 1), the inversion number reduces by 4.
In Shell sort, we use a sequence of diminishing increments
s1 > s2 >
s3 ...
sq = 1.
(Because of this, Shell sort is also known as
diminishing increment sort.)
For any increment x, we view the sequence
a[0:n-1] to be sorted
as being comprised of several subsequences.
The first is a[0],
a[0+x],
a[0+2x], ...;
the second is
a[1],
a[1+x],
a[1+2x], ...;
the third is
a[2],
a[2+x],
a[2+2x], ...; etc.
These subsequences are comprised of elements that are
x units apart in the array.
Each subsequence is sorted using insertion sort and then the
process is repeated using the next increment.
Since the last increment is 1,
a[0:n-1] has only
one subsequence when the last increment is used.
This subsequence is a[0],
a[1],
a[2], ...
Performing an insertion sort in this subsequence guarantees
that the result is sorted. The insertion sorts done with the
earlier increments allow elements to move toward their
final spots by making large jumps.
The net result is a faster sort than when we simply use insertion
sort. Notice that insertion sort is identical to shell sort
when the increment sequence is just 1.
Suppose we use the increment sequence 3, 1 to sort the elements
5, 4, 3, 2, 1. For the increment 3, the subsequences are
5, 2; 4, 1; and 3.
Sorting these subsequences using the insertion sort method
yields 2, 1, 3, 5, 4.
The next and final increment to use is 1.
Sorting with this increment results in the sorted sequence 1, 2, 3, 4, 5.
Although any diminishing sequence of increments (with the last one being 1)
can be used,
the performance of Shell sort depends acutely on the particular
increment sequence
that is used. Donald Knuth's book The art of computer programming::Sorting
and searching, volume 3, 2nd Edition,
Addison-Wesley, 1998 contains a discussion of the asymptotic complexity
of Shell sort using various increment sequences. An empirical
evaluation appears in the paper ``Empirical results on the running time
of Shellsort,'' by M. Weiss, Computer Journal, 1991, 88-91.
The complexity of Shell sort is O(n1.5)
when the increment sequence is of the form
si = 2t-i-1
for t = floor(log2n) and
0 <= i <= t as well as when the sequence is derived in
the following way: start with an increment of n/2; to get the next increment,
divide the current increment by 2, if the result is even, add 1 to make
the increment odd; continue until the increment becomes 1.
Weiss has observed that the observed performance is better when
the next increment is obtained by dividing by 2.2 rather than by 2.
The code for Shell sort using the divide by 2.2 strategy to generate
succeeding increments is given below.
public class ShellSort
{
template
void shellSort(T a[], int n)
{// Sort a[0:n-1] using Shell sort.
int incr = n / 2; // initial increment
while (incr >= 1)
{// insertion sort all sequences spaced by incr
for (int i = incr; i < a.length; i++)
{// insert a[i] into a[i - incr], a[i - 2*incr], ...
T insertElement = a[i];
int j;
for (j = i - incr;
j >= 0 && insertElement < a[j];
j -= incr)
a[j + incr] = a[j];
a[j + incr] = insertElement;
}
// reduce increment by a factor of 2.2
if (incr == 2)
incr = 1; // last increment must be 1
else
incr = (int) (incr / 2.2);
}
}
}