Package org.apache.commons.math3.util
Class KthSelector
- java.lang.Object
-
- org.apache.commons.math3.util.KthSelector
-
- All Implemented Interfaces:
java.io.Serializable
public class KthSelector extends java.lang.Object implements java.io.Serializable
A Simple Kth selector implementation to pick up the Kth ordered element from a work array containing the input numbers.- Since:
- 3.4
- See Also:
- Serialized Form
-
-
Field Summary
Fields Modifier and Type Field Description private static int
MIN_SELECT_SIZE
Minimum selection size for insertion sort rather than selection.private PivotingStrategyInterface
pivotingStrategy
APivotingStrategyInterface
used for pivotingprivate static long
serialVersionUID
Serializable UID.
-
Constructor Summary
Constructors Constructor Description KthSelector()
Constructor with defaultmedian of 3
pivoting strategyKthSelector(PivotingStrategyInterface pivotingStrategy)
Constructor with specified pivoting strategy
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method 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.
-
-
-
Field Detail
-
serialVersionUID
private static final long serialVersionUID
Serializable UID.- See Also:
- Constant Field Values
-
MIN_SELECT_SIZE
private static final int MIN_SELECT_SIZE
Minimum selection size for insertion sort rather than selection.- See Also:
- Constant Field Values
-
pivotingStrategy
private final PivotingStrategyInterface pivotingStrategy
APivotingStrategyInterface
used for pivoting
-
-
Constructor Detail
-
KthSelector
public KthSelector()
Constructor with defaultmedian of 3
pivoting strategy
-
KthSelector
public KthSelector(PivotingStrategyInterface pivotingStrategy) throws NullArgumentException
Constructor with specified pivoting strategy- Parameters:
pivotingStrategy
- pivoting strategy to use- Throws:
NullArgumentException
- when pivotingStrategy is null- See Also:
MedianOf3PivotingStrategy
,RandomPivotingStrategy
,CentralPivotingStrategy
-
-
Method Detail
-
getPivotingStrategy
public PivotingStrategyInterface getPivotingStrategy()
Get the pivotin strategy.- Returns:
- pivoting strategy
-
select
public double select(double[] work, int[] pivotsHeap, int k)
Select Kth value in the array.- Parameters:
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 interest- Returns:
- Kth value
-
partition
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.- Parameters:
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- Returns:
- index of the pivot after partition
-
-