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
kcorrespond to their correctly sorted value in the equivalent fully sorted array. For all indiceskand any indexi: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
nvalues 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 rangekaand then selecting the remaining elements(ka, kb]that are at the edge of the partition bounded byka.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
nindices can be split isn - 1before 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 byDouble.compare(double, double).-0.0is treated as less than value0.0;Double.NaNis considered greater than any other value; and allDouble.NaNvalues are considered equal.References
Quickselect is introduced in Hoare [1]. This selects an element
kfromnusing repeat division of the data around a partition element, recursing into the partition that containsk.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
kin 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].
- Hoare (1961) Algorithm 65: Find Comm. ACM. 4 (7): 321–322
- Musser (1999) Introspective Sorting and Selection Algorithms Software: Practice and Experience 27, 983-993.
- Floyd and Rivest (1975) Algorithm 489: The Algorithm SELECT—for Finding the ith Smallest of n elements. Comm. ACM. 18 (3): 173.
- Kiwiel (2005) On Floyd and Rivest's SELECT algorithm. Theoretical Computer Science 347, 214-238.
- Blum, Floyd, Pratt, Rivest, and Tarjan (1973) Time bounds for selection. Journal of Computer and System Sciences. 7 (4): 448–461.
- Alexandrescu (2016) Fast Deterministic Selection arXiv:1606.00484.
- Quickselect (Wikipedia)
- Introsort (Wikipedia)
- Introselect (Wikipedia)
- Floyd-Rivest algorithm (Wikipedia)
- Median of medians (Wikipedia)
- Since:
- 1.2
-
-
Method Summary
All Methods Static Methods Concrete Methods Modifier and Type Method Description static voidselect(double[] a, int k)Partition the array such that indexkcorresponds to its correctly sorted value in the equivalent fully sorted array.static voidselect(double[] a, int[] k)Partition the array such that indiceskcorrespond to their correctly sorted value in the equivalent fully sorted array.static voidselect(double[] a, int fromIndex, int toIndex, int k)Partition the array such that indexkcorresponds to its correctly sorted value in the equivalent fully sorted array.static voidselect(double[] a, int fromIndex, int toIndex, int[] k)Partition the array such that indiceskcorrespond to their correctly sorted value in the equivalent fully sorted array.static voidselect(int[] a, int k)Partition the array such that indexkcorresponds to its correctly sorted value in the equivalent fully sorted array.static voidselect(int[] a, int[] k)Partition the array such that indiceskcorrespond to their correctly sorted value in the equivalent fully sorted array.static voidselect(int[] a, int fromIndex, int toIndex, int k)Partition the array such that indexkcorresponds to its correctly sorted value in the equivalent fully sorted array.static voidselect(int[] a, int fromIndex, int toIndex, int[] k)Partition the array such that indiceskcorrespond to their correctly sorted value in the equivalent fully sorted array.
-
-
-
Method Detail
-
select
public static void select(double[] a, int k)
Partition the array such that indexkcorresponds to its correctly sorted value in the equivalent fully sorted array.- Parameters:
a- Values.k- Index.- Throws:
IndexOutOfBoundsException- if indexkis not within the sub-range[0, a.length)
-
select
public static void select(double[] a, int[] k)
Partition the array such that indiceskcorrespond to their correctly sorted value in the equivalent fully sorted array.- Parameters:
a- Values.k- Indices (may be destructively modified).- Throws:
IndexOutOfBoundsException- if any indexkis 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 indexkcorresponds 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 indexkis 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 indiceskcorrespond 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 indexkis not within the sub-range[fromIndex, toIndex)
-
select
public static void select(int[] a, int k)
Partition the array such that indexkcorresponds to its correctly sorted value in the equivalent fully sorted array.- Parameters:
a- Values.k- Index.- Throws:
IndexOutOfBoundsException- if indexkis not within the sub-range[0, a.length)
-
select
public static void select(int[] a, int[] k)
Partition the array such that indiceskcorrespond to their correctly sorted value in the equivalent fully sorted array.- Parameters:
a- Values.k- Indices (may be destructively modified).- Throws:
IndexOutOfBoundsException- if any indexkis 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 indexkcorresponds 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 indexkis 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 indiceskcorrespond 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 indexkis not within the sub-range[fromIndex, toIndex)
-
-