Java Reference
In-Depth Information
A method to perform a Shell sort will invoke
incrementalInsertionSort
and supply any
sequence of spacing factors. For example, we might write the following method, using the spacing
that Segment 8.23 described:
public static
<T
extends
Comparable<?
super
T>>
void
shellSort(T[] a,
int
first,
int
last)
{
int
n = last - first + 1;
// number of array entries
for
(
int
space = n / 2; space > 0; space = space / 2)
{
for
(
int
begin = first; begin < first + space; begin++)
incrementalInsertionSort(a, begin, last, space);
}
// end for
}
// end shellSort
Question 6
Trace the steps that a Shell sort takes when sorting the following array into
ascending order: 9 6 2 4 8 7 5 3.
Since the Shell sort uses an insertion sort repeatedly, it certainly seems like much more work than using
only one insertion sort. Actually, however, it is not. Although we used an insertion sort several times instead
of just once, the initial sorts are of arrays that are much smaller than the original one, the later sorts are on
arrays that are partially sorted, and the final sort is on an array that is almost entirely sorted. Intuitively, this
seems good. But even though the Shell sort is not very complicated, its analysis is.
Since
incrementalInsertionSort
involves a loop and is called from within nested loops, the
Shell sort uses three nested loops. Often such algorithms are O(
n
3
), but it turns out that the worst-
case behavior of the Shell sort is still O(
n
2
). If
n
is a power of 2, the average-case behavior is
O(
n
1.5
). And if you tweak the spacing a bit, you can make the Shell sort even more efficient.
One improvement is to avoid even values of
space
. Figure 8-12 provided an example of the
subarrays when
space
was 6. The first subarray contained 10, 9, and 7, for instance. Later, after we
halved
space
, the first subarrray contained 7, 4, 9, 17, and 10, as Figure 8-14 shows. Notice that
these two subarrays have entries in common, namely the 10, 9, and 7. Thus, the comparisons that
you make when
space
is even will be repeated on the next pass when the increment is
space/
2.
To avoid this inefficiency, simply add 1 to
space
whenever it is even. This simple change results in
consecutive increments that have no factor in common. The worst-case behavior of the Shell sort is then
O(
n
1.5
). Other sequences for
space
result in even greater efficiencies, although the proof that this is the
case remains elusive. An improved Shell sort can be a reasonable choice for moderately large arrays.
Note:
The time efficiency of Shell sort
The Shell sort, as implemented in this chapter, is O(
n
2
) in the worst case. By adding 1 to
space anytime that it is even, you can improve the worst-case behavior to O(
n
1.5
).
8.26
Figure 8-16 summarizes the time efficiencies of the three sorting algorithms presented in this chapter.
Generally, the selection sort is the slowest algorithm. The Shell sort, by capitalizing on the best-case
behavior of the insertion sort, is the fastest.
