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 K^th selector implementation to pick up the K^th ordered element from a work array containing the input numbers.

Since:

3.4

See Also:

Serialized Form

Field Summary

Fields

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 Summary

Constructors

Constructor and Description
KthSelector() Constructor with default median of 3 pivoting strategy
KthSelector(PivotingStrategyInterface pivotingStrategy) Constructor with specified pivoting strategy

Method Summary

Methods

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.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

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

A PivotingStrategyInterface used for pivoting

Constructor Detail

KthSelector

public KthSelector()

Constructor with default median 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 K^th value in the array.

Parameters:

work - work array to use to find out the K^th value

pivotsHeap - cached pivots heap that can be used for efficient estimation

k - the index whose value in the array is of interest

Returns:

K^th 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 array

begin - index of the first element of the slice of work array

end - index after the last element of the slice of work array

pivot - initial index of the pivot

Returns:

index of the pivot after partition