Package org.apache.commons.numbers.arrays

Class Selection

java.lang.Object

org.apache.commons.numbers.arrays.Selection

public final class Selection
extends Object

Select indices in array data.

Arranges elements such that indices k correspond to their correctly sorted value in the equivalent fully sorted array. For all indices k and any index i:

 data[i < k] <= data[k] <= data[k < i]
 

Examples:

 data    [0, 1, 2, 1, 2, 5, 2, 3, 3, 6, 7, 7, 7, 7]


 k=4   : [0, 1, 2, 1], [2], [5, 2, 3, 3, 6, 7, 7, 7, 7]
 k=4,8 : [0, 1, 2, 1], [2], [3, 3, 2], [5], [6, 7, 7, 7, 7]
 

This implementation can select on multiple indices and will handle duplicate and unordered indices. The method detects ordered indices (with or without duplicates) and uses this during processing. Passing ordered indices is recommended if the order is already known; for example using uniform spacing through the array data, or to select the top and bottom n values from the data.

A quickselect adaptive method is used for single indices. This uses analysis of the partition sizes after each division to update the algorithm mode. If the partition containing the target does not sufficiently reduce in size then the algorithm is progressively changed to use partitions with guaranteed margins. This ensures a set fraction of data is eliminated each step and worse-case linear run time performance. This method can handle a range of indices [ka, kb] with a small separation by targeting the start of the range ka and then selecting the remaining elements (ka, kb] that are at the edge of the partition bounded by ka.

Multiple keys are partitioned collectively using an introsort method which only recurses into partitions containing indices. Excess recursion will trigger use of a heapselect on the remaining range of indices ensuring non-quadratic worse case performance. Any partition containing a single index, adjacent pair of indices, or range of indices with a small separation will use the quickselect adaptive method for single keys. Note that the maximum number of times that n indices can be split is n - 1 before all indices are handled as singles.

Floating-point order

The < relation does not impose a total order on all floating-point values. This class respects the ordering imposed by Double.compare(double, double). -0.0 is treated as less than value 0.0; Double.NaN is considered greater than any other value; and all Double.NaN values are considered equal.

References

Quickselect is introduced in Hoare [1]. This selects an element k from n using repeat division of the data around a partition element, recursing into the partition that contains k.

Introsort/select is introduced in Musser [2]. This detects excess recursion in quicksort/select and reverts to a heapsort or linear select to achieve an improved worst case bound.

Use of sampling to identify a pivot that places k in the smaller partition is performed in the SELECT algorithm of Floyd and Rivest [3, 4].

A worst-case linear time algorithm PICK is described in Blum et al [5]. This uses the median of medians as a partition element for selection which ensures a minimum fraction of the elements are eliminated per iteration. This was extended to use an asymmetric pivot choice with efficient placement of the medians sample location in the QuickselectAdpative algorithm of Alexandrescu [6].

1. Hoare (1961) Algorithm 65: Find Comm. ACM. 4 (7): 321–322
2. Musser (1999) Introspective Sorting and Selection Algorithms Software: Practice and Experience 27, 983-993.
3. Floyd and Rivest (1975) Algorithm 489: The Algorithm SELECT—for Finding the ith Smallest of n elements. Comm. ACM. 18 (3): 173.
4. Kiwiel (2005) On Floyd and Rivest's SELECT algorithm. Theoretical Computer Science 347, 214-238.
5. Blum, Floyd, Pratt, Rivest, and Tarjan (1973) Time bounds for selection. Journal of Computer and System Sciences. 7 (4): 448–461.
6. Alexandrescu (2016) Fast Deterministic Selection arXiv:1606.00484.
7. Quickselect (Wikipedia)
8. Introsort (Wikipedia)
9. Introselect (Wikipedia)
10. Floyd-Rivest algorithm (Wikipedia)
11. Median of medians (Wikipedia)

Since:

1.2

Method Summary

Modifier and Type	Method	Description
static void	select(double[] a, int k)	Partition the array such that index k corresponds to its correctly sorted value in the equivalent fully sorted array.
static void	select(double[] a, int[] k)	Partition the array such that indices k correspond to their correctly sorted value in the equivalent fully sorted array.
static void	select(double[] a, int fromIndex, int toIndex, int k)	Partition the array such that index k corresponds to its correctly sorted value in the equivalent fully sorted array.
static void	select(double[] a, int fromIndex, int toIndex, int[] k)	Partition the array such that indices k correspond to their correctly sorted value in the equivalent fully sorted array.
static void	select(int[] a, int k)	Partition the array such that index k corresponds to its correctly sorted value in the equivalent fully sorted array.
static void	select(int[] a, int[] k)	Partition the array such that indices k correspond to their correctly sorted value in the equivalent fully sorted array.
static void	select(int[] a, int fromIndex, int toIndex, int k)	Partition the array such that index k corresponds to its correctly sorted value in the equivalent fully sorted array.
static void	select(int[] a, int fromIndex, int toIndex, int[] k)	Partition the array such that indices k correspond to their correctly sorted value in the equivalent fully sorted array.

Methods inherited from class java.lang.Object

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

Method Detail

select

public static void select(double[] a,
                          int k)

Partition the array such that index k corresponds to its correctly sorted value in the equivalent fully sorted array.

Parameters:

a - Values.

k - Index.

Throws:

IndexOutOfBoundsException - if index k is not within the sub-range [0, a.length)

select

public static void select(double[] a,
                          int[] k)

Partition the array such that indices k correspond to their correctly sorted value in the equivalent fully sorted array.

Parameters:

a - Values.

k - Indices (may be destructively modified).

Throws:

IndexOutOfBoundsException - if any index k is not within the sub-range [0, a.length)

select

public static void select(double[] a,
                          int fromIndex,
                          int toIndex,
                          int k)

Partition the array such that index k corresponds to its correctly sorted value in the equivalent fully sorted array.

Parameters:

a - Values.

fromIndex - Index of the first element (inclusive).

toIndex - Index of the last element (exclusive).

k - Index.

Throws:

IndexOutOfBoundsException - if the sub-range [fromIndex, toIndex) is out of bounds of range [0, a.length); or if index k is not within the sub-range [fromIndex, toIndex)

select

public static void select(double[] a,
                          int fromIndex,
                          int toIndex,
                          int[] k)

Partition the array such that indices k correspond to their correctly sorted value in the equivalent fully sorted array.

Parameters:

a - Values.

fromIndex - Index of the first element (inclusive).

toIndex - Index of the last element (exclusive).

k - Indices (may be destructively modified).

Throws:

IndexOutOfBoundsException - if the sub-range [fromIndex, toIndex) is out of bounds of range [0, a.length); or if any index k is not within the sub-range [fromIndex, toIndex)

select

public static void select(int[] a,
                          int k)

Partition the array such that index k corresponds to its correctly sorted value in the equivalent fully sorted array.

Parameters:

a - Values.

k - Index.

Throws:

IndexOutOfBoundsException - if index k is not within the sub-range [0, a.length)

select

public static void select(int[] a,
                          int[] k)

Partition the array such that indices k correspond to their correctly sorted value in the equivalent fully sorted array.

Parameters:

a - Values.

k - Indices (may be destructively modified).

Throws:

IndexOutOfBoundsException - if any index k is not within the sub-range [0, a.length)

select

public static void select(int[] a,
                          int fromIndex,
                          int toIndex,
                          int k)

Partition the array such that index k corresponds to its correctly sorted value in the equivalent fully sorted array.

Parameters:

a - Values.

fromIndex - Index of the first element (inclusive).

toIndex - Index of the last element (exclusive).

k - Index.

Throws:

IndexOutOfBoundsException - if the sub-range [fromIndex, toIndex) is out of bounds of range [0, a.length); or if index k is not within the sub-range [fromIndex, toIndex)

select

public static void select(int[] a,
                          int fromIndex,
                          int toIndex,
                          int[] k)

Partition the array such that indices k correspond to their correctly sorted value in the equivalent fully sorted array.

Parameters:

a - Values.

fromIndex - Index of the first element (inclusive).

toIndex - Index of the last element (exclusive).

k - Indices (may be destructively modified).

Throws:

IndexOutOfBoundsException - if the sub-range [fromIndex, toIndex) is out of bounds of range [0, a.length); or if any index k is not within the sub-range [fromIndex, toIndex)