-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathQuickSelect.java
66 lines (59 loc) · 1.64 KB
/
QuickSelect.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
public class QuickSelect {
private static boolean less(Comparable a, Comparable b) {
return a.compareTo(b) < 0;
}
private static void exchange(Comparable[] a, int i, int j) {
Comparable temp = a[i];
a[i] = a[j];
a[j] = temp;
}
private static int partition(Comparable[] a, int low, int high) {
int i = low;
int j = high + 1;
while (true) {
while (less(a[i++], a[low])) {
if (i == high) {
break;
}
}
while (less(a[low], a[--j])) {
if (j == low) {
break;
}
}
if (j <= i) {
break;
}
exchange(a, i, j);
}
exchange(a, low, j);
return j;
}
private static Comparable select(Comparable[] a, int k) {
int low = 0;
int high = a.length - 1;
while (high > low) {
int j = partition(a, low, high);
if (j < k) {
low = j + 1;
} else if (k < j) {
high = j - 1;
} else {
break;
}
}
return a[k];
}
public static void print(Object[] array) {
for (Object a : array) {
System.out.print(a + " ");
}
System.out.println("");
}
public static void main(String[] args) {
String[] array = {"Eve", "Charlie", "Bob", "Hope", "Alice", "Tom"};
QuickSelect.print(array);
String median = (String)QuickSelect.select(array, 1);
System.out.println(median);
}
}