public class TestQuick
1: import java.util.Arrays;
3: /**
4: * Thest the methods in the class Quick.
5: *
6: * @author Mark Young (A00000000)
7: */
8: public class TestQuick {
10: public static void main(String[] args) {
11: int size = 20;
12: int part = size / 4;
13: int[] numbers = new int[size];
14: for (int i = 0; i < size; ++i) {
15: numbers[i] = (int) (1000 * Math.random());
16: }
18: testSmallest(part, Arrays.copyOf(numbers, size));
19: testLargest(part, Arrays.copyOf(numbers, size));
20: testMiddle(part, Arrays.copyOf(numbers, size));
21: testSort(Arrays.copyOf(numbers, size));
22: }
24: /**
25: * Test the method to find the smallest elements in an array.
26: *
27: * @param numbers the array to test with
28: */
29: private static void testSmallest(int part, int[] numbers) {
30: System.out.println("Test Small");
31: Quick.sortSmallest(part, numbers);
32: sorted(numbers, 0, part);
33: }
35: /**
36: * Test the method to sfind the largest elements in an array.
37: *
38: * @param numbers the array to test with
39: */
40: private static void testLargest(int part, int[] numbers) {
41: System.out.println("Test Large");
42: Quick.sortLargest(part, numbers);
43: sorted(numbers, numbers.length - part, numbers.length);
44: }
46: /**
47: * Test the method to find the mid-sized elements of the array.
48: *
49: * @param numbers the array to test with
50: */
51: private static void testMiddle(int part, int[] numbers) {
52: System.out.println("Test Middle");
53: Quick.sortMiddle(part, numbers);
54: int numOutside = numbers.length - part;
55: int numBelow = numOutside / 2;
56: sorted(numbers, numBelow, numbers.length - numBelow);
57: }
59: /**
60: * Test the method to sort the entire array.
61: *
62: * @param numbers the array to test with
63: */
64: private static void testSort(int[] numbers) {
65: System.out.println("Test Sort");
66: Quick.sort(numbers);
67: sorted(numbers, 0, numbers.length);
68: }
70: /**
71: * Check whether the array is such that:
72: * <ul>
73: * <li> Everything below {@code begin} is at least as small as anything in
74: * the sorted range.
75: * <li> Everything between {@code begin} (included) and {@code end}
76: * (excluded) is sorted.
77: * <li> Everything at/above {@code end} is at least as large as anything in
78: * the sorted range.
79: * </ul>
80: *
81: * @param numbers the array to test
82: * @param begin the lowest index (inclusive) of the sorted range
83: * @param end the highest index (exclusive) of the sorted range
84: */
85: private static void sorted(int[] numbers, int begin, int end) {
86: // To start we'll assume the middle range is sorted, so that the
87: // smallest element is in position begin, and the largest is in
88: // position end - 1.
89: //
90: // We WILL test this assumption later!
91: int low = numbers[begin];
92: int high = numbers[end - 1];
94: // everything before sorted range should be small
95: for (int i = 0; i < begin; ++i) {
96: if (numbers[i] > low) {
97: System.out.println("ERROR BELOW THE SORTED RANGE!");
98: System.out.println("numbers[" + i + "] == " + numbers[i]
99: + " > " + low);
100: System.out.println(Arrays.toString(numbers));
101: }
102: }
104: // everything in sorted range should be sorted (duh!)
105: for (int i = begin + 1; i < end; ++i) {
106: if (numbers[i - 1] > numbers[i]) {
107: System.out.println("ERROR IN THE SORTED RANGE!");
108: System.out.println("numbers[" + (i - 1) + "] == "
109: + numbers[i - 1] + " > "
110: + "numbers[" + i + "] == " + numbers[i]);
111: System.out.println(Arrays.toString(numbers));
112: }
113: }
115: // everything above sorted range should be large
116: for (int i = end; i < numbers.length; ++i) {
117: if (numbers[i] < high) {
118: System.out.println("ERROR ABOVE THE SORTED RANGE!");
119: System.out.println("numbers[" + i + "] == " + numbers[i]
120: + " < " + high);
121: System.out.println(Arrays.toString(numbers));
122: }
123: }
124: }
126: }