/
QuickSelect.java
74 lines (61 loc) · 3.04 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
package com.yunikov.algorithms.selection;
import com.yunikov.algorithms.util.ArrayUtils;
import java.util.Random;
/**
* QuickSelect (Randomized selection) algorithm for finding n-th ranked (minimum) element in the array.
* Based on the same idea as QuickSort algorithm.
* Running time is O(n*log(n)).
*/
public class QuickSelect extends Selection {
private final Random random = new Random(System.currentTimeMillis());
@Override
protected int doSelect(final int[] array, final int rankElementIndex) {
return randomizedSelect(array, rankElementIndex, 0, array.length);
}
/**
* Randomly chooses pivot index between start point and the end point.
*
* @param startPoint lowest bound to choose the pivot from
* @param endPoint highest bound to choose the pivot from
* @return pivot index between start point and end point
*/
protected int choosePivotIndex(final int startPoint, final int endPoint) {
if (startPoint == endPoint) {
return startPoint;
}
return random.nextInt(endPoint - startPoint) + startPoint;
}
private int randomizedSelect(final int[] array, final int rankElementIndex, final int leftIndex, final int rightIndex) {
if (leftIndex < rightIndex) {
final int pivotIndex = choosePivotIndex(leftIndex, rightIndex - 1);
final int newPivotIndex = partition(array, pivotIndex, leftIndex, rightIndex);
if (newPivotIndex > rankElementIndex) {
randomizedSelect(array, rankElementIndex, leftIndex, newPivotIndex);
} else if (newPivotIndex < rankElementIndex) {
randomizedSelect(array, rankElementIndex, newPivotIndex + 1, rightIndex);
} else {
return array[newPivotIndex];
}
}
return array[rankElementIndex];
}
private int partition(final int[] array, final int pivotIndex, final int leftIndex, final int rightIndex) {
// put the pivot to the first position of part to be sorted
ArrayUtils.swap(array, leftIndex, pivotIndex);
final int pivot = array[leftIndex];
int partitionedMiddle = leftIndex + 1; // holds the middle point between partitioned elements
// left from partitionedMiddle are less than the pivot, right from partitionedMiddle are bigger than the pivot
for (int currentPosition = leftIndex + 1; currentPosition < rightIndex; currentPosition++) {
// swap only if element is less than the pivot
// otherwise it stays on the right part (where the bigger elements than the pivot are)
if (array[currentPosition] < pivot) {
ArrayUtils.swap(array, currentPosition, partitionedMiddle);
partitionedMiddle++;
}
}
// place the pivot at the partitioned middle
// so elements less than the pivot are left from it, and the ones bigger than the pivot are right from it
ArrayUtils.swap(array, leftIndex, partitionedMiddle - 1);
return partitionedMiddle - 1;
}
}