Class QuickSelect
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
FieldsModifier and TypeFieldDescriptionprivate 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 -
Method Summary
Modifier and TypeMethodDescription(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 indicesk
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 indicesk
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 betweenka
andkb
using a heap select algorithm.(package private) static void
heapSelect
(int[] a, int left, int right, int ka, int kb) Partition the elements betweenka
andkb
using a heap select algorithm.(package private) static void
heapSelectLeft
(double[] a, int left, int right, int ka, int kb) Partition the elements betweenka
andkb
using a heap select algorithm.(package private) static void
heapSelectLeft
(int[] a, int left, int right, int ka, int kb) Partition the elements betweenka
andkb
using a heap select algorithm.(package private) static void
heapSelectRight
(double[] a, int left, int right, int ka, int kb) Partition the elements betweenka
andkb
using a heap select algorithm.(package private) static void
heapSelectRight
(int[] a, int left, int right, int ka, int kb) Partition the elements betweenka
andkb
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 indicesk
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 indicesk
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 indexk
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 indicesk
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 indexk
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 indicesk
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 betweenka
andkb
using a sort select algorithm.(package private) static void
sortSelect
(int[] a, int left, int right, int ka, int kb) Partition the elements betweenka
andkb
using a sort select algorithm.(package private) static void
sortSelectLeft
(double[] a, int left, int right, int k) Partition the minimumn
elements belowk
wheren = k - left + 1
.(package private) static void
sortSelectLeft
(int[] a, int left, int right, int k) Partition the minimumn
elements belowk
wheren = k - left + 1
.(package private) static void
sortSelectRight
(double[] a, int left, int right, int k) Partition the maximumn
elements abovek
wheren = right - k + 1
.(package private) static void
sortSelectRight
(int[] a, int left, int right, int k) Partition the maximumn
elements abovek
wheren = right - k + 1
.
-
Field Details
-
MODE_FR_SAMPLING
static final int MODE_FR_SAMPLINGSampling mode using Floyd-Rivest sampling.- See Also:
-
MODE_SAMPLING
static final int MODE_SAMPLINGSampling mode.- See Also:
-
MODE_ADAPTION
static final int MODE_ADAPTIONNo sampling but use adaption of the target k.- See Also:
-
MODE_STRICT
static final int MODE_STRICTNo sampling and no adaption of target k (strict margins).- See Also:
-
MIN_SORTSELECT_SIZE
private static final int MIN_SORTSELECT_SIZEMinimum 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_SIZESingle-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_SIZEDual-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_SIZEThreshold 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_INCREMENTIncrement 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_MASKMask 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_LEFTThreshold to use repeated step left: 7 / 16.- See Also:
-
STEP_RIGHT
private static final double STEP_RIGHTThreshold to use repeated step right: 9 / 16.- See Also:
-
STEP_FAR_LEFT
private static final double STEP_FAR_LEFTThreshold to use repeated step far-left: 1 / 12.- See Also:
-
STEP_FAR_RIGHT
private static final double STEP_FAR_RIGHTThreshold 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 betweenka
andkb
using a heap select algorithm. It is assumedleft <= 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 betweenka
andkb
using a heap select algorithm. It is assumedleft <= 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 betweenka
andkb
using a heap select algorithm. It is assumedleft <= 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 betweenka
andkb
using a sort select algorithm. It is assumedleft <= 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 minimumn
elements belowk
wheren = k - left + 1
. Uses an insertion sort algorithm.Works with any
k
in the rangeleft <= k <= right
and performs a full sort of the range belowk
.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 maximumn
elements abovek
wheren = right - k + 1
. Uses an insertion sort algorithm.Works with any
k
in the rangeleft <= k <= right
and can be used to perform a full sort of the range abovek
.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 indexk
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 indicesk
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 indexk
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 indicesk
correspond to their correctly sorted value in the equivalent fully sorted array.For all indices
[ka, kb]
and any indexi
: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 assumesr - 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 handlesleft == start
and/orend == 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
Partition the array such that indicesk
correspond to their correctly sorted value in the equivalent fully sorted array.For all indices
k
and any indexi
:data[i < k] <= data[k] <= data[k < i]
This function accepts a
UpdatingInterval
of indicesk
that define the range of indices to partition. TheUpdatingInterval
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 forr - 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
andk1 < i < k2
are unsorted. When the range[k0, k3]
contains fully sorted elements the result is set tok1 = k3; k2 == k0
. This can occur ifP1 == P2
or there are zero or one value between the pivotsP1 < 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 betweenka
andkb
using a heap select algorithm. It is assumedleft <= 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 betweenka
andkb
using a heap select algorithm. It is assumedleft <= 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 betweenka
andkb
using a heap select algorithm. It is assumedleft <= 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 betweenka
andkb
using a sort select algorithm. It is assumedleft <= 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 minimumn
elements belowk
wheren = k - left + 1
. Uses an insertion sort algorithm.Works with any
k
in the rangeleft <= k <= right
and performs a full sort of the range belowk
.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 maximumn
elements abovek
wheren = right - k + 1
. Uses an insertion sort algorithm.Works with any
k
in the rangeleft <= k <= right
and can be used to perform a full sort of the range abovek
.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 indexk
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 indicesk
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 indexk
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 indicesk
correspond to their correctly sorted value in the equivalent fully sorted array.For all indices
[ka, kb]
and any indexi
: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 assumesr - 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 handlesleft == start
and/orend == 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
Partition the array such that indicesk
correspond to their correctly sorted value in the equivalent fully sorted array.For all indices
k
and any indexi
:data[i < k] <= data[k] <= data[k < i]
This function accepts a
UpdatingInterval
of indicesk
that define the range of indices to partition. TheUpdatingInterval
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 forr - 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
andk1 < i < k2
are unsorted. When the range[k0, k3]
contains fully sorted elements the result is set tok1 = k3; k2 == k0
. This can occur ifP1 == P2
or there are zero or one value between the pivotsP1 < 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) wherek == 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 to2 * log3 (x)
.The result is between
2*floor(log3(x))
and2*ceil(log3(x))
. The result is correctly rounded whenx +/- 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.
-