Rotate, Partition, Select
Three problems that look like they need a second array and do not. Rotating is three reversals. Sorting into three groups is one pass with three pointers. Finding the k-th smallest is quick sort that only follows one side.
The values 100, 7, 42, 100, 999, 7, 250 may be huge or sparse, but only their order matters for many problems, and array-indexed structures such as a Fenwick tree need small indices. Sort the distinct values, 7, 42, 100, 250, 999, and replace each value by its position in that list, its rank. Order is preserved and the range shrinks to 0..4.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 7, with their answers.
The distinct values in order are 7, 42, 100, 250, 999. What rank does 100 get?
Answer: 2. The rank is the value's index in the sorted list of distinct values, counting from 0.
The distinct values in order are 7, 42, 100, 250, 999. What rank does 7 get?
Answer: 0. The rank is the value's index in the sorted list of distinct values, counting from 0.
The distinct values in order are 7, 42, 100, 250, 999. What rank does 42 get?
Answer: 1. The rank is the value's index in the sorted list of distinct values, counting from 0.
The distinct values in order are 7, 42, 100, 250, 999. What rank does 100 get?
Answer: 2. The rank is the value's index in the sorted list of distinct values, counting from 0.
The distinct values in order are 7, 42, 100, 250, 999. What rank does 999 get?
Answer: 4. The rank is the value's index in the sorted list of distinct values, counting from 0.
The distinct values in order are 7, 42, 100, 250, 999. What rank does 7 get?
Answer: 0. The rank is the value's index in the sorted list of distinct values, counting from 0.
The distinct values in order are 7, 42, 100, 250, 999. What rank does 250 get?
Answer: 3. The rank is the value's index in the sorted list of distinct values, counting from 0.
How it runs, step by step
The values 100, 7, 42, 100, 999, 7, 250 may be huge or sparse, but only their order matters for many problems, and array-indexed structures such as a Fenwick tree need small indices. Sort the distinct values, 7, 42, 100, 250, 999, and replace each value by its position in that list, its rank. Order is preserved and the range shrinks to 0..4.
Coordinate compression of 7 values with 5 distinct.
100 is the 3rd smallest distinct value, so it becomes 2.
100 becomes rank 2.
7 is the 1st smallest distinct value, so it becomes 0.
7 becomes rank 0.
42 is the 2nd smallest distinct value, so it becomes 1.
42 becomes rank 1.
100 is the 3rd smallest distinct value, so it becomes 2. An earlier 100 got the same rank: equal values stay equal.
100 becomes rank 2.
999 is the 5th smallest distinct value, so it becomes 4.
999 becomes rank 4.
7 is the 1st smallest distinct value, so it becomes 0. An earlier 7 got the same rank: equal values stay equal.
7 becomes rank 0.
250 is the 4th smallest distinct value, so it becomes 3.
250 becomes rank 3.
Compressed to ranks 0..4. Comparisons between any two entries come out the same as before, so anything that depends only on order, from a Fenwick tree to counting inversions, can now index by rank. O(n log n) for the sort and one binary search per value.
Compression complete.
Write it yourself
Define quickSelect(values, k) and return the kth smallest value, counting from 1. It runs in your browser against this lesson's own 3 examples.
// Partition around a pivot. The pivot lands in its final place, so only the side holding k needs to be looked at again.function quickSelect(values, k) { return 0;}
Remember
- Reverse all, then reverse each part: rotation in O(n) time and O(1) space.
- In the three-way partition, mid does not move after swapping with high, because what came back is unknown.
- Quickselect drops half the array each round without sorting it, so the expected cost is O(n).
Related
Where this is used
Developer toolsstd::rotate and moving a block of text
Moving a selected block of lines up or down in an editor, or dragging an item to a new position in a list, is a rotation of the range between the block and its destination. The C++ standard library exposes this as std::rotate, and libstdc++ picks between the same two tricks depending on the iterator: the three-reversal version for bidirectional iterators, the gcd-cycle version for random access. Doing it in place matters because the buffer being rearranged is the document itself.
Standard librariesSorts that survive duplicate-heavy data
Plain quicksort degrades towards O(n^2) when an array has few distinct values, because every element equal to the pivot keeps piling onto one side. Go's sort package uses pattern-defeating quicksort, and Rust's slice::sort_unstable uses ipnsort, which is built from it. Both notice when a pivot repeats and switch to a partition that separates values equal to the pivot from values above it. The equal block is then in its final position, so the sort steps past it and carries on with the rest. That reaches the same end state as the Dutch flag arrangement by a different route, for the same reason: a run of duplicates should be settled once and never partitioned again.
DataMedians and top-k without sorting
NumPy's np.partition and np.argpartition run introselect, and np.median calls partition internally: to get the middle value of a billion numbers only that one position has to be correct, not the whole array. C++ offers the same operation as std::nth_element, which the standard requires to be linear on average. Anything phrased as the top k, the p95 or the median is a selection problem, and sorting first throws away the gap between O(n) and O(n log n).
DatabasesDictionary encoding in columnar stores
Apache Parquet and ClickHouse's LowCardinality columns store each distinct value once in a dictionary and replace every entry with a small integer index into it, which is coordinate compression under another name. A column of URLs becomes a column of ints that packs tightly and compares in one instruction. When the dictionary is kept in sorted order the codes preserve the original ordering, so a predicate like value < x can be answered on the integers without touching the strings at all.
Why it works this way
Why three reversals rotate the array
Rotating right by r means the last r values move to the front keeping their order, and the first n - r follow keeping theirs. Reversing the whole array puts both groups on the correct side in one step, but each group comes out backwards. Reversing each group in place fixes that, and across the three passes no element is touched more than twice, which is where the O(n) time and O(1) space come from. The obvious alternative, shifting everything one place and repeating r times, costs O(n * r).
Rotating by k when k is zero, negative, or larger than the array
Only k mod n matters, because n rotations put the array back where it started, which is why the code reduces k first. When that remainder is 0 the call becomes reverse(a, 0, -1), so reverse has to treat an empty or backwards range as a no-op instead of indexing past the end. An empty array has to be rejected earlier still, because k % a.size divides by zero before any reversal runs. In Kotlin, Java, C and Go the % operator keeps the sign of the left operand, so a negative k yields a negative remainder: rotate left by k either needs ((k % n) + n) % n or should be turned into a right rotation by n - k.
Why mid advances after one swap but not the other
The loop maintains four regions: below low is less than the pivot, low up to mid is equal, past high is greater, and mid through high is the part nobody has looked at yet. Swapping with low trades the current value for one already known to equal the pivot, so that slot is settled and mid can step forward. Swapping with high pulls in a value from the unexamined region, so mid has to inspect it before moving. The same invariant explains the loop condition: it must be mid <= high, because when the two meet there is still one unexamined element left.
Why quickselect is O(n) when quicksort is O(n log n)
Both pay a partition costing the length of the current range, but quicksort then recurses into both sides while quickselect follows only the side that can contain position k. The work is n + n/2 + n/4 and so on, a geometric sum of about 2n rather than n log n. That assumes the pivot lands near the middle: an already sorted array with a first-element pivot gives ranges of n, n-1, n-2 and O(n^2) in total, which is why real implementations randomise the pivot or fall back to median of medians after too many bad splits. Note also that quickselect rearranges the array it is given, so copy first if the original order still matters.
Read more
- Dutch national flag problemWikipedia
- QuickselectWikipedia
- Median of mediansWikipedia
- K-th order statistic in O(N)cp-algorithms
- std::rotatecppreference