public class QuickSelect
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 QuickSelect {
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: + "QuickSelect\n"
25: + "-----------\n\n"
26: + "This program demonstrates using the QuickSort algorithm "
27: + "to find the smallest\nelements of a list.\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: // get how many small values we want
39: System.out.print("How many of the smallest elements do you want? ");
40: int numToGet = KBD.nextInt();
41: KBD.nextLine();
43: // show the original array
44: System.out.println("\nArray values before sorting:");
45: PrintTrace.printArray(arr);
46: pause();
48: // select the smallest elements
49: quickSelect(arr, 0, arr.length, numToGet);
51: // show the smallest elements
52: System.out.println("\nThe " + numToGet + " smallest elements:");
53: PrintTrace.printArray(arr, 0, numToGet);
54: pause();
56: // show the remaining elements
57: System.out.println("\nThe remaining elements:");
58: PrintTrace.printArray(arr, numToGet, arr.length);
59: pause();
61: // do a test to make sure that the chosen elements ARE the smallest
62: if (max(arr, 0, numToGet) > min(arr, numToGet, arr.length)) {
63: System.err.println("Oops! That didn't work!");
64: }
65: }
67: /**
68: * A modified version of quicksort that only sorts the lower end of the
69: * array. It reports its actions as it goes along.
70: *
71: * @param arr the array to (partially) sort
72: * @param begin the lower bound (inclusive) of the part being sorted
73: * @param end the upper bound (exclusive) of the part being sorted
74: * @param numToGet the upper bound (exclusive) of the part needing to be
75: * sorted
76: */
77: public static void quickSelect(
78: int[] arr,
79: int begin,
80: int end,
81: int numToGet) {
82: // only need to sort subsections of length 2 or more
83: if (end - begin > 1) {
84: // we don't need to sort if there are numToGet elements BELOW begin
85: if (numToGet <= begin) {
86: System.out.printf("We can skip sorting from %d to %d.%n",
87: begin, end);
88: return;
89: }
91: // report the range that's being sorted
92: System.out.println("Sorting from " + begin + " to " + end + "...");
94: // pick pivot
95: int pivot = pickAndMovePivot(arr, begin, end);
97: // partition
98: int pivotPlace = partition(arr, begin, end, pivot);
99: System.out.printf("After partitioning at %d (pivot = %d):%n",
100: pivotPlace, pivot);
101: PrintTrace.printArray(arr, begin, end);
102: pause();
104: // quickSelect lower part (for smallest values)
105: quickSelect(arr, begin, pivotPlace, numToGet);
107: // quickSelect upper part
108: quickSelect(arr, pivotPlace + 1, end, numToGet);
109: }
110: }
112: /**
113: * Use the median-of-three method to pick a pivot value, then move it to the
114: * end of the array.
115: *
116: * @param arr the array to pick the pivot from
117: * @param begin the lower bound (inclusive) of the part of the array being
118: * sorted
119: * @param end the upper bound (exclusive) of the part of the array being
120: * sorted
121: * @return the value chosen as the pivot
122: */
123: private static int pickAndMovePivot(int[] arr, int begin, int end) {
124: int p1 = begin;
125: int p2 = end - 1;
126: int p3 = begin + (end - begin) / 2;
127: if (arr[p1] < arr[p2]) {
128: if (arr[p2] < arr[p3]) {
129: return movePivot(arr, p2, end);
130: } else if (arr[p1] < arr[p3]) {
131: return movePivot(arr, p3, end);
132: } else {
133: return movePivot(arr, p1, end);
134: }
135: } else if (arr[p1] < arr[p3]) {
136: return movePivot(arr, p1, end);
137: } else if (arr[p2] < arr[p3]) {
138: return movePivot(arr, p3, end);
139: } else {
140: return movePivot(arr, p2, end);
141: }
142: }
144: /**
145: * Move the pivot value to the end of the part of the array being sorted.
146: *
147: * @param arr the array being sorted
148: * @param pivotStart the index where the pivot value was in the array
149: * @param end the upper bound (exclusive) of the part of the array being
150: * sorted
151: * @return the value moved to the end (i.e. the pivot value)
152: */
153: private static int movePivot(int[] arr, int pivotStart, int end) {
154: swap(arr, pivotStart, end - 1);
155: return arr[end - 1];
156: }
158: /**
159: * Partition the part of the array being sorted. That is, move all the
160: * smaller values toward the front of the array and the bigger ones toward
161: * the back. Bigger and smaller are determined with respect to the pivot
162: * value.
163: *
164: * @param arr the array being sorted
165: * @param begin the lower bound (inclusive) of the part of the array being
166: * sorted
167: * @param end the upper bound (exclusive) of the part of the array being
168: * sorted
169: * @param pivot the pivot value
170: * @return the position the pivot value ended up in
171: */
172: private static int partition(int[] arr, int begin, int end, int pivot) {
173: int lowerEdge = begin;
174: int upperEdge = end - 2; // pivot is in end-1
175:
176: // swap near-front-larger and near-back-smaller values until we cross
177: // in the middle
178: while (true) {
179: if (arr[lowerEdge] < pivot) {
180: // near-front-small
181: lowerEdge++;
182: } else if (lowerEdge >= upperEdge) {
183: // crossed in the middle
184: break;
185: } else if (pivot < arr[upperEdge]) {
186: // near-back-large
187: upperEdge--;
188: } else {
189: // near-front-large and near-back-small
190: swap(arr, lowerEdge, upperEdge);
191: lowerEdge++;
192: upperEdge--;
193: }
194: }
195:
196: // move the pivot, if necessary
197: if (pivot < arr[lowerEdge]) {
198: swap(arr, lowerEdge, end - 1);
199: }
200:
201: // return the location of the/a pivot value
202: return lowerEdge;
203: }
205: private static void swap(int[] arr, int p1, int p2) {
206: int temp = arr[p1];
207: arr[p1] = arr[p2];
208: arr[p2] = temp;
209: }
211: /**
212: * Wait for the user to press the enter key.
213: */
214: public static void pause() {
215: System.out.print("\n...Press ENTER...");
216: KBD.nextLine();
217: System.out.println();
218: }
220: /**
221: * Find the maximum value in part of the array.
222: *
223: * @param arr the array to search
224: * @param begin the lower bound (inclusive) of the part to search
225: * @param end the upper bound (exclusive) of the part to search
226: * @return the maximum value in the given part of the array
227: */
228: private static int max(int[] arr, int begin, int end) {
229: int max = Integer.MIN_VALUE;
230: for (int i = begin; i < end; ++i) {
231: max = Math.max(max, arr[i]);
232: }
233: return max;
234: }
236: /**
237: * Find the minimum value in part of the array.
238: *
239: * @param arr the array to search
240: * @param begin the lower bound (inclusive) of the part to search
241: * @param end the upper bound (exclusive) of the part to search
242: * @return the minimum value in the given part of the array
243: */
244: private static int min(int[] arr, int begin, int end) {
245: int min = Integer.MAX_VALUE;
246: for (int i = begin; i < end; ++i) {
247: min = Math.min(min, arr[i]);
248: }
249: return min;
250: }
252: }