Top Description Fields Constructors Methods
org.apache.commons.math3.util

public Class KthSelector

extends Object
implements Serializable
Class Inheritance
All Implemented Interfaces
java.io.Serializable
Imports
java.io.Serializable, java.util.Arrays, org.apache.commons.math3.exception.NullArgumentException
A Simple Kth selector implementation to pick up the Kth ordered element from a work array containing the input numbers.
Since
3.4

Field Summary

Modifier and TypeField and Description
private static final int
MIN_SELECT_SIZE

Minimum selection size for insertion sort rather than selection.

private final PivotingStrategyInterface
pivotingStrategy

A PivotingStrategyInterface used for pivoting

private static final long
serialVersionUID

Serializable UID.

Constructor Summary

AccessConstructor and Description
public
KthSelector()

Constructor with default median of 3 pivoting strategy

public
KthSelector(final PivotingStrategyInterface
pivoting strategy to use
pivotingStrategy)

Constructor with specified pivoting strategy

Method Summary

Modifier and TypeMethod and Description
public PivotingStrategyInterface

Returns:

pivoting strategy
getPivotingStrategy()

Get the pivotin strategy.

private int

Returns:

index of the pivot after partition
partition(final double[]
work array
work, final int
index of the first element of the slice of work array
begin, final int
index after the last element of the slice of work array
end, final int
initial index of the pivot
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.

public double

Returns:

Kth value
select(final double[]
work array to use to find out the Kth value
work, final int[]
cached pivots heap that can be used for efficient estimation
pivotsHeap, final int
the index whose value in the array is of interest
k)

Select Kth value in the array.

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

MIN_SELECT_SIZEback to summary
private static final int MIN_SELECT_SIZE

Minimum selection size for insertion sort rather than selection.

pivotingStrategyback to summary
private final PivotingStrategyInterface pivotingStrategy

A PivotingStrategyInterface used for pivoting

serialVersionUIDback to summary
private static final long serialVersionUID

Serializable UID.

Constructor Detail

KthSelectorback to summary
public KthSelector()

Constructor with default median of 3 pivoting strategy

KthSelectorback to summary
public KthSelector(final PivotingStrategyInterface pivotingStrategy) throws NullArgumentException

Constructor with specified pivoting strategy

Parameters
pivotingStrategy:PivotingStrategyInterface

pivoting strategy to use

Exceptions
NullArgumentException:
when pivotingStrategy is null
See Also
MedianOf3PivotingStrategy, RandomPivotingStrategy, CentralPivotingStrategy

Method Detail

getPivotingStrategyback to summary
public PivotingStrategyInterface getPivotingStrategy()

Get the pivotin strategy.

Returns:PivotingStrategyInterface

pivoting strategy

partitionback to summary
private int partition(final double[] work, final int begin, final int end, final 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:double[]

work array

begin:int

index of the first element of the slice of work array

end:int

index after the last element of the slice of work array

pivot:int

initial index of the pivot

Returns:int

index of the pivot after partition

selectback to summary
public double select(final double[] work, final int[] pivotsHeap, final int k)

Select Kth value in the array.

Parameters
work:double[]

work array to use to find out the Kth value

pivotsHeap:int[]

cached pivots heap that can be used for efficient estimation

k:int

the index whose value in the array is of interest

Returns:double

Kth value