public class ShellSort
3: import java.util.Scanner;
5: /**
6: *
7: * @author Mark Young (A00000000)
8: */
9: public class ShellSort {
11: public static final Scanner KBD = Common.KBD;
12: private static final int HOW_MANY = 10;
13: private static final int MAX = 1000;
14: private static int traceLevel = 0;
16: public static void main(String[] args) {
17: System.out.println("\n\n"
18: + "Shell Sort\n"
19: + "==========\n");
21: setTraceLevel();
23: // create an array of random integers
24: int[] numbers = Common.randomNumbers(HOW_MANY, MAX / 10, MAX);
25: Common.printArray(numbers);
26: Common.pause();
28: // sort it
29: shellSort(numbers);
30:
31: // show it sorted
32: System.out.println("Array now sorted");
33: Common.printArray(numbers);
34: Common.pause();
35: }
37: /**
38: * Prompt for and read a level of tracing to do.
39: */
40: public static void setTraceLevel() {
41: String traceMenu = "Enter a trace level: \n"
42: + " 0 - no tracing\n"
43: + " 1 - outer loop only (n-sorted)\n"
44: + " 2 - middle loop, too (inserted)\n"
45: + " 3 - innermost loop (inserting)\n\n"
46: + "Trace level: ";
48: System.out.print(traceMenu);
49: traceLevel = KBD.nextInt();
50: KBD.nextLine();
51: while (traceLevel < 0 || 3 < traceLevel) {
52: System.out.print(traceMenu);
53: traceLevel = KBD.nextInt();
54: KBD.nextLine();
55: }
56: }
58: /**
59: * Perform insertion sort on the given array.
60: *
61: * @param arr the array to sort
62: */
63: public static void shellSort(int[] arr) {
64: int gap = arr.length / 2;
65: while (gap >= 1) {
66: if (gap % 2 == 0) {
67: ++gap;
68: }
69: if (traceLevel > 1) {
70: System.out.println("..." + gap + "-sorting...");
71: // Common.printArray(arr);
72: for (int rem = 0; rem < gap; ++rem) {
73: // System.out.println("...offset " + rem);
74: Common.printOffset(arr, gap, rem);
75: }
76: Common.pause();
77: }
78: for (int i = 0; i < arr.length - gap; ++i) {
79: int p = i + gap;
80: int temp = arr[p];
81: int end = p;
82: if (traceLevel > 2) {
83: System.out.println("...inserting " + temp + "...");
84: Common.printOffset(arr, gap, i % gap, end);
85: Common.pause();
86: }
87: while (p >= gap && arr[p - gap] > temp) {
88: arr[p] = arr[p - gap];
89: p -= gap;
90: if (traceLevel > 2) {
91: System.out.println("...inserting " + temp + "...");
92: System.out.println("...copy up " + arr[p] + "...");
93: Common.printOffset(arr, gap, i % gap, end + 1);
94: Common.pause();
95: }
96: }
97: arr[p] = temp;
98: if (traceLevel > 1) {
99: System.out.println("one more inserted: ");
100: Common.printOffset(arr, gap, i % gap, end + 1);
101: Common.pause();
102: }
103: }
104: if (traceLevel > 0) {
105: System.out.println("now " + gap + "-sorted");
106: for (int rem = 0; rem < gap; ++rem) {
107: // System.out.println("...offset " + rem);
108: Common.printOffset(arr, gap, rem);
109: }
110: Common.pause();
111: }
112: gap /= 2;
113: }
114: }
116: }