Advanced Sorting - Advanced Topics in Java: Core Concepts in Data Structures - page 276

Similarly, there is only one element before num[5] that is three away, that is, num[2] . So, when we come to process
num[5] , we can assume that num[2] , by itself, is sorted. We insert num[5] relative to num[2] so that num[2] and num[5]
are sorted. Similar remarks apply to num[3] and num[6] .
When we get to num[7] , the two items before num[7] ( num[1] and num[4] ) are sorted. We insert num[7] such that
num[1] , num[4] , and num[7] are sorted.
When we get to num[8] , the two items before num[8] ( num[2] and num[5] ) are sorted. We insert num[8] such that
num[2] , num[5] , and num[8] are sorted.
When we get to num[9] , the two items before num[9] ( num[3] and num[6] ) are sorted. We insert num[9] such that
num[3] , num[6] , and num[9] are sorted.
When we get to num[10] , the three items before num[10] ( num[1] , num[4] , and num[7] ) are sorted. We insert
num[10] such that num[1] , num[4] , num[7] , and num[10] are sorted.
And so on. Starting at h+1 , we step through the array processing each item with respect to previous items that are
multiples of h away.
In the example, when h = 3, we said we must sort elements (1, 4, 7, 10, 13, 16), (2, 5, 8, 11, 14), and (3, 6, 9, 12, 15).
This is true, but our algorithm will not sort items (1, 4, 7, 10, 13, 16), followed by items (2, 5, 8, 11, 14) followed by
items (3, 6, 9, 12, 15).
Rather, it will sort them in parallel by sorting the pieces in the following order: (1, 4), (2, 5), (3, 6), (1, 4, 7), (2, 5, 8),
(3, 6, 9), (1, 4, 7, 10), (2, 5, 8, 11), (3, 6, 9, 12), (1, 4, 7, 10, 13), (2, 5, 8, 11, 14), (3, 6, 9, 12, 15), and finally (1, 4, 7, 10, 13, 16).
This may sound more difficult, but it is actually easier to code, since we merely need to step through the array starting
at h+1 .
The following will perform an h -sort on A[1..n] :
public static void hsort(int[] A, int n, int h) {
for (int k = h + 1; k <= n; k++) {
int j = k - h;
int key = A[k];
while (j > 0 && key < A[j]) {
A[j + h] = A[j];
j = j - h;
}
A[j + h] = key;
}
} //end hsort
Alert readers will realize that if we set h to 1, this becomes insertion sort.
Programming note : If we want to sort A[0..n-1] , we must change the for statement to the following and use
j >= 0 in the while statement:
for (int k = h; k < n; k++)
Given a series of increments h t , h t-1 , ..., h 1 = 1, we simply call hsort with each increment, from largest to smallest,
to effect the sort.
We write Program P9.5, which reads numbers from the file shell.in , sorts them using Shell sort (with three
increments—8, 3 and 1), and prints the sorted list, ten numbers per line.
Program P9.5
import java.io.*;
import java.util.*;
public class ShellSortTest {
final static int MaxNumbers = 100;
public static void main (String[] args) throws IOException {