Java Reference
In-Depth Information
FIGURE 8-15
The subarrays of Figure 8-14 after each is sorted, and the array
that contains them
4
7
9
17
10
6
8
16
15
1
11
12
3
4
6
1
7
8
3
9
15
11
10
16
12
17
0
1
2
3
4
5
6
7
8
9
10
11
12
Dividing the current separation, 3, by 2 results in 1. Therefore, the final step is simply an
ordinary insertion sort of the entire array. This last step will sort the array regardless of what we
have done to it beforehand. Thus, Shell sort will work if you use any sequence of index separations,
as long as the last one is 1. But not just any sequence will make the Shell sort efficient, as you will
see in Segment 8.25.
Question 5
Apply the Shell sort to the array 9 8 2 7 5 4 6 3 1, with index separations
of 4, 2, and 1. What are the intermediate steps?
8.24
The heart of the Shell sort is the adaptation of the insertion sort to work on a subarray of equally
spaced entries. By combining and modifying the two algorithms that describe the insertion sort, as
given in Segment 8.11, we obtain the following method that sorts array entries whose indices are
separated by an increment of
space
.
/** Sorts equally spaced entries of an array into ascending order.
@param a an array of Comparable objects
@param first the integer index of the first array entry to
consider; first >= 0 and < a.length
@param last the integer index of the last array entry to
consider; last >= first and < a.length
@param space the difference between the indices of the
entries to sort */
private static
<T
extends
Comparable<?
super
T>>
void
incrementalInsertionSort(T[] a,
int
first,
int
last,
int
space)
{
int
unsorted, index;
for
(unsorted = first + space; unsorted <= last;
unsorted = unsorted + space)
{
T nextToInsert = a[unsorted];
for
(index = unsorted - space; (index >= first) &&
(nextToInsert.compareTo(a[index]) < 0);
index = index - space)
{
a[index + space] = a[index];
}
// end for
a[index + space] = nextToInsert;
}
// end for
}
// end incrementalInsertionSort
