public abstract class IntroSelector extends Selector
It uses the median of the first, middle and last values as a pivot and
falls back to a median of medians when the number of recursion levels exceeds
2 lg(n)
, as a consequence it runs in linear time on average.
Constructor and Description |
---|
IntroSelector() |
Modifier and Type | Method and Description |
---|---|
protected int |
compare(int i,
int j)
Compare entries found in slots
i and j . |
protected abstract int |
comparePivot(int j)
Compare the pivot with the slot at
j , similarly to
compare(i, j) . |
(package private) int |
medianOfMediansSelect(int left,
int right,
int k) |
private int |
partition(int left,
int right,
int k,
int pivotIndex) |
private int |
partition5(int left,
int right) |
private int |
pivot(int left,
int right) |
private void |
quickSelect(int from,
int to,
int k,
int maxDepth) |
void |
select(int from,
int to,
int k)
Reorder elements so that the element at position
k is the same
as if all elements were sorted and all other elements are partitioned
around it: [from, k) only contains elements that are less than
or equal to k and (k, to) only contains elements that
are greater than or equal to k . |
protected abstract void |
setPivot(int i)
Save the value at slot
i so that it can later be used as a
pivot, see comparePivot(int) . |
(package private) int |
slowSelect(int from,
int to,
int k) |
public final void select(int from, int to, int k)
Selector
k
is the same
as if all elements were sorted and all other elements are partitioned
around it: [from, k)
only contains elements that are less than
or equal to k
and (k, to)
only contains elements that
are greater than or equal to k
.int slowSelect(int from, int to, int k)
int medianOfMediansSelect(int left, int right, int k)
private int partition(int left, int right, int k, int pivotIndex)
private int pivot(int left, int right)
private int partition5(int left, int right)
private void quickSelect(int from, int to, int k, int maxDepth)
protected int compare(int i, int j)
i
and j
.
The contract for the returned value is the same as
Comparator.compare(Object, Object)
.protected abstract void setPivot(int i)
i
so that it can later be used as a
pivot, see comparePivot(int)
.protected abstract int comparePivot(int j)
j
, similarly to
compare(i, j)
.