public class KthSelector
extends java.lang.Object
implements java.io.Serializable
Modifier and Type | Field and Description |
---|---|
private static int |
MIN_SELECT_SIZE
Minimum selection size for insertion sort rather than selection.
|
private PivotingStrategyInterface |
pivotingStrategy
A
PivotingStrategyInterface used for pivoting |
private static long |
serialVersionUID
Serializable UID.
|
Constructor and Description |
---|
KthSelector()
Constructor with default
median of 3 pivoting strategy |
KthSelector(PivotingStrategyInterface pivotingStrategy)
Constructor with specified pivoting strategy
|
Modifier and Type | Method and Description |
---|---|
PivotingStrategyInterface |
getPivotingStrategy()
Get the pivotin strategy.
|
private int |
partition(double[] work,
int begin,
int end,
int pivot)
Partition an array slice around a pivot.Partitioning exchanges array
elements such that all elements smaller than pivot are before it and
all elements larger than pivot are after it.
|
double |
select(double[] work,
int[] pivotsHeap,
int k)
Select Kth value in the array.
|
private static final long serialVersionUID
private static final int MIN_SELECT_SIZE
private final PivotingStrategyInterface pivotingStrategy
PivotingStrategyInterface
used for pivotingpublic KthSelector()
median of 3
pivoting strategypublic KthSelector(PivotingStrategyInterface pivotingStrategy) throws NullArgumentException
pivotingStrategy
- pivoting strategy to useNullArgumentException
- when pivotingStrategy is nullMedianOf3PivotingStrategy
,
RandomPivotingStrategy
,
CentralPivotingStrategy
public PivotingStrategyInterface getPivotingStrategy()
public double select(double[] work, int[] pivotsHeap, int k)
work
- work array to use to find out the Kth valuepivotsHeap
- cached pivots heap that can be used for efficient estimationk
- the index whose value in the array is of interestprivate int partition(double[] work, int begin, int end, int pivot)
work
- work arraybegin
- index of the first element of the slice of work arrayend
- index after the last element of the slice of work arraypivot
- initial index of the pivot