Package org.apache.commons.math3.util
Class KthSelector
java.lang.Object
org.apache.commons.math3.util.KthSelector
- All Implemented Interfaces:
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:
-
Field Summary
FieldsModifier and TypeFieldDescriptionprivate static final int
Minimum selection size for insertion sort rather than selection.private final PivotingStrategyInterface
APivotingStrategyInterface
used for pivotingprivate static final long
Serializable UID. -
Constructor Summary
ConstructorsConstructorDescriptionConstructor with defaultmedian of 3
pivoting strategyKthSelector
(PivotingStrategyInterface pivotingStrategy) Constructor with specified pivoting strategy -
Method Summary
Modifier and TypeMethodDescriptionGet 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 Details
-
serialVersionUID
private static final long serialVersionUIDSerializable UID.- See Also:
-
MIN_SELECT_SIZE
private static final int MIN_SELECT_SIZEMinimum selection size for insertion sort rather than selection.- See Also:
-
pivotingStrategy
APivotingStrategyInterface
used for pivoting
-
-
Constructor Details
-
KthSelector
public KthSelector()Constructor with defaultmedian of 3
pivoting strategy -
KthSelector
Constructor with specified pivoting strategy- Parameters:
pivotingStrategy
- pivoting strategy to use- Throws:
NullArgumentException
- when pivotingStrategy is null- See Also:
-
-
Method Details
-
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
-