-
Notifications
You must be signed in to change notification settings - Fork 3
/
QuickSelect.java
87 lines (63 loc) · 2.41 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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
import java.util.Random;
import Sort.QuickSort;
public class QuickSelect {
private static final Random random = new Random();
private QuickSelect() {
}
/**
* Given an array of integers, find the ith smallest
* number in it. Warning: this method doesn't preserve
* the order of the elements. If this is crucial, pass an
* copy of your array. If you use this method an big amount
* of times, sorting and then simply choosing will be more
* efficient.
*
* @param numbers
* @param index
*/
public static int select(int[] numbers, int index) {
return select(numbers, 0, numbers.length - 1, index);
}
private static int select(int[] numbers, int low, int high, int index) {
if (high == low) return numbers[index];
int pivotIndex = getRandomIndex(low, high);
int pivotPosition = QuickSort.partition(numbers, low, high, pivotIndex);
if (pivotPosition == index) return numbers[index];
if (index < pivotPosition) {
return select(numbers, low, pivotPosition - 1, index);
} else {
return select(numbers, pivotPosition + 1, high, index);
}
}
/**
* Given an array of comparable objects, find the ith smallest
* object in it. Warning: this method doesn't preserve
* the order of the elements. If this is crucial, pass an
* copy of your array. If you use this method an big amount
* of times, sorting and then simply choosing will be more
* efficient, if memory is not a problem.
*
* @param numbers
* @param index
*/
public static Comparable select(Comparable[] numbers, int index) {
return select(numbers, 0, numbers.length - 1, index);
}
private static Comparable select(Comparable[] array, int low, int high, int index) {
if (high == low) return array[index];
int pivotIndex = getRandomIndex(low, high);
int pivotPosition = QuickSort.partition(array, low, high, pivotIndex);
if (pivotPosition == index) return array[index];
if (index < pivotPosition) {
return select(array, low, pivotPosition - 1, index);
} else {
return select(array, pivotPosition + 1, high, index);
}
}
/**
* Helper methods
*/
private static int getRandomIndex(int low, int high) {
return random.nextInt(high - low + 1) + low;
}
}