Class QuickSelect

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

final class QuickSelect extends 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:
  • Field Summary

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

    Constructors
    Modifier
    Constructor
    Description
    private
    No instances.
  • Method Summary

    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
    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 Details

    • MODE_FR_SAMPLING

      static final int MODE_FR_SAMPLING
      Sampling mode using Floyd-Rivest sampling.
      See Also:
    • MODE_SAMPLING

      static final int MODE_SAMPLING
      Sampling mode.
      See Also:
    • MODE_ADAPTION

      static final int MODE_ADAPTION
      No sampling but use adaption of the target k.
      See Also:
    • MODE_STRICT

      static final int MODE_STRICT
      No sampling and no adaption of target k (strict margins).
      See Also:
    • 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:
    • 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:
    • 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:
    • 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:
    • 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:
    • 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:
    • STEP_LEFT

      private static final double STEP_LEFT
      Threshold to use repeated step left: 7 / 16.
      See Also:
    • STEP_RIGHT

      private static final double STEP_RIGHT
      Threshold to use repeated step right: 9 / 16.
      See Also:
    • STEP_FAR_LEFT

      private static final double STEP_FAR_LEFT
      Threshold to use repeated step far-left: 1 / 12.
      See Also:
    • STEP_FAR_RIGHT

      private static final double STEP_FAR_RIGHT
      Threshold to use repeated step far-right: 11 / 12.
      See Also:
  • Constructor Details

    • QuickSelect

      private QuickSelect()
      No instances.
  • Method Details

    • 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 Kth 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 Kth 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 Kth 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 Kth 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 Kth 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 Kth 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:
      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 Kth 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 Kth 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 Kth 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 Kth 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 Kth 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 Kth 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:
      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.