public class QuickSelectDemo
1: //QuickSelectDemo.java
3: import java.util.Arrays;
4: import java.util.Scanner;
6: public class QuickSelectDemo
7: {
8: private static int partition
9: (
10: int[] numbers,
11: int startIndex,
12: int endIndex
13: )
14: {
15: // Select the middle value as the pivot.
16: int midpoint = startIndex + (endIndex - startIndex) / 2;
17: int pivot = numbers[midpoint];
19: // "low" and "high" start at the ends of the array segment
20: // and move towards each other.
21: int low = startIndex;
22: int high = endIndex;
24: boolean done = false;
25: while (!done)
26: {
27: // Increment low while numbers[low] < pivot
28: while (numbers[low] < pivot)
29: {
30: low = low + 1;
31: }
33: // Decrement high while pivot < numbers[high]
34: while (pivot < numbers[high])
35: {
36: high = high - 1;
37: }
39: // If low and high have crossed each other, the loop
40: // is done. If not, the elements are swapped, low is
41: // incremented and high is decremented.
42: if (low >= high)
43: {
44: done = true;
45: }
46: else
47: {
48: int temp = numbers[low];
49: numbers[low] = numbers[high];
50: numbers[high] = temp;
51: low = low + 1;
52: high = high - 1;
53: }
54: }
56: // "high" is the last index in the left segment.
57: return high;
58: }
60: private static int QuickSelect
61: (
62: int[] numbers,
63: int startIndex,
64: int endIndex,
65: int k
66: )
67: {
68: if (startIndex >= endIndex)
69: {
70: return numbers[startIndex];
71: }
73: int lowLastIndex = partition(numbers, startIndex, endIndex);
74: if (k <= lowLastIndex)
75: {
76: return QuickSelect(numbers, startIndex, lowLastIndex, k);
77: }
78: return QuickSelect(numbers, lowLastIndex + 1, endIndex, k);
79: }
81: public static void main(String[] args)
82: {
83: int[] numbers = { 6, 2, 12, 8, 4, 3, 19, 17, 22, 41, 7, 1, 15 };
84: System.out.println("Original array: " + Arrays.toString(numbers));
86: // Get k from user
87: Scanner scnr = new Scanner(System.in);
88: int k = scnr.nextInt();
89: int kthValue = QuickSelect(numbers, 0, numbers.length - 1, k);
91: // Display results, and compare to sorted list.
92: System.out.printf
93: (
94: "After QuickSelect(%d): %s%n",
95: k,
96: Arrays.toString(numbers)
97: );
98: System.out.printf
99: (
100: "QuickSelect(%d) result: %d%n",
101: k,
102: kthValue
103: );
105: System.out.println();
106: Arrays.sort(numbers);
107: System.out.println("Sorted list: " + Arrays.toString(numbers));
108: System.out.printf("kth sorted item: %d%n", numbers[k]);
109: }
110: }