Class Selection
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].
- 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
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionprivate static void
doSelect
(double[] a, int fromIndex, int toIndex, int k) Partition the array such that indexk
corresponds to its correctly sorted value in the equivalent fully sorted array.private static void
doSelect
(double[] a, int fromIndex, int toIndex, int[] k) Partition the array such that indicesk
correspond to their correctly sorted value in the equivalent fully sorted array.static void
select
(double[] a, int k) Partition the array such that indexk
corresponds to its correctly sorted value in the equivalent fully sorted array.static void
select
(double[] a, int[] k) Partition the array such that indicesk
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 indexk
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 indicesk
correspond to their correctly sorted value in the equivalent fully sorted array.static void
select
(int[] a, int k) Partition the array such that indexk
corresponds to its correctly sorted value in the equivalent fully sorted array.static void
select
(int[] a, int[] k) Partition the array such that indicesk
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 indexk
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 indicesk
correspond to their correctly sorted value in the equivalent fully sorted array.
-
Constructor Details
-
Selection
private Selection()No instances.
-
-
Method Details
-
select
public static void select(double[] a, int k) Partition the array such that indexk
corresponds to its correctly sorted value in the equivalent fully sorted array.- Parameters:
a
- Values.k
- Index.- Throws:
IndexOutOfBoundsException
- if indexk
is not within the sub-range[0, a.length)
-
select
public static void select(double[] a, int[] k) Partition the array such that indicesk
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 indexk
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 indexk
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 indexk
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 indicesk
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 indexk
is not within the sub-range[fromIndex, toIndex)
-
doSelect
private static void doSelect(double[] a, int fromIndex, int toIndex, int k) Partition the array such that indexk
corresponds to its correctly sorted value in the equivalent fully sorted array.This method pre/post-processes the data and indices to respect the ordering imposed by
Double.compare(double, double)
.- Parameters:
a
- Values.fromIndex
- Index of the first element (inclusive).toIndex
- Index of the last element (exclusive).k
- Index.
-
doSelect
private static void doSelect(double[] a, int fromIndex, int toIndex, int[] k) Partition the array such that indicesk
correspond to their correctly sorted value in the equivalent fully sorted array.This method pre/post-processes the data and indices to respect the ordering imposed by
Double.compare(double, double)
.- Parameters:
a
- Values.fromIndex
- Index of the first element (inclusive).toIndex
- Index of the last element (exclusive).k
- Indices (may be destructively modified).
-
select
public static void select(int[] a, int k) Partition the array such that indexk
corresponds to its correctly sorted value in the equivalent fully sorted array.- Parameters:
a
- Values.k
- Index.- Throws:
IndexOutOfBoundsException
- if indexk
is not within the sub-range[0, a.length)
-
select
public static void select(int[] a, int[] k) Partition the array such that indicesk
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 indexk
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 indexk
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 indexk
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 indicesk
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 indexk
is not within the sub-range[fromIndex, toIndex)
-