A value is not a record
Suppose a finite array contains records, each with a key from a totally ordered set and a distinct identity. We want exactly records with the smallest keys, where . Keys may repeat. The task is not necessarily to sort the output. The selected key multiset is unique, but the selected identities need not be unless a rule resolves equal keys. We will choose earlier original positions when a tie crosses the selection boundary, and return the selected records in their original input order.
For , return the empty list. For , return all records in input order. For , let be the key of rank , counted from one with multiplicity. The three groups are records with key less than, equal to, and greater than ; call them . The definition of rank gives
Definition 4.2.1
(Smallest-k selection with the earliest-position tie rule)
Let the keys, sorted with multiplicity, be . A set of exactly records is a smallest- selection if its multiset of keys equals ; equivalently, every key in is at most every key outside . Among all smallest- selections, the earliest-position selection is the one whose records of are the earliest ones in the input. It is returned in input order.
Thus every valid answer must include all , exclude all , and select exactly records from . Including all records whose key is at most can return too many. The boundary rule chooses the earliest records of by their original positions.
Counterexample mode
Keeping every key at most the threshold
Claim: to get the smallest records, find and keep every record whose key is at most . Take the keys and . The sorted keys are , so and every key is at most : the rule keeps all five records instead of three. Here holds the keys , so and only of the three records with key may be kept. The repaired rule keeps the records at positions , with keys in input order. Ties on the boundary are exactly where a threshold filter and a count disagree.
Observe the boundary
Worked example 4.2.2
(Rank 4 in a list with repeated keys)
For the list and rank , choose the first value as pivot. The less, equal and greater blocks are , and . Since , the answer is ; no further partition is needed. As a check, the sorted list is , whose fourth entry is .
In the default trace, , and . The component shows a reproducible fixed-first-pivot selection trace, not a randomized algorithm and not a record-identity selector. If the seven records are named in input order, the selected identities under our tie rule are : the three keys below and the earliest key equal to . Returning preserves input order; it does not sort by key. The paragraph above the component provides the key partition as static study material.
Worked example 4.2.3
(Two of three boundary records, in input order)
Take the keys at positions and . The sorted keys are , so , (the key ) and (positions ). The quota for key is . The second scan reads position (key , quota used ), skips position (key ), emits position (key , quota used ), skips positions and because the quota is spent or the key is above , and emits position (key ). The output is positions , with keys . The third record with key is left out, though its key equals .
Worked example 4.2.4
(Degenerate cases: k = 0, k = n and all keys equal)
For the answer is the empty list for every input, and no threshold is needed. For every record is returned in input order. If the keys are and , then , , and , so the quota is : the second scan emits positions and and stops emitting afterwards. The inequality holds, as the rank definition guarantees. For the same scan returns all four records, which agrees with the rule for .
Why the construction is correct
First find using any correct rank-selection routine. Scan the original array to count ; then scan it again. Emit every record with key less than , and emit only the first records whose key equals . Ignore keys above . Because the second scan reads original positions from left to right, emitted records retain input order and the equal-key choice is deterministic.
Theorem 4.2.5
(Two-scan selection is the earliest-position selection)
Let , let and . The two-scan procedure emits exactly records, in input order, and the emitted set is the earliest-position smallest- selection. Moreover, every smallest- selection contains all of , contains no record of , and contains exactly records of .
Proof
(Counting keys and forcing the boundary groups)
The rank inequality gives , so the quota of boundary records can be filled and the second scan emits records. Exactly of the sorted keys are below , namely , and all equal , because they are at most and not below it. The emitted keys are the keys of together with copies of , so their multiset is and the emitted set is a smallest- selection.
Now let be any smallest- selection, so every key in is at most every key outside . If some were outside , every key in would be at most the key of , which is below ; then and , contradicting . If some were in , every key outside would be at least the key of , which exceeds . But has records and has only places left for them, so a record of , with key at most , lies outside , a contradiction. Hence is plus records of , and the earliest-position rule picks the first of , which is what the scan emits.
Proof X-ray
Where the rank inequality and the tie rule are used
The counting step uses only the number of keys below and the fact that ; it never looks at which record carries which key. That is why any correct rank routine may be used to find . The lower half of is what makes the quota at least one, so a boundary record is really needed; the upper half makes the quota achievable. If were taken to be instead, the inequality could fail and the scan could emit the wrong number of records. The earliest-position rule plays no role in the key multiset; it only chooses among records with equal keys, so that the output is determined.
The component exposes one possible way to obtain . In a three-way partition with local one-based rank , keep the less block if ; stop in the equal block if ; otherwise keep the greater block and replace by . Rank adjustment applies to the current subproblem. The component's particular trace stops in the equal block; its selection result alone does not preserve or choose record identities.
Cost, mutation and a streaming alternative
If the rank routine takes key comparisons, the two additional scans take comparisons. The total inherits the routine’s worst-case or expected guarantee, as appropriate. If the routine mutates its input, run it on a private copy of the keys so the second scan still sees the original records in order. The key copy needs extra key slots, in addition to output records; the selection routine may use further workspace. Another design stores original indices with records before mutation, selects the smallest pairs, and sorts the selected indices in comparisons to restore input order. Selecting by the pairs is what enforces the earliest-position tie rule.
Concept lensStructural
Make all keys distinct by pairing them with positions
Replace each record by the pair , ordered lexicographically. These pairs are all distinct, so the rank- pair is a genuine threshold, and the earliest-position selection is exactly the set of records whose pair is at most . For the keys and , the sorted pairs begin , so and the selected positions are .
A fixed-first-pivot quickselect can take comparisons. A suitable uniformly randomized pivot rule with three-way partition has an expected linear selection bound under its stated model; it is not a worst-case bound for every run, and the component does not simulate randomness. If the output must also be sorted by key, sorting the selected records adds comparisons with a comparison sort.
For a stream with , another contract keeps a max-heap of at most records ordered lexicographically by . Distinct indices and the total order on keys make these pairs totally ordered. After each arrival it contains the smallest pairs: if the heap is not full, insert the pair; if full and the arriving pair is no smaller than the maximum, discard it; if full and the pair is smaller, replace the maximum and restore heap order. Induction proves the invariant. This costs comparisons and stored records. Heap order is not output order; returning records by original index needs an additional ordering step. The empty- case stores nothing.
Common mistake
(Running the second scan on a rearranged array)
Suppose records have keys and . Then , , and the earliest-position selection is , returned as . If the rank routine has rearranged the array into and the second scan reads that array, it emits and then the first it meets, which is . The identity is wrong and the order is not the input order. Scan the original records, or a copy that kept their original positions.
Common mistake
(Replacing the heap maximum on an equal key)
In the streaming version with , let three records with the same key arrive at indices . The heap holds and . The arriving pair is larger than the maximum in the lexicographic order, so it is discarded. Replacing the maximum whenever the key is not larger would keep the later record and drop an earlier one, which breaks the earliest-position rule.
Exercises
Quick check
(For keys with distinct identities in input order and , find , , and the selected positions under the stated tie rule.)
Sort the keys with multiplicity before reading off the fourth one.
Solution · Answer
The sorted keys are , so , , . Select positions : all keys below and the earliest , returned in original order.
Quick check
(Why is returning every record with key at most wrong when a tie crosses the boundary?)
Count the records returned and compare with .
Solution · Answer
For the keys of the previous check it returns all six records rather than four. Only one of the three equal-boundary records is needed.
Quick check
(What extra issue arises if rank selection rearranges the only copy of the input but the output must be in original order?)
Think about what the second scan reads.
Solution · Answer
The selection may destroy original order. Preserve an unchanged input copy, or retain original indices and explicitly restore the required order; merely knowing the selected key values is not enough to recover record identities.