1 import java.util.ArrayList;
2
3 /**
4 The sort method of this class sorts an array, using the Shell
5 sort algorithm.
6 */
7 public class ShellSorter
8 {
9 /**
10 Sorts an array, using selection sort.
11 @param a the array to sort
12 */
13 public static void sort(int[] a)
14 {
15 // Generate the sequence values
16 ArrayList<Integer> columns = new ArrayList<Integer>();
17 int c = 1;
18 while (c < a.length)
19 {
20 columns.add(c);
21 c = 3 * c + 1;
22 }
23
24 // For each column count, sort all columns
25 for (int s = columns.size() - 1; s >= 0; s--)
26 {
27 c = columns.get(s);
28 for (int k = 0; k < c; k++)
29 {
30 insertionSort(a, k, c);
31 }
32 }
33 }
34
35 /**
36 Sorts a column, using insertion sort.
37 @param a the array to sort
38 @param k the index of the first element in the column
39 @param c the gap between elements in the column
40 */
41 public static void insertionSort(int[] a, int k, int c)
42 {
43 for (int i = k + c; i < a.length; i = i + c)
44 {
45 int next = a[i];
46 // Move all larger elements up
47 int j = i;
48 while (j >= c && a[j - c] > next)
49 {
50 a[j] = a[j - c];
51 j = j - c;
52 }
53 // Insert the element
54 a[j] = next;
55 }
56 }
57 }