public class ShellSort
1: import java.util.ArrayList;
2: import java.util.Iterator;
3: import java.util.List;
5: /**
6: *
7: * @author Mark Young (A00000000)
8: */
9: public class ShellSort {
11: private static boolean tracing = true;
12: private static final int HOW_MANY = 10000;
14: public static void main(String[] args) {
15: System.out.println("\n\n"
16: + "Shell Sort\n"
17: + "==============\n");
19: // Strings
20: sortNames(Common.getCrew());
22: // integers
23: sortNumbers(Common.randomNumbers(HOW_MANY, 1, HOW_MANY));
25: System.out.println();
26: }
29: /**
30: * Sort a list of words/names.
31: *
32: * @param names the names to sort
33: */
34: public static void sortNames(SortArray<String> names) {
36: // print title
37: System.out.println("\n"
38: + "Sorting Strings\n"
39: + "---------------\n");
41: // show sorting
42: System.out.println("Before sorting:\n\t" + names);
43: shellSort(names);
44: System.out.println("After sorting:\n\t" + names);
46: // report counts
47: int numAsgn = names.getNumAsgn();
48: int numComp = names.getNumComp();
49: System.out.printf("To sort %,d words "
50: + "took %,d assignments "
51: + "and %,d comparisons,\n"
52: + "for a total of %,d operations.%n%n",
53: names.length, numAsgn, numComp, numAsgn + numComp);
54: }
56: /**
57: * Sort a list of integer values, generated randomly.
58: *
59: * @param numbers the numbers to sort
60: */
61: public static void sortNumbers(SortArray<Integer> numbers) {
62: tracing = false;
64: System.out.println("\n"
65: + "Sorting Numbers\n"
66: + "---------------\n");
68: shellSort(numbers);
69: int numAsgn = numbers.getNumAsgn();
70: int numComp = numbers.getNumComp();
71: System.out.printf("To sort %,d numbers "
72: + "took %,d assignments "
73: + "and %,d comparisons,\n"
74: + "for a total of %,d operations.%n%n",
75: HOW_MANY, numAsgn, numComp, numAsgn + numComp);
77: }
80: /**
81: * Perform insertion sort on the given array.
82: *
83: * @param <T> base type of the array
84: * @param arr the array to sort
85: */
86: public static <T extends Comparable<? super T>>
87: void shellSort(SortArray<T> arr) {
88: arr.reset();
89: Iterator<Integer> gaps = getGapSequence(arr.length);
90: while (gaps.hasNext()) {
91: int gap = gaps.next();
92: for (int i = gap; i < arr.length; ++i) {
93: int p = i;
94: T temp = arr.get(p);
95: while (p >= gap && arr.compareTo(p - gap, temp) > 0) {
96: arr.move(p, p - gap);
97: p -= gap;
98: }
99: arr.set(p, temp);
100: if (tracing) {
101: System.out.println("...gap=" + gap + ": " + arr);
102: }
103: }
104: }
105: }
107: /**
108: * Return the gap sequence to use for an array of the given size. The
109: * sequence must end with the number 1. We will only be working our way thru
110: * the sequence from start to finish, without changing any elements, so we
111: * only need an Iterator, not a ListIterator.
112: *
113: * @param size the size of the array
114: * @return an iterator thru the sequence
115: */
116: private static Iterator<Integer> getGapSequence(int size) {
117: List<Integer> result = new ArrayList<>();
118:
119: // standard gap sequence
120: while (size > 1) {
121: size /= 2;
122: if (size % 2 == 0) {
123: ++size;
124: }
125: result.add(size);
126: }
127:
128: // guaranteed to end in 1 so long as its not empty!
129: // And its only empty if the size of the list is length 0 or 1,
130: // in which case the List is already sorted!
132: return result.iterator();
133: }
134:
135: }