public class TestQuick
1: import java.util.Arrays;
2: import java.util.Scanner;
4: /**
5: * Test the methods in the class Quick.
6: *
7: * @author Mark Young (A00000000)
8: */
9: public class TestQuick {
11: public static void main(String[] args) {
12: int size = 20;
13: int part = size / 4;
14: int[] numbers = new int[size];
15: for (int i = 0; i < size; ++i) {
16: numbers[i] = (int) (1000 * Math.random());
17: }
19: testSmallest(part, Arrays.copyOf(numbers, size));
20: pause();
21: testLargest(part, Arrays.copyOf(numbers, size));
22: pause();
23: testMiddle(part, Arrays.copyOf(numbers, size));
24: pause();
25: testSort(Arrays.copyOf(numbers, size));
26: pause();
27: }
29: /**
30: * Test the method to find the smallest elements in an array.
31: *
32: * @param numbers the array to test with
33: */
34: private static void testSmallest(int part, int[] numbers) {
35: System.out.println("Test Small");
36: System.out.println("...before: " + toString(numbers));
37: Quick.sortSmallest(part, numbers);
38: System.out.println("...after: " + toString(numbers));
39: sorted(numbers, 0, part);
40: }
42: /**
43: * Test the method to sfind the largest elements in an array.
44: *
45: * @param numbers the array to test with
46: */
47: private static void testLargest(int part, int[] numbers) {
48: System.out.println("Test Large");
49: System.out.println("...before: " + toString(numbers));
50: Quick.sortLargest(part, numbers);
51: System.out.println("...after: " + toString(numbers));
52: sorted(numbers, numbers.length - part, numbers.length);
53: }
55: /**
56: * Test the method to find the mid-sized elements of the array.
57: *
58: * @param numbers the array to test with
59: */
60: private static void testMiddle(int part, int[] numbers) {
61: System.out.println("Test Middle");
62: System.out.println("...before: " + toString(numbers));
63: Quick.sortMiddle(part, numbers);
64: System.out.println("...after: " + toString(numbers));
65: int numOutside = numbers.length - part;
66: int numBelow = numOutside / 2;
67: sorted(numbers, numBelow, numbers.length - numBelow);
68: }
70: /**
71: * Test the method to sort the entire array.
72: *
73: * @param numbers the array to test with
74: */
75: private static void testSort(int[] numbers) {
76: System.out.println("Test Sort");
77: System.out.println("...before: " + toString(numbers));
78: Quick.sort(numbers);
79: System.out.println("...after: " + toString(numbers));
80: sorted(numbers, 0, numbers.length);
81: }
83: /**
84: * Check whether the array is such that:
85: * <ul>
86: * <li> Everything below {@code begin} is at least as small as anything in
87: * the sorted range.
88: * <li> Everything between {@code begin} (included) and {@code end}
89: * (excluded) is sorted.
90: * <li> Everything at/above {@code end} is at least as large as anything in
91: * the sorted range.
92: * </ul>
93: *
94: * @param numbers the array to test
95: * @param begin the lowest index (inclusive) of the sorted range
96: * @param end the highest index (exclusive) of the sorted range
97: */
98: private static void sorted(int[] numbers, int begin, int end) {
99: // To start we'll assume the middle range is sorted, so that the
100: // smallest element is in position begin, and the largest is in
101: // position end - 1.
102: //
103: // We WILL test this assumption later!
104: int low = numbers[begin];
105: int high = numbers[end - 1];
107: // everything before sorted range should be small
108: boolean allSmaller = true;
109: for (int i = 0; i < begin; ++i) {
110: if (numbers[i] > low) {
111: System.out.println("ERROR BELOW THE SORTED RANGE!");
112: System.out.println("numbers[" + i + "] == " + numbers[i]
113: + " > " + low);
114: System.out.println(toString(numbers));
115: allSmaller = false;
116: }
117: }
118: if (allSmaller) {
119: System.out.printf("...everything below it is smaller than "
120: + "arr[%d] == %d%n",
121: begin, low);
122: }
124: // everything in sorted range should be sorted (duh!)
125: boolean isSorted = true;
126: for (int i = begin + 1; i < end; ++i) {
127: if (numbers[i - 1] > numbers[i]) {
128: System.out.println("ERROR IN THE SORTED RANGE!");
129: System.out.println("numbers[" + (i - 1) + "] == "
130: + numbers[i - 1] + " > "
131: + "numbers[" + i + "] == " + numbers[i]);
132: System.out.println(toString(numbers));
133: isSorted = false;
134: }
135: }
136: if (isSorted) {
137: System.out.printf("...everything in the range arr[%d] = %d "
138: + "arr[%d] = %d is sorted%n",
139: begin, low, end - 1, high);
140: }
142: // everything above sorted range should be large
143: boolean allBigger = true;
144: for (int i = end; i < numbers.length; ++i) {
145: if (numbers[i] < high) {
146: System.out.println("ERROR ABOVE THE SORTED RANGE!");
147: System.out.println("numbers[" + i + "] == " + numbers[i]
148: + " < " + high);
149: System.out.println(toString(numbers));
150: allBigger = false;
151: }
152: }
153: if (allBigger) {
154: System.out.printf("...everything above it is larger than "
155: + "arr[%d] == %d%n",
156: end - 1, high);
157: }
158: }
160: private static final Scanner KBD = new Scanner(System.in);
162: /**
163: * Prompt the user and wait for them to press the enter key.
164: */
165: private static void pause() {
166: System.out.print("\n...press enter...");
167: KBD.nextLine();
168: System.out.println();
169: }
171: /**
172: * Generate a String for an array in some reasonable fashion.
173: *
174: * @param arr the array to print
175: */
176: private static String toString(int[] arr) {
177: String result = "";
178: int onLine = 0;
179: for (int num : arr) {
180: if (onLine % 10 == 0) {
181: result += "\n\t";
182: }
183: result += String.format("%6d", num);
184: ++onLine;
185: }
186: return result + "\n";
187: }
188: }