Class 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_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 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:
        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 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:
        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.