public class QuickSort
1: /**
2: * A program to select the N smallest values in an array of randomly generated
3: * numbers.
4: *
5: * @author Mark Young (A00000000)
6: */
7: import java.util.Scanner;
9: public class QuickSort {
11: /**
12: * biggest number in list
13: */
14: private static final int BIGGEST = 1000;
16: /**
17: * keyboard scanner for whole program
18: */
19: private static final Scanner KBD = new Scanner(System.in);
21: public static void main(String[] args) {
22: // introduce program
23: System.out.print("\n\n"
24: + "QuickSort\n"
25: + "---------\n\n"
26: + "This program demonstrates the QuickSort algorithm.\n\n"
27: + "By Mark Young (A00000000).\n\n");
29: // create list
30: System.out.print("How long should I make the list? ");
31: int numElts = KBD.nextInt();
32: KBD.nextLine();
33: int[] arr = new int[numElts];
34: for (int i = 0; i < numElts; i++) {
35: arr[i] = (int) (BIGGEST * Math.random());
36: }
38: // show the original array
39: System.out.println("\nArray values before sorting:");
40: PrintTrace.printArray(arr);
41: pause();
43: // sort the array
44: quickSort(arr, 0, arr.length);
46: // show the sorted array
47: System.out.println("\nThe sorted array:");
48: PrintTrace.printArray(arr);
49: pause();
51: // do a test to make sure that the list is sorted
52: if (!sorted(arr)) {
53: System.err.println("Oops! That didn't work!");
54: }
55: }
57: /**
58: * Sort an array using the quicksort algorithm. Report what parts of the
59: * array are being sorted.
60: *
61: * @param arr the array to (partially) sort
62: * @param begin the lower bound (inclusive) of the part being sorted
63: * @param end the upper bound (exclusive) of the part being sorted
64: */
65: public static void quickSort(
66: int[] arr,
67: int begin,
68: int end) {
69: // only need to sort subsections of length 2 or more
70: if (end - begin > 1) {
71: // report the range that's being sorted
72: System.out.println("Sorting from " + begin + " to " + end + "...");
74: // pick pivot
75: int pivot = pickAndMovePivot(arr, begin, end);
77: // partition
78: int pivotPlace = partition(arr, begin, end, pivot);
79: System.out.printf("After partitioning at %d (pivot = %d):%n",
80: pivotPlace, pivot);
81: PrintTrace.printArray(arr, begin, end);
82: pause();
84: // quickSort lower part (for smallest values)
85: quickSort(arr, begin, pivotPlace);
87: // quickSort upper part
88: quickSort(arr, pivotPlace + 1, end);
89: }
90: }
92: /**
93: * Use the median-of-three method to pick a pivot value, then move it to the
94: * end of the array.
95: *
96: * @param arr the array to pick the pivot from
97: * @param begin the lower bound (inclusive) of the part of the array being
98: * sorted
99: * @param end the upper bound (exclusive) of the part of the array being
100: * sorted
101: * @return the value chosen as the pivot
102: */
103: private static int pickAndMovePivot(int[] arr, int begin, int end) {
104: int p1 = begin;
105: int p2 = end - 1;
106: int p3 = begin + (end - begin) / 2;
107: if (arr[p1] < arr[p2]) {
108: if (arr[p2] < arr[p3]) {
109: return movePivot(arr, p2, end);
110: } else if (arr[p1] < arr[p3]) {
111: return movePivot(arr, p3, end);
112: } else {
113: return movePivot(arr, p1, end);
114: }
115: } else if (arr[p1] < arr[p3]) {
116: return movePivot(arr, p1, end);
117: } else if (arr[p2] < arr[p3]) {
118: return movePivot(arr, p3, end);
119: } else {
120: return movePivot(arr, p2, end);
121: }
122: }
124: /**
125: * Move the pivot value to the end of the part of the array being sorted.
126: *
127: * @param arr the array being sorted
128: * @param pivotStart the index where the pivot value was in the array
129: * @param end the upper bound (exclusive) of the part of the array being
130: * sorted
131: * @return the value moved to the end (i.e. the pivot value)
132: */
133: private static int movePivot(int[] arr, int pivotStart, int end) {
134: swap(arr, pivotStart, end - 1);
135: return arr[end - 1];
136: }
138: /**
139: * Partition the part of the array being sorted. That is, move all the
140: * smaller values toward the front of the array and the bigger ones toward
141: * the back. Bigger and smaller are determined with respect to the pivot
142: * value.
143: *
144: * @param arr the array being sorted
145: * @param begin the lower bound (inclusive) of the part of the array being
146: * sorted
147: * @param end the upper bound (exclusive) of the part of the array being
148: * sorted
149: * @param pivot the pivot value
150: * @return the position the pivot value ended up in
151: */
152: private static int partition(int[] arr, int begin, int end, int pivot) {
153: int lowerEdge = begin;
154: int upperEdge = end - 2; // pivot is in end-1
156: // swap near-front-larger and near-back-smaller values until we cross
157: // in the middle
158: while (true) {
159: if (arr[lowerEdge] < pivot) {
160: // near-front-small
161: lowerEdge++;
162: } else if (lowerEdge >= upperEdge) {
163: // crossed in the middle
164: break;
165: } else if (pivot < arr[upperEdge]) {
166: // near-back-large
167: upperEdge--;
168: } else {
169: // near-front-large and near-back-small
170: swap(arr, lowerEdge, upperEdge);
171: lowerEdge++;
172: upperEdge--;
173: }
174: }
176: // move the pivot, if necessary
177: if (pivot < arr[lowerEdge]) {
178: swap(arr, lowerEdge, end - 1);
179: }
181: // return the location of the/a pivot value
182: return lowerEdge;
183: }
185: private static void swap(int[] arr, int p1, int p2) {
186: int temp = arr[p1];
187: arr[p1] = arr[p2];
188: arr[p2] = temp;
189: }
191: /**
192: * Wait for the user to press the enter key.
193: */
194: public static void pause() {
195: System.out.print("\n...Press ENTER...");
196: KBD.nextLine();
197: System.out.println();
198: }
200: /**
201: * Check whether the given array is sorted.
202: *
203: * @param arr the array to check
204: * @return true if arr is sorted; false otherwise
205: */
206: private static boolean sorted(int[] arr) {
207: for (int i = 1; i < arr.length; ++i) {
208: if (arr[i - 1] > arr[i]) {
209: return false;
210: }
211: }
212: return true;
213: }
215: }