public class Quick
1: import java.util.Arrays;
3: /**
4: *
5: * @author Mark Young (A00000000)
6: */
7: public class Quick {
9: /**
10: * Sort the given array using the quicksort algorithm.
11: *
12: * @param arr the array to sort
13: */
14: public static void sort(int[] arr) {
15: sortIntoRange(arr, 0, arr.length, 0, arr.length);
16: }
18: /**
19: * Partially sort the given array using the quicksort algorithm so that the
20: * given range contains its proper values. Everything below the range will
21: * be less than or equal to the smallest value in the sorted range, and
22: * everything above the range will be greater than or equal to the largest
23: * value in the sorted range. Elements in the range will be sorted.
24: *
25: * @param arr the array to (partially) sort
26: * @param sortBegin the lower bound (inclusive) of the part being sorted
27: * @param sortEnd the upper bound (exclusive) of the part being sorted
28: */
29: public static void sortIntoRange(int[] arr, int sortBegin, int sortEnd) {
30: sortIntoRange(arr, 0, arr.length, sortBegin, sortEnd);
31: }
33: /**
34: * Sort the given part of the given array using the quicksort algorithm. The
35: * values outside the range are ignored. Values in the range will be sorted.
36: *
37: * @param arr the array to (partially) sort
38: * @param sortBegin the lower bound (inclusive) of the part being sorted
39: * @param sortEnd the upper bound (exclusive) of the part being sorted
40: */
41: public static void sortPart(int[] arr, int sortBegin, int sortEnd) {
42: sortIntoRange(arr, sortBegin, sortEnd, sortBegin, sortEnd);
43: }
45: /**
46: * Partially sort the given array using the quicksort algorithm so that the
47: * lowest part contains its proper values. The first {@code numToGet}
48: * elements will be sorted. Everything above that in the array will be
49: * greater than or equal to the largest value in the sorted range.
50: *
51: * @param arr the array to (partially) sort
52: * @param numToGet how many of the lowest elements to get
53: */
54: public static void sortSmallest(int numToGet, int[] arr) {
55: sortIntoRange(arr, 0, arr.length, 0, numToGet);
56: }
58: /**
59: * Partially sort the given array using the quicksort algorithm so that the
60: * highest part contains its proper values. The last {@code numToGet}
61: * elements will be sorted. Everything below that in the array will be less
62: * than or equal to the smallest value in the sorted range.
63: *
64: * @param arr the array to (partially) sort
65: * @param numToGet how many of the lowest elements to get
66: */
67: public static void sortLargest(int numToGet, int[] arr) {
68: sortIntoRange(arr, 0, arr.length, arr.length - numToGet, arr.length);
69: }
71: /**
72: * Partially sort the given array using the quicksort algorithm so that the
73: * middle part contains its proper values. The middle part will be <em>at
74: * least</em> {@code numToGet} elements long. (It will be increased by one
75: * if necessary to make the lower and higher parts of the array the same
76: * length.) The middle part will be sorted. Everything below the range will
77: * be less than or equal to the smallest value in the sorted range, and
78: * everything above the range will be greater than or equal to the largest
79: * value in the sorted range.
80: *
81: * @param arr the array to (partially) sort
82: * @param numToGet how many of the lowest elements to get
83: */
84: public static void sortMiddle(int numToGet, int[] arr) {
85: int numOutside = arr.length - numToGet;
86: int numBelow = numOutside / 2;
87: sortIntoRange(arr, 0, arr.length, numBelow, arr.length - numBelow);
88: }
90: /*
91: * ---------- Implementation ----------
92: */
93: /**
94: * A modified version of quicksort that only sorts part of the array.
95: *
96: * @param arr the array to (partially) sort
97: * @param sortBegin the lower bound (inclusive) of the part being sorted
98: * @param sortEnd the upper bound (exclusive) of the part being sorted
99: * @param reqBegin the lower bound (inclusive) of the part needing to be
100: * sorted
101: * @param reqEnd the upper bound (exclusive) of the part needing to be
102: * sorted
103: */
104: private static void sortIntoRange(
105: int[] arr,
106: int sortBegin,
107: int sortEnd,
108: int reqBegin,
109: int reqEnd) {
110: // only need to sort subsections of length 2 or more
111: // also only need to sort parts that overlap the part needing sorted
112: if (sortEnd - sortBegin > 1
113: && reqBegin < sortEnd && sortBegin < reqEnd) {
114: // pick pivot
115: int pivot = pickAndMovePivot(arr, sortBegin, sortEnd);
117: // partition
118: int pivotPlace = partition(arr, sortBegin, sortEnd, pivot);
120: // quickSelect lower part (for sortSmallest values)
121: sortIntoRange(arr, sortBegin, pivotPlace, reqBegin, reqEnd);
123: // quickSelect upper part
124: sortIntoRange(arr, pivotPlace + 1, sortEnd, reqBegin, reqEnd);
125: }
126: }
128: /**
129: * Use the median-of-three method to pick a pivot value, then move it to the
130: * end of the array.
131: *
132: * @param arr the array to pick the pivot from
133: * @param begin the lower bound (inclusive) of the part of the array being
134: * sorted
135: * @param end the upper bound (exclusive) of the part of the array being
136: * sorted
137: * @return the value chosen as the pivot
138: */
139: private static int pickAndMovePivot(int[] arr, int begin, int end) {
140: int p1 = begin;
141: int p2 = end - 1;
142: int p3 = begin + (end - begin) / 2;
143: if (arr[p1] < arr[p2]) {
144: if (arr[p2] < arr[p3]) {
145: return movePivot(arr, p2, end);
146: } else if (arr[p1] < arr[p3]) {
147: return movePivot(arr, p3, end);
148: } else {
149: return movePivot(arr, p1, end);
150: }
151: } else if (arr[p1] < arr[p3]) {
152: return movePivot(arr, p1, end);
153: } else if (arr[p2] < arr[p3]) {
154: return movePivot(arr, p3, end);
155: } else {
156: return movePivot(arr, p2, end);
157: }
158: }
160: /**
161: * Move the pivot value to the end of the part of the array being sorted.
162: *
163: * @param arr the array being sorted
164: * @param pivotStart the index where the pivot value was in the array
165: * @param end the upper bound (exclusive) of the part of the array being
166: * sorted
167: * @return the value moved to the end (i.e. the pivot value)
168: */
169: private static int movePivot(int[] arr, int pivotStart, int end) {
170: swap(arr, pivotStart, end - 1);
171: return arr[end - 1];
172: }
174: /**
175: * Partition the part of the array being sorted. That is, move all the
176: * smaller values toward the front of the array and the bigger ones toward
177: * the back. Bigger and smaller are determined with respect to the pivot
178: * value.
179: *
180: * @param arr the array being sorted
181: * @param begin the lower bound (inclusive) of the part of the array being
182: * sorted
183: * @param end the upper bound (exclusive) of the part of the array being
184: * sorted
185: * @param pivot the pivot value
186: * @return the position the pivot value ended up in
187: */
188: private static int partition(int[] arr, int begin, int end, int pivot) {
189: int lowerEdge = begin;
190: int upperEdge = end - 2; // pivot is in end-1
192: // swap near-front-larger and near-back-smaller values until we cross
193: // in the sortMiddle
194: while (true) {
195: if (arr[lowerEdge] < pivot) {
196: // near-front-small
197: lowerEdge++;
198: } else if (lowerEdge >= upperEdge) {
199: // crossed in the sortMiddle
200: break;
201: } else if (pivot < arr[upperEdge]) {
202: // near-back-large
203: upperEdge--;
204: } else {
205: // near-front-large and near-back-small
206: swap(arr, lowerEdge, upperEdge);
207: lowerEdge++;
208: upperEdge--;
209: }
210: }
212: // move the pivot, if necessary
213: if (pivot < arr[lowerEdge]) {
214: swap(arr, lowerEdge, end - 1);
215: }
217: // return the location of the/a pivot value
218: return lowerEdge;
219: }
221: private static void swap(int[] arr, int p1, int p2) {
222: int temp = arr[p1];
223: arr[p1] = arr[p2];
224: arr[p2] = temp;
225: }
227: }