java.lang.Object
- org.apache.commons.numbers.arrays.QuickSelect

```
final class QuickSelect
extends java.lang.Object
```
Partition array data.
Note: Requires that the floating-point data contains no NaN values; sorting does not respect the order of signed zeros imposed by Double.compare(double, double); mixed signed zeros may be destroyed (the mixture updated during partitioning). The caller is responsible for counting a mixture of signed zeros and restoring them if required.

Since:

1.2

See Also:

Selection

Field Summary

Fields
Modifier and Type	Field	Description
`private static int`	`DP_SORTSELECT_SIZE`	Dual-pivot sortselect size for the distance of a single k from the edge of the range length n.
`private static int`	`FR_SAMPLING_SIZE`	Threshold to use Floyd-Rivest sub-sampling.
`private static int`	`LINEAR_SORTSELECT_SIZE`	Single-pivot sortselect size for quickselect adaptive.
`private static int`	`MIN_SORTSELECT_SIZE`	Minimum size for sortselect.
`(package private) static int`	`MODE_ADAPTION`	No sampling but use adaption of the target k.
`(package private) static int`	`MODE_FR_SAMPLING`	Sampling mode using Floyd-Rivest sampling.
`(package private) static int`	`MODE_SAMPLING`	Sampling mode.
`(package private) static int`	`MODE_STRICT`	No sampling and no adaption of target k (strict margins).
`private static int`	`RECURSION_INCREMENT`	Increment used for the recursion counter.
`private static int`	`SORTSELECT_MASK`	Mask to extract the sort select size from the dual-pivot control flags.
`private static double`	`STEP_FAR_LEFT`	Threshold to use repeated step far-left: 1 / 12.
`private static double`	`STEP_FAR_RIGHT`	Threshold to use repeated step far-right: 11 / 12.
`private static double`	`STEP_LEFT`	Threshold to use repeated step left: 7 / 16.
`private static double`	`STEP_RIGHT`	Threshold to use repeated step right: 9 / 16.

Constructor Summary

Constructors
Modifier Constructor Description

private QuickSelect()
No instances.

Method Summary

All Methods Static Methods Concrete Methods
Modifier and Type	Method	Description
`(package private) static int`	`dualPivotFlags(int maxDepth, int ss)`	Configure the dual-pivot control flags.
`private static int`	`dualPivotFlags(int left, int right, int k1, int kn)`	Configure the dual-pivot control flags.
`(package private) static int`	`dualPivotMaxDepth(int x)`	Compute the maximum recursion depth for dual pivot recursion.
`(package private) static void`	`dualPivotQuickSelect(double[] a, int left, int right, UpdatingInterval k, int flags)`	Partition the array such that indices `k` correspond to their correctly sorted value in the equivalent fully sorted array.
`(package private) static void`	`dualPivotQuickSelect(int[] a, int left, int right, UpdatingInterval k, int flags)`	Partition the array such that indices `k` correspond to their correctly sorted value in the equivalent fully sorted array.
`private static int`	`dualPivotSortSelectSize(int k1, int kn)`	Configure the sort select size for dual pivot partitioning.
`(package private) static int`	`expandPartition(double[] a, int left, int right, int start, int end, int pivot0, int pivot1, int[] upper)`	Expand a partition around a single pivot.
`(package private) static int`	`expandPartition(int[] a, int left, int right, int start, int end, int pivot0, int pivot1, int[] upper)`	Expand a partition around a single pivot.
`(package private) static void`	`heapSelect(double[] a, int left, int right, int ka, int kb)`	Partition the elements between `ka` and `kb` using a heap select algorithm.
`(package private) static void`	`heapSelect(int[] a, int left, int right, int ka, int kb)`	Partition the elements between `ka` and `kb` using a heap select algorithm.
`(package private) static void`	`heapSelectLeft(double[] a, int left, int right, int ka, int kb)`	Partition the elements between `ka` and `kb` using a heap select algorithm.
`(package private) static void`	`heapSelectLeft(int[] a, int left, int right, int ka, int kb)`	Partition the elements between `ka` and `kb` using a heap select algorithm.
`(package private) static void`	`heapSelectRight(double[] a, int left, int right, int ka, int kb)`	Partition the elements between `ka` and `kb` using a heap select algorithm.
`(package private) static void`	`heapSelectRight(int[] a, int left, int right, int ka, int kb)`	Partition the elements between `ka` and `kb` using a heap select algorithm.
`private static int`	`mapDistance(int d, int l, int r, int n)`	Map the distance from the edge of `[l, r]` to a new distance in `[0, n)`.
`private static void`	`maxHeapSiftDown(double[] a, double v, int p, int root, int end)`	Sift the element down the max heap.
`private static void`	`maxHeapSiftDown(int[] a, int v, int p, int root, int end)`	Sift the element down the max heap.
`private static void`	`minHeapSiftDown(double[] a, double v, int p, int root, int end)`	Sift the element down the min heap.
`private static void`	`minHeapSiftDown(int[] a, int v, int p, int root, int end)`	Sift the element down the min heap.
`private static int`	`partition(double[] a, int left, int right, int[] bounds)`	Partition an array slice around 2 pivots.
`private static int`	`partition(int[] a, int left, int right, int[] bounds)`	Partition an array slice around 2 pivots.
`(package private) static int`	`quickSelectAdaptive(double[] a, int left, int right, int ka, int kb, int[] bounds, int flags)`	Partition the array such that indices `k` correspond to their correctly sorted value in the equivalent fully sorted array.
`(package private) static int`	`quickSelectAdaptive(int[] a, int left, int right, int ka, int kb, int[] bounds, int flags)`	Partition the array such that indices `k` correspond to their correctly sorted value in the equivalent fully sorted array.
`private static int`	`repeatedStep(double[] a, int l, int r, int k, int[] upper, int flags)`	Partition an array slice around a pivot.
`private static int`	`repeatedStep(int[] a, int l, int r, int k, int[] upper, int flags)`	Partition an array slice around a pivot.
`private static int`	`repeatedStepFarLeft(double[] a, int l, int r, int k, int[] upper, int flags)`	Partition an array slice around a pivot.
`private static int`	`repeatedStepFarLeft(int[] a, int l, int r, int k, int[] upper, int flags)`	Partition an array slice around a pivot.
`private static int`	`repeatedStepFarRight(double[] a, int l, int r, int k, int[] upper, int flags)`	Partition an array slice around a pivot.
`private static int`	`repeatedStepFarRight(int[] a, int l, int r, int k, int[] upper, int flags)`	Partition an array slice around a pivot.
`private static int`	`repeatedStepLeft(double[] a, int l, int r, int k, int[] upper, int flags)`	Partition an array slice around a pivot.
`private static int`	`repeatedStepLeft(int[] a, int l, int r, int k, int[] upper, int flags)`	Partition an array slice around a pivot.
`private static int`	`repeatedStepRight(double[] a, int l, int r, int k, int[] upper, int flags)`	Partition an array slice around a pivot.
`private static int`	`repeatedStepRight(int[] a, int l, int r, int k, int[] upper, int flags)`	Partition an array slice around a pivot.
`private static int`	`sampleStep(double[] a, int l, int r, int k, int[] upper)`	Partition an array slice around a pivot.
`private static int`	`sampleStep(int[] a, int l, int r, int k, int[] upper)`	Partition an array slice around a pivot.
`(package private) static void`	`select(double[] a, int left, int right, int k)`	Partition the array such that index `k` corresponds to its correctly sorted value in the equivalent fully sorted array.
`(package private) static int`	`select(double[] a, int left, int right, int[] k, int n)`	Partition the array such that indices `k` correspond to their correctly sorted value in the equivalent fully sorted array.
`(package private) static void`	`select(int[] a, int left, int right, int k)`	Partition the array such that index `k` corresponds to its correctly sorted value in the equivalent fully sorted array.
`(package private) static void`	`select(int[] a, int left, int right, int[] k, int n)`	Partition the array such that indices `k` correspond to their correctly sorted value in the equivalent fully sorted array.
`(package private) static void`	`sortSelect(double[] a, int left, int right, int ka, int kb)`	Partition the elements between `ka` and `kb` using a sort select algorithm.
`(package private) static void`	`sortSelect(int[] a, int left, int right, int ka, int kb)`	Partition the elements between `ka` and `kb` using a sort select algorithm.
`(package private) static void`	`sortSelectLeft(double[] a, int left, int right, int k)`	Partition the minimum `n` elements below `k` where `n = k - left + 1`.
`(package private) static void`	`sortSelectLeft(int[] a, int left, int right, int k)`	Partition the minimum `n` elements below `k` where `n = k - left + 1`.
`(package private) static void`	`sortSelectRight(double[] a, int left, int right, int k)`	Partition the maximum `n` elements above `k` where `n = right - k + 1`.
`(package private) static void`	`sortSelectRight(int[] a, int left, int right, int k)`	Partition the maximum `n` elements above `k` where `n = right - k + 1`.

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Field Detail
  - MODE_FR_SAMPLING
```
static final int MODE_FR_SAMPLING
```
    Sampling mode using Floyd-Rivest sampling.
    
    See Also:
    
    Constant Field Values
  - MODE_SAMPLING
```
static final int MODE_SAMPLING
```
    Sampling mode.
    
    See Also:
    
    Constant Field Values
  - MODE_ADAPTION
```
static final int MODE_ADAPTION
```
    No sampling but use adaption of the target k.
    
    See Also:
    
    Constant Field Values
  - MODE_STRICT
```
static final int MODE_STRICT
```
    No sampling and no adaption of target k (strict margins).
    
    See Also:
    
    Constant Field Values
  - MIN_SORTSELECT_SIZE
```
private static final int MIN_SORTSELECT_SIZE
```
    Minimum size for sortselect. Below this perform a sort rather than selection. This is used to avoid sort select on tiny data.
    
    See Also:
    
    Constant Field Values
  - LINEAR_SORTSELECT_SIZE
```
private static final int LINEAR_SORTSELECT_SIZE
```
    Single-pivot sortselect size for quickselect adaptive. Note that quickselect adaptive recursively calls quickselect so very small lengths are included with an initial medium length. Using lengths of 1023-5 and 2043-53 indicate optimum performance around 20-30. Note: The expand partition function assumes a sample of at least length 2 as each end of the sample is used as a sentinel; this imposes a minimum length of 24 on the range to ensure it contains a 12-th tile of length 2. Thus the absolute minimum for the distance from the edge is 12.
    
    See Also:
    
    Constant Field Values
  - DP_SORTSELECT_SIZE
```
private static final int DP_SORTSELECT_SIZE
```
    Dual-pivot sortselect size for the distance of a single k from the edge of the range length n. Benchmarking in range [81+81, 243+243] suggests a value of ~20 (or higher on some hardware). Ranges are chosen based on third interval spacing between powers of 3.
    Sortselect is faster at this small size than heapselect. A second advantage is that all indices closer to the edge than the target index are also sorted. This allows selection of multiple close indices to be performed with effectively the same speed. High density indices will result in recursion to very short fragments which also trigger use of sort select. The threshold for sorting short lengths is configured in dualPivotSortSelectSize(int, int).
    
    See Also:
    
    Constant Field Values
  - FR_SAMPLING_SIZE
```
private static final int FR_SAMPLING_SIZE
```
    Threshold to use Floyd-Rivest sub-sampling. This partitions a sample of the data to identify a pivot so that the target element is in the smaller set after partitioning. The original FR paper used 600 otherwise reverted to the target index as the pivot. This implementation reverts to quickselect adaptive which increases robustness at small size on a variety of data and allows raising the original FR threshold.
    
    See Also:
    
    Constant Field Values
  - RECURSION_INCREMENT
```
private static final int RECURSION_INCREMENT
```
    Increment used for the recursion counter. The counter will overflow to negative when recursion has exceeded the maximum level. The counter is maintained in the upper bits of the dual-pivot control flags.
    
    See Also:
    
    Constant Field Values
  - SORTSELECT_MASK
```
private static final int SORTSELECT_MASK
```
    Mask to extract the sort select size from the dual-pivot control flags. Currently the bits below those used for the recursion counter are only used for the sort select size so this can use a mask with all bits below the increment.
    
    See Also:
    
    Constant Field Values
  - STEP_LEFT
```
private static final double STEP_LEFT
```
    Threshold to use repeated step left: 7 / 16.
    
    See Also:
    
    Constant Field Values
  - STEP_RIGHT
```
private static final double STEP_RIGHT
```
    Threshold to use repeated step right: 9 / 16.
    
    See Also:
    
    Constant Field Values
  - STEP_FAR_LEFT
```
private static final double STEP_FAR_LEFT
```
    Threshold to use repeated step far-left: 1 / 12.
    
    See Also:
    
    Constant Field Values
  - STEP_FAR_RIGHT
```
private static final double STEP_FAR_RIGHT
```
    Threshold to use repeated step far-right: 11 / 12.
    
    See Also:
    
    Constant Field Values
- Constructor Detail
  - QuickSelect
```
private QuickSelect()
```
    No instances.
- Method Detail
  - heapSelect
```
static void heapSelect(double[] a,
                       int left,
                       int right,
                       int ka,
                       int kb)
```
    Partition the elements between ka and kb using a heap select algorithm. It is assumed left <= ka <= kb <= right.
    
    Parameters:
    
    a - Data array to use to find out the K^th value.
    
    left - Lower bound (inclusive).
    
    right - Upper bound (inclusive).
    
    ka - Lower index to select.
    
    kb - Upper index to select.
  - heapSelectLeft
```
static void heapSelectLeft(double[] a,
                           int left,
                           int right,
                           int ka,
                           int kb)
```
    Partition the elements between ka and kb using a heap select algorithm. It is assumed left <= ka <= kb <= right.
    For best performance this should be called with k in the lower half of the range.
    
    Parameters:
    
    a - Data array to use to find out the K^th value.
    
    left - Lower bound (inclusive).
    
    right - Upper bound (inclusive).
    
    ka - Lower index to select.
    
    kb - Upper index to select.
  - maxHeapSiftDown
```
private static void maxHeapSiftDown(double[] a,
                                    double v,
                                    int p,
                                    int root,
                                    int end)
```
    Sift the element down the max heap.
    Assumes root <= p < end, i.e. the max heap is above root.
    
    Parameters:
    
    a - Heap data.
    
    v - Value to sift.
    
    p - Start position.
    
    root - Root of the heap.
    
    end - End of the heap (exclusive).
  - heapSelectRight
```
static void heapSelectRight(double[] a,
                            int left,
                            int right,
                            int ka,
                            int kb)
```
    Partition the elements between ka and kb using a heap select algorithm. It is assumed left <= ka <= kb <= right.
    For best performance this should be called with k in the upper half of the range.
    
    Parameters:
    
    a - Data array to use to find out the K^th value.
    
    left - Lower bound (inclusive).
    
    right - Upper bound (inclusive).
    
    ka - Lower index to select.
    
    kb - Upper index to select.
  - minHeapSiftDown
```
private static void minHeapSiftDown(double[] a,
                                    double v,
                                    int p,
                                    int root,
                                    int end)
```
    Sift the element down the min heap.
    Assumes root >= p > end, i.e. the max heap is below root.
    
    Parameters:
    
    a - Heap data.
    
    v - Value to sift.
    
    p - Start position.
    
    root - Root of the heap.
    
    end - End of the heap (exclusive).
  - sortSelect
```
static void sortSelect(double[] a,
                       int left,
                       int right,
                       int ka,
                       int kb)
```
    Partition the elements between ka and kb using a sort select algorithm. It is assumed left <= ka <= kb <= right.
    
    Parameters:
    
    a - Data array to use to find out the K^th value.
    
    left - Lower bound (inclusive).
    
    right - Upper bound (inclusive).
    
    ka - Lower index to select.
    
    kb - Upper index to select.
  - sortSelectLeft
```
static void sortSelectLeft(double[] a,
                           int left,
                           int right,
                           int k)
```
    Partition the minimum n elements below k where n = k - left + 1. Uses an insertion sort algorithm.
    Works with any k in the range left <= k <= right and performs a full sort of the range below k.
    For best performance this should be called with k - left < right - k, i.e. to partition a value in the lower half of the range.
    
    Parameters:
    
    a - Data array to use to find out the K^th value.
    
    left - Lower bound (inclusive).
    
    right - Upper bound (inclusive).
    
    k - Index to select.
  - sortSelectRight
```
static void sortSelectRight(double[] a,
                            int left,
                            int right,
                            int k)
```
    Partition the maximum n elements above k where n = right - k + 1. Uses an insertion sort algorithm.
    Works with any k in the range left <= k <= right and can be used to perform a full sort of the range above k.
    For best performance this should be called with k - left > right - k, i.e. to partition a value in the upper half of the range.
    
    Parameters:
    
    a - Data array to use to find out the K^th value.
    
    left - Lower bound (inclusive).
    
    right - Upper bound (inclusive).
    
    k - Index to select.
  - select
```
static void select(double[] a,
                   int left,
                   int right,
                   int k)
```
    Partition the array such that index k corresponds to its correctly sorted value in the equivalent fully sorted array.
    Assumes k is a valid index into [left, right].
    
    Parameters:
    
    a - Values.
    
    left - Lower bound of data (inclusive).
    
    right - Upper bound of data (inclusive).
    
    k - Index.
  - select
```
static int select(double[] a,
                  int left,
                  int right,
                  int[] k,
                  int n)
```
    Partition the array such that indices k correspond to their correctly sorted value in the equivalent fully sorted array.
    The count of the number of used indices is returned. If the keys are sorted in-place, the count is returned as a negative.
    
    Parameters:
    
    a - Values.
    
    left - Lower bound of data (inclusive).
    
    right - Upper bound of data (inclusive).
    
    k - Indices (may be destructively modified).
    
    n - Count of indices.
    
    Returns:
    
    the count of used indices
    
    Throws:
    
    java.lang.IndexOutOfBoundsException - if any index k is not within the sub-range [left, right]
  - quickSelectAdaptive
```
static int quickSelectAdaptive(double[] a,
                               int left,
                               int right,
                               int ka,
                               int kb,
                               int[] bounds,
                               int flags)
```
    Partition the array such that indices k correspond to their correctly sorted value in the equivalent fully sorted array.
    For all indices [ka, kb] and any index i:
    data[i < ka] <= data[ka] <= data[kb] <= data[kb < i]
    
    This function accepts indices [ka, kb] that define the range of indices to partition. It is expected that the range is small.
    The flags are used to control the sampling mode and adaption of the index within the sample.
    Returns the bounds containing [ka, kb]. These may be lower/higher than the keys if equal values are present in the data.
    Parameters:
    
    a - Values.
    
    left - Lower bound of data (inclusive, assumed to be strictly positive).
    
    right - Upper bound of data (inclusive, assumed to be strictly positive).
    
    ka - First key of interest.
    
    kb - Last key of interest.
    
    bounds - Upper bound of the range containing [ka, kb] (inclusive).
    
    flags - Adaption flags.
    
    Returns:
    
    Lower bound of the range containing [ka, kb] (inclusive).
  - sampleStep
```
private static int sampleStep(double[] a,
                              int l,
                              int r,
                              int k,
                              int[] upper)
```
    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.
    Partitions a Floyd-Rivest sample around a pivot offset so that the input k will fall in the smaller partition when the entire range is partitioned.
    Assumes the range r - l is large.
    
    Parameters:
    
    a - Data array.
    
    l - Lower bound (inclusive).
    
    r - Upper bound (inclusive).
    
    k - Target index.
    
    upper - Upper bound (inclusive) of the pivot range.
    
    Returns:
    
    Lower bound (inclusive) of the pivot range.
  - repeatedStep
```
private static int repeatedStep(double[] a,
                                int l,
                                int r,
                                int k,
                                int[] upper,
                                int flags)
```
    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.
    Assumes the range r - l >= 8; the caller is responsible for selection on a smaller range. If using a 12th-tile for sampling then assumes r - l >= 11.
    Uses the Chen and Dumitrescu repeated step median-of-medians-of-medians algorithm with the median of 3 then median of 3; the final sample is placed in the 5th 9th-tile; the pivot chosen from the sample is adaptive using the input k.
    Given a pivot in the middle of the sample this has margins of 2/9 and 2/9.
    
    Parameters:
    
    a - Data array.
    
    l - Lower bound (inclusive).
    
    r - Upper bound (inclusive).
    
    k - Target index.
    
    upper - Upper bound (inclusive) of the pivot range.
    
    flags - Control flags.
    
    Returns:
    
    Lower bound (inclusive) of the pivot range.
  - repeatedStepLeft
```
private static int repeatedStepLeft(double[] a,
                                    int l,
                                    int r,
                                    int k,
                                    int[] upper,
                                    int flags)
```
    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.
    Assumes the range r - l >= 11; the caller is responsible for selection on a smaller range.
    Uses the Chen and Dumitrescu repeated step median-of-medians-of-medians algorithm with the lower median of 4 then either median of 3 with the final sample placed in the 5th 12th-tile, or min of 3 with the final sample in the 4th 12th-tile; the pivot chosen from the sample is adaptive using the input k.
    Given a pivot in the middle of the sample this has margins of 1/6 and 1/4.
    
    Parameters:
    
    a - Data array.
    
    l - Lower bound (inclusive).
    
    r - Upper bound (inclusive).
    
    k - Target index.
    
    upper - Upper bound (inclusive) of the pivot range.
    
    flags - Control flags.
    
    Returns:
    
    Lower bound (inclusive) of the pivot range.
  - repeatedStepRight
```
private static int repeatedStepRight(double[] a,
                                     int l,
                                     int r,
                                     int k,
                                     int[] upper,
                                     int flags)
```
    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.
    Assumes the range r - l >= 11; the caller is responsible for selection on a smaller range.
    Uses the Chen and Dumitrescu repeated step median-of-medians-of-medians algorithm with the upper median of 4 then either median of 3 with the final sample placed in the 8th 12th-tile, or max of 3 with the final sample in the 9th 12th-tile; the pivot chosen from the sample is adaptive using the input k.
    Given a pivot in the middle of the sample this has margins of 1/4 and 1/6.
    
    Parameters:
    
    a - Data array.
    
    l - Lower bound (inclusive).
    
    r - Upper bound (inclusive).
    
    k - Target index.
    
    upper - Upper bound (inclusive) of the pivot range.
    
    flags - Control flags.
    
    Returns:
    
    Lower bound (inclusive) of the pivot range.
  - repeatedStepFarLeft
```
private static int repeatedStepFarLeft(double[] a,
                                       int l,
                                       int r,
                                       int k,
                                       int[] upper,
                                       int flags)
```
    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.
    Assumes the range r - l >= 11; the caller is responsible for selection on a smaller range.
    Uses the Chen and Dumitrescu repeated step median-of-medians-of-medians algorithm with the minimum of 4 then median of 3; the final sample is placed in the 2nd 12th-tile; the pivot chosen from the sample is adaptive using the input k.
    Given a pivot in the middle of the sample this has margins of 1/12 and 1/3.
    
    Parameters:
    
    a - Data array.
    
    l - Lower bound (inclusive).
    
    r - Upper bound (inclusive).
    
    k - Target index.
    
    upper - Upper bound (inclusive) of the pivot range.
    
    flags - Control flags.
    
    Returns:
    
    Lower bound (inclusive) of the pivot range.
  - repeatedStepFarRight
```
private static int repeatedStepFarRight(double[] a,
                                        int l,
                                        int r,
                                        int k,
                                        int[] upper,
                                        int flags)
```
    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.
    Assumes the range r - l >= 11; the caller is responsible for selection on a smaller range.
    Uses the Chen and Dumitrescu repeated step median-of-medians-of-medians algorithm with the maximum of 4 then median of 3; the final sample is placed in the 11th 12th-tile; the pivot chosen from the sample is adaptive using the input k.
    Given a pivot in the middle of the sample this has margins of 1/3 and 1/12.
    
    Parameters:
    
    a - Data array.
    
    l - Lower bound (inclusive).
    
    r - Upper bound (inclusive).
    
    k - Target index.
    
    upper - Upper bound (inclusive) of the pivot range.
    
    flags - Control flags.
    
    Returns:
    
    Lower bound (inclusive) of the pivot range.
  - expandPartition
```
static int expandPartition(double[] a,
                           int left,
                           int right,
                           int start,
                           int end,
                           int pivot0,
                           int pivot1,
                           int[] upper)
```
    Expand a partition around a single pivot. Partitioning exchanges array elements such that all elements smaller than pivot are before it and all elements larger than pivot are after it. The central region is already partitioned.
    |l |s |p0 p1| e| r| | ??? | <P | ==P | >P | ??? |
    
    This requires that start != end. However it handles left == start and/or end == right.
    Parameters:
    
    a - Data array.
    
    left - Lower bound (inclusive).
    
    right - Upper bound (inclusive).
    
    start - Start of the partition range (inclusive).
    
    end - End of the partitioned range (inclusive).
    
    pivot0 - Lower pivot location (inclusive).
    
    pivot1 - Upper pivot location (inclusive).
    
    upper - Upper bound (inclusive) of the pivot range [k1].
    
    Returns:
    
    Lower bound (inclusive) of the pivot range [k0].
  - dualPivotQuickSelect
```
static void dualPivotQuickSelect(double[] a,
                                 int left,
                                 int right,
                                 UpdatingInterval k,
                                 int flags)
```
    Partition the array 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]
    
    This function accepts a UpdatingInterval of indices k that define the range of indices to partition. The UpdatingInterval can be narrowed or split as partitioning divides the range.
    Uses an introselect variant. The quickselect is a dual-pivot quicksort partition method by Vladimir Yaroslavskiy; the fall-back on poor convergence of the quickselect is a heapselect.
    The flags contain the the current recursion count and the configured length threshold for r - l to perform sort select. The count is in the upper bits and the threshold is in the lower bits.
    Parameters:
    
    a - Values.
    
    left - Lower bound of data (inclusive, assumed to be strictly positive).
    
    right - Upper bound of data (inclusive, assumed to be strictly positive).
    
    k - Interval of indices to partition (ordered).
    
    flags - Control flags.
  - partition
```
private static int partition(double[] a,
                             int left,
                             int right,
                             int[] bounds)
```
    Partition an array slice around 2 pivots. Partitioning exchanges array elements such that all elements smaller than pivot are before it and all elements larger than pivot are after it.
    This method returns 4 points describing the pivot ranges of equal values.
    |k0 k1| |k2 k3| | <P | ==P1 | <P1 && <P2 | ==P2 | >P |
    
    k0: lower pivot1 point
    k1: upper pivot1 point (inclusive)
    k2: lower pivot2 point
    k3: upper pivot2 point (inclusive)
    
    Bounds are set so i < k0, i > k3 and k1 < i < k2 are unsorted. When the range [k0, k3] contains fully sorted elements the result is set to k1 = k3; k2 == k0. This can occur if P1 == P2 or there are zero or one value between the pivots P1 < v < P2. Any sort/partition of ranges [left, k0-1], [k1+1, k2-1] and [k3+1, right] must check the length is > 1.
    Parameters:
    
    a - Data array.
    
    left - Lower bound (inclusive).
    
    right - Upper bound (inclusive).
    
    bounds - Points [k1, k2, k3].
    
    Returns:
    
    Lower bound (inclusive) of the pivot range [k0].
  - heapSelect
```
static void heapSelect(int[] a,
                       int left,
                       int right,
                       int ka,
                       int kb)
```
    Partition the elements between ka and kb using a heap select algorithm. It is assumed left <= ka <= kb <= right.
    
    Parameters:
    
    a - Data array to use to find out the K^th value.
    
    left - Lower bound (inclusive).
    
    right - Upper bound (inclusive).
    
    ka - Lower index to select.
    
    kb - Upper index to select.
  - heapSelectLeft
```
static void heapSelectLeft(int[] a,
                           int left,
                           int right,
                           int ka,
                           int kb)
```
    Partition the elements between ka and kb using a heap select algorithm. It is assumed left <= ka <= kb <= right.
    For best performance this should be called with k in the lower half of the range.
    
    Parameters:
    
    a - Data array to use to find out the K^th value.
    
    left - Lower bound (inclusive).
    
    right - Upper bound (inclusive).
    
    ka - Lower index to select.
    
    kb - Upper index to select.
  - maxHeapSiftDown
```
private static void maxHeapSiftDown(int[] a,
                                    int v,
                                    int p,
                                    int root,
                                    int end)
```
    Sift the element down the max heap.
    Assumes root <= p < end, i.e. the max heap is above root.
    
    Parameters:
    
    a - Heap data.
    
    v - Value to sift.
    
    p - Start position.
    
    root - Root of the heap.
    
    end - End of the heap (exclusive).
  - heapSelectRight
```
static void heapSelectRight(int[] a,
                            int left,
                            int right,
                            int ka,
                            int kb)
```
    Partition the elements between ka and kb using a heap select algorithm. It is assumed left <= ka <= kb <= right.
    For best performance this should be called with k in the upper half of the range.
    
    Parameters:
    
    a - Data array to use to find out the K^th value.
    
    left - Lower bound (inclusive).
    
    right - Upper bound (inclusive).
    
    ka - Lower index to select.
    
    kb - Upper index to select.
  - minHeapSiftDown
```
private static void minHeapSiftDown(int[] a,
                                    int v,
                                    int p,
                                    int root,
                                    int end)
```
    Sift the element down the min heap.
    Assumes root >= p > end, i.e. the max heap is below root.
    
    Parameters:
    
    a - Heap data.
    
    v - Value to sift.
    
    p - Start position.
    
    root - Root of the heap.
    
    end - End of the heap (exclusive).
  - sortSelect
```
static void sortSelect(int[] a,
                       int left,
                       int right,
                       int ka,
                       int kb)
```
    Partition the elements between ka and kb using a sort select algorithm. It is assumed left <= ka <= kb <= right.
    
    Parameters:
    
    a - Data array to use to find out the K^th value.
    
    left - Lower bound (inclusive).
    
    right - Upper bound (inclusive).
    
    ka - Lower index to select.
    
    kb - Upper index to select.
  - sortSelectLeft
```
static void sortSelectLeft(int[] a,
                           int left,
                           int right,
                           int k)
```
    Partition the minimum n elements below k where n = k - left + 1. Uses an insertion sort algorithm.
    Works with any k in the range left <= k <= right and performs a full sort of the range below k.
    For best performance this should be called with k - left < right - k, i.e. to partition a value in the lower half of the range.
    
    Parameters:
    
    a - Data array to use to find out the K^th value.
    
    left - Lower bound (inclusive).
    
    right - Upper bound (inclusive).
    
    k - Index to select.
  - sortSelectRight
```
static void sortSelectRight(int[] a,
                            int left,
                            int right,
                            int k)
```
    Partition the maximum n elements above k where n = right - k + 1. Uses an insertion sort algorithm.
    Works with any k in the range left <= k <= right and can be used to perform a full sort of the range above k.
    For best performance this should be called with k - left > right - k, i.e. to partition a value in the upper half of the range.
    
    Parameters:
    
    a - Data array to use to find out the K^th value.
    
    left - Lower bound (inclusive).
    
    right - Upper bound (inclusive).
    
    k - Index to select.
  - select
```
static void select(int[] a,
                   int left,
                   int right,
                   int k)
```
    Partition the array such that index k corresponds to its correctly sorted value in the equivalent fully sorted array.
    Assumes k is a valid index into [left, right].
    
    Parameters:
    
    a - Values.
    
    left - Lower bound of data (inclusive).
    
    right - Upper bound of data (inclusive).
    
    k - Index.
  - select
```
static void select(int[] a,
                   int left,
                   int right,
                   int[] k,
                   int n)
```
    Partition the array such that indices k correspond to their correctly sorted value in the equivalent fully sorted array.
    The count of the number of used indices is returned. If the keys are sorted in-place, the count is returned as a negative.
    
    Parameters:
    
    a - Values.
    
    left - Lower bound of data (inclusive).
    
    right - Upper bound of data (inclusive).
    
    k - Indices (may be destructively modified).
    
    n - Count of indices.
    
    Throws:
    
    java.lang.IndexOutOfBoundsException - if any index k is not within the sub-range [left, right]
  - quickSelectAdaptive
```
static int quickSelectAdaptive(int[] a,
                               int left,
                               int right,
                               int ka,
                               int kb,
                               int[] bounds,
                               int flags)
```
    Partition the array such that indices k correspond to their correctly sorted value in the equivalent fully sorted array.
    For all indices [ka, kb] and any index i:
    data[i < ka] <= data[ka] <= data[kb] <= data[kb < i]
    
    This function accepts indices [ka, kb] that define the range of indices to partition. It is expected that the range is small.
    The flags are used to control the sampling mode and adaption of the index within the sample.
    Returns the bounds containing [ka, kb]. These may be lower/higher than the keys if equal values are present in the data.
    Parameters:
    
    a - Values.
    
    left - Lower bound of data (inclusive, assumed to be strictly positive).
    
    right - Upper bound of data (inclusive, assumed to be strictly positive).
    
    ka - First key of interest.
    
    kb - Last key of interest.
    
    bounds - Upper bound of the range containing [ka, kb] (inclusive).
    
    flags - Adaption flags.
    
    Returns:
    
    Lower bound of the range containing [ka, kb] (inclusive).
  - sampleStep
```
private static int sampleStep(int[] a,
                              int l,
                              int r,
                              int k,
                              int[] upper)
```
    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.
    Partitions a Floyd-Rivest sample around a pivot offset so that the input k will fall in the smaller partition when the entire range is partitioned.
    Assumes the range r - l is large.
    
    Parameters:
    
    a - Data array.
    
    l - Lower bound (inclusive).
    
    r - Upper bound (inclusive).
    
    k - Target index.
    
    upper - Upper bound (inclusive) of the pivot range.
    
    Returns:
    
    Lower bound (inclusive) of the pivot range.
  - repeatedStep
```
private static int repeatedStep(int[] a,
                                int l,
                                int r,
                                int k,
                                int[] upper,
                                int flags)
```
    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.
    Assumes the range r - l >= 8; the caller is responsible for selection on a smaller range. If using a 12th-tile for sampling then assumes r - l >= 11.
    Uses the Chen and Dumitrescu repeated step median-of-medians-of-medians algorithm with the median of 3 then median of 3; the final sample is placed in the 5th 9th-tile; the pivot chosen from the sample is adaptive using the input k.
    Given a pivot in the middle of the sample this has margins of 2/9 and 2/9.
    
    Parameters:
    
    a - Data array.
    
    l - Lower bound (inclusive).
    
    r - Upper bound (inclusive).
    
    k - Target index.
    
    upper - Upper bound (inclusive) of the pivot range.
    
    flags - Control flags.
    
    Returns:
    
    Lower bound (inclusive) of the pivot range.
  - repeatedStepLeft
```
private static int repeatedStepLeft(int[] a,
                                    int l,
                                    int r,
                                    int k,
                                    int[] upper,
                                    int flags)
```
    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.
    Assumes the range r - l >= 11; the caller is responsible for selection on a smaller range.
    Uses the Chen and Dumitrescu repeated step median-of-medians-of-medians algorithm with the lower median of 4 then either median of 3 with the final sample placed in the 5th 12th-tile, or min of 3 with the final sample in the 4th 12th-tile; the pivot chosen from the sample is adaptive using the input k.
    Given a pivot in the middle of the sample this has margins of 1/6 and 1/4.
    
    Parameters:
    
    a - Data array.
    
    l - Lower bound (inclusive).
    
    r - Upper bound (inclusive).
    
    k - Target index.
    
    upper - Upper bound (inclusive) of the pivot range.
    
    flags - Control flags.
    
    Returns:
    
    Lower bound (inclusive) of the pivot range.
  - repeatedStepRight
```
private static int repeatedStepRight(int[] a,
                                     int l,
                                     int r,
                                     int k,
                                     int[] upper,
                                     int flags)
```
    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.
    Assumes the range r - l >= 11; the caller is responsible for selection on a smaller range.
    Uses the Chen and Dumitrescu repeated step median-of-medians-of-medians algorithm with the upper median of 4 then either median of 3 with the final sample placed in the 8th 12th-tile, or max of 3 with the final sample in the 9th 12th-tile; the pivot chosen from the sample is adaptive using the input k.
    Given a pivot in the middle of the sample this has margins of 1/4 and 1/6.
    
    Parameters:
    
    a - Data array.
    
    l - Lower bound (inclusive).
    
    r - Upper bound (inclusive).
    
    k - Target index.
    
    upper - Upper bound (inclusive) of the pivot range.
    
    flags - Control flags.
    
    Returns:
    
    Lower bound (inclusive) of the pivot range.
  - repeatedStepFarLeft
```
private static int repeatedStepFarLeft(int[] a,
                                       int l,
                                       int r,
                                       int k,
                                       int[] upper,
                                       int flags)
```
    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.
    Assumes the range r - l >= 11; the caller is responsible for selection on a smaller range.
    Uses the Chen and Dumitrescu repeated step median-of-medians-of-medians algorithm with the minimum of 4 then median of 3; the final sample is placed in the 2nd 12th-tile; the pivot chosen from the sample is adaptive using the input k.
    Given a pivot in the middle of the sample this has margins of 1/12 and 1/3.
    
    Parameters:
    
    a - Data array.
    
    l - Lower bound (inclusive).
    
    r - Upper bound (inclusive).
    
    k - Target index.
    
    upper - Upper bound (inclusive) of the pivot range.
    
    flags - Control flags.
    
    Returns:
    
    Lower bound (inclusive) of the pivot range.
  - repeatedStepFarRight
```
private static int repeatedStepFarRight(int[] a,
                                        int l,
                                        int r,
                                        int k,
                                        int[] upper,
                                        int flags)
```
    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.
    Assumes the range r - l >= 11; the caller is responsible for selection on a smaller range.
    Uses the Chen and Dumitrescu repeated step median-of-medians-of-medians algorithm with the maximum of 4 then median of 3; the final sample is placed in the 11th 12th-tile; the pivot chosen from the sample is adaptive using the input k.
    Given a pivot in the middle of the sample this has margins of 1/3 and 1/12.
    
    Parameters:
    
    a - Data array.
    
    l - Lower bound (inclusive).
    
    r - Upper bound (inclusive).
    
    k - Target index.
    
    upper - Upper bound (inclusive) of the pivot range.
    
    flags - Control flags.
    
    Returns:
    
    Lower bound (inclusive) of the pivot range.
  - expandPartition
```
static int expandPartition(int[] a,
                           int left,
                           int right,
                           int start,
                           int end,
                           int pivot0,
                           int pivot1,
                           int[] upper)
```
    Expand a partition around a single pivot. Partitioning exchanges array elements such that all elements smaller than pivot are before it and all elements larger than pivot are after it. The central region is already partitioned.
    |l |s |p0 p1| e| r| | ??? | <P | ==P | >P | ??? |
    
    This requires that start != end. However it handles left == start and/or end == right.
    Parameters:
    
    a - Data array.
    
    left - Lower bound (inclusive).
    
    right - Upper bound (inclusive).
    
    start - Start of the partition range (inclusive).
    
    end - End of the partitioned range (inclusive).
    
    pivot0 - Lower pivot location (inclusive).
    
    pivot1 - Upper pivot location (inclusive).
    
    upper - Upper bound (inclusive) of the pivot range [k1].
    
    Returns:
    
    Lower bound (inclusive) of the pivot range [k0].
  - dualPivotQuickSelect
```
static void dualPivotQuickSelect(int[] a,
                                 int left,
                                 int right,
                                 UpdatingInterval k,
                                 int flags)
```
    Partition the array 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]
    
    This function accepts a UpdatingInterval of indices k that define the range of indices to partition. The UpdatingInterval can be narrowed or split as partitioning divides the range.
    Uses an introselect variant. The quickselect is a dual-pivot quicksort partition method by Vladimir Yaroslavskiy; the fall-back on poor convergence of the quickselect is a heapselect.
    The flags contain the the current recursion count and the configured length threshold for r - l to perform sort select. The count is in the upper bits and the threshold is in the lower bits.
    Parameters:
    
    a - Values.
    
    left - Lower bound of data (inclusive, assumed to be strictly positive).
    
    right - Upper bound of data (inclusive, assumed to be strictly positive).
    
    k - Interval of indices to partition (ordered).
    
    flags - Control flags.
  - partition
```
private static int partition(int[] a,
                             int left,
                             int right,
                             int[] bounds)
```
    Partition an array slice around 2 pivots. Partitioning exchanges array elements such that all elements smaller than pivot are before it and all elements larger than pivot are after it.
    This method returns 4 points describing the pivot ranges of equal values.
    |k0 k1| |k2 k3| | <P | ==P1 | <P1 && <P2 | ==P2 | >P |
    
    k0: lower pivot1 point
    k1: upper pivot1 point (inclusive)
    k2: lower pivot2 point
    k3: upper pivot2 point (inclusive)
    
    Bounds are set so i < k0, i > k3 and k1 < i < k2 are unsorted. When the range [k0, k3] contains fully sorted elements the result is set to k1 = k3; k2 == k0. This can occur if P1 == P2 or there are zero or one value between the pivots P1 < v < P2. Any sort/partition of ranges [left, k0-1], [k1+1, k2-1] and [k3+1, right] must check the length is > 1.
    Parameters:
    
    a - Data array.
    
    left - Lower bound (inclusive).
    
    right - Upper bound (inclusive).
    
    bounds - Points [k1, k2, k3].
    
    Returns:
    
    Lower bound (inclusive) of the pivot range [k0].
  - mapDistance
```
private static int mapDistance(int d,
                               int l,
                               int r,
                               int n)
```
    Map the distance from the edge of [l, r] to a new distance in [0, n).
    The provides the adaption kf'/|A| from Alexandrescu (2016) where k == d, f' == n and |A| == r-l+1.
    For convenience this accepts the input range [l, r].
    
    Parameters:
    
    d - Distance from the edge in [0, r - l].
    
    l - Lower bound (inclusive).
    
    r - Upper bound (inclusive).
    
    n - Size of the new range.
    
    Returns:
    
    the mapped distance in [0, n)
  - dualPivotFlags
```
private static int dualPivotFlags(int left,
                                  int right,
                                  int k1,
                                  int kn)
```
    Configure the dual-pivot control flags. This packs the maximum recursion depth and sort select size into a single integer.
    
    Parameters:
    
    left - Lower bound (inclusive).
    
    right - Upper bound (inclusive).
    
    k1 - First key of interest.
    
    kn - Last key of interest.
    
    Returns:
    
    the flags
  - dualPivotFlags
```
static int dualPivotFlags(int maxDepth,
                          int ss)
```
    Configure the dual-pivot control flags. This packs the maximum recursion depth and sort select size into a single integer.
    
    Parameters:
    
    maxDepth - Maximum recursion depth.
    
    ss - Sort select size.
    
    Returns:
    
    the flags
  - dualPivotMaxDepth
```
static int dualPivotMaxDepth(int x)
```
    Compute the maximum recursion depth for dual pivot recursion. This is an approximation to 2 * log3 (x).
    The result is between 2*floor(log3(x)) and 2*ceil(log3(x)). The result is correctly rounded when x +/- 1 is a power of 3.
    
    Parameters:
    
    x - Value.
    
    Returns:
    
    maximum recursion depth
  - dualPivotSortSelectSize
```
private static int dualPivotSortSelectSize(int k1,
                                           int kn)
```
    Configure the sort select size for dual pivot partitioning.
    
    Parameters:
    
    k1 - First key of interest.
    
    kn - Last key of interest.
    
    Returns:
    
    the sort select size.

Class QuickSelect

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

MODE_FR_SAMPLING

MODE_SAMPLING

MODE_ADAPTION

MODE_STRICT

MIN_SORTSELECT_SIZE

LINEAR_SORTSELECT_SIZE

DP_SORTSELECT_SIZE

FR_SAMPLING_SIZE

RECURSION_INCREMENT

SORTSELECT_MASK

STEP_LEFT

STEP_RIGHT

STEP_FAR_LEFT

STEP_FAR_RIGHT

Constructor Detail

QuickSelect

Method Detail

heapSelect

heapSelectLeft

maxHeapSiftDown

heapSelectRight

minHeapSiftDown

sortSelect

sortSelectLeft

sortSelectRight

select

select

quickSelectAdaptive

sampleStep

repeatedStep

repeatedStepLeft

repeatedStepRight

repeatedStepFarLeft

repeatedStepFarRight

expandPartition

dualPivotQuickSelect

partition

heapSelect

heapSelectLeft

maxHeapSiftDown

heapSelectRight

minHeapSiftDown

sortSelect

sortSelectLeft

sortSelectRight

select

select

quickSelectAdaptive

sampleStep

repeatedStep

repeatedStepLeft

repeatedStepRight

repeatedStepFarLeft

repeatedStepFarRight

expandPartition

dualPivotQuickSelect

partition

mapDistance

dualPivotFlags

dualPivotFlags

dualPivotMaxDepth

dualPivotSortSelectSize