in commons-numbers-arrays/src/main/java/org/apache/commons/numbers/arrays/QuickSelect.java [2557:2722]
private static int partition(int[] a, int left, int right, int[] bounds) {
// Pick 2 pivots from 5 approximately uniform through the range.
// Spacing is ~ 1/7 made using shifts. Other strategies are equal or much
// worse. 1/7 = 5/35 ~ 1/8 + 1/64 : 0.1429 ~ 0.1406
// Ensure the value is above zero to choose different points!
final int n = right - left;
final int step = 1 + (n >>> 3) + (n >>> 6);
final int i3 = left + (n >>> 1);
final int i2 = i3 - step;
final int i1 = i2 - step;
final int i4 = i3 + step;
final int i5 = i4 + step;
Sorting.sort5(a, i1, i2, i3, i4, i5);
// Partition data using pivots P1 and P2 into less-than, greater-than or between.
// Pivot values P1 & P2 are placed at the end. If P1 < P2, P2 acts as a sentinel.
// k traverses the unknown region ??? and values moved if less-than or
// greater-than:
//
// left less k great right
// |P1| <P1 | P1 <= & <= P2 | ??? | >P2 |P2|
//
// <P1 (left, lt)
// P1 <= & <= P2 [lt, k)
// >P2 (gt, right)
//
// At the end pivots are swapped back to behind the less and great pointers.
//
// | <P1 |P1| P1<= & <= P2 |P2| >P2 |
// Swap ends to the pivot locations.
final int v1 = a[i2];
a[i2] = a[left];
a[left] = v1;
final int v2 = a[i4];
a[i4] = a[right];
a[right] = v2;
// pointers
int less = left;
int great = right;
// Fast-forward ascending / descending runs to reduce swaps.
// Cannot overrun as end pivots (v1 <= v2) act as sentinels.
do {
++less;
} while (a[less] < v1);
do {
--great;
} while (a[great] > v2);
// a[less - 1] < P1 : a[great + 1] > P2
// unvisited in [less, great]
SORTING:
for (int k = less - 1; ++k <= great;) {
final int v = a[k];
if (v < v1) {
// swap(a, k, less++)
a[k] = a[less];
a[less] = v;
less++;
} else if (v > v2) {
// while k < great and a[great] > v2:
// great--
while (a[great] > v2) {
if (great-- == k) {
// Done
break SORTING;
}
}
// swap(a, k, great--)
// if a[k] < v1:
// swap(a, k, less++)
final int w = a[great];
a[great] = v;
great--;
// delay a[k] = w
if (w < v1) {
a[k] = a[less];
a[less] = w;
less++;
} else {
a[k] = w;
}
}
}
// Change to inclusive ends : a[less] < P1 : a[great] > P2
less--;
great++;
// Move the pivots to correct locations
a[left] = a[less];
a[less] = v1;
a[right] = a[great];
a[great] = v2;
// Record the pivot locations
final int lower = less;
bounds[2] = great;
// equal elements
// Original paper: If middle partition is bigger than a threshold
// then check for equal elements.
// Note: This is extra work. When performing partitioning the region of interest
// may be entirely above or below the central region and this can be skipped.
// Here we look for equal elements if the centre is more than 5/8 the length.
// 5/8 = 1/2 + 1/8. Pivots must be different.
if ((great - less) > (n >>> 1) + (n >>> 3) && v1 != v2) {
// Fast-forward to reduce swaps. Changes inclusive ends to exclusive ends.
// Since v1 != v2 these act as sentinels to prevent overrun.
do {
++less;
} while (a[less] == v1);
do {
--great;
} while (a[great] == v2);
// This copies the logic in the sorting loop using == comparisons
EQUAL:
for (int k = less - 1; ++k <= great;) {
final int v = a[k];
if (v == v1) {
a[k] = a[less];
a[less] = v;
less++;
} else if (v == v2) {
while (a[great] == v2) {
if (great-- == k) {
// Done
break EQUAL;
}
}
final int w = a[great];
a[great] = v;
great--;
if (w == v1) {
a[k] = a[less];
a[less] = w;
less++;
} else {
a[k] = w;
}
}
}
// Change to inclusive ends
less--;
great++;
}
// Between pivots in (less, great)
if (v1 != v2 && less < great - 1) {
// Record the pivot end points
bounds[0] = less;
bounds[1] = great;
} else {
// No unsorted internal region (set k1 = k3; k2 = k0)
bounds[0] = bounds[2];
bounds[1] = lower;
}
return lower;
}