Use three-way array partitioning around a saved pivot value:
procedure Partition(var a; l, r; var m, n)
x := a[Pivot(a,l,r)]
m := l
k := l
n := r
while k < n do
if a[k] < x then
swap(a[k], a[m])
m := m+1
k := k+1
else if a[k] > x then
n := n-1
swap(a[k], a[n])
else
k := k+1Assume a total ordering on the element keys. The loop invariant partitions the original segment intowith and the segment's multiset unchanged. A smaller entry exchanges with the first equality position; the displaced equal entry is accounted for when both indices advance. A greater entry exchanges with the last unclassified position, so
k must stay to inspect the incoming entry. The loop variant decreases by one in every branch.At termination the equality interval is . It is nonempty because the pivot value came from the segment and swaps preserve the bag. The stronger strict outer-region conditions therefore imply the requested overlapping inequalities and . Storing the pivot value avoids following an array position whose contents may move.
Four-region invariant for duplicate-aware array partitioning
. The unclassified interval shrinks at every comparison. On completion, the equal interval remains nonempty and both outer intervals can be discarded or searched by rank. Details.
Keep the target as an absolute, zero-based array index:
function Find(i; var a; l, r): T
require l <= i < r
Partition(a,l,r,m,n)
if i < m then
return Find(i,a,l,m)
else if i >= n then
return Find(i,a,n,r)
else
return a[i]The order statistic belongs to the lower segment, equality interval or upper segment according to the index comparison. In the middle interval its value is the pivot; otherwise Quickselect recurses only into the relevant outer interval. The nonempty equality interval guarantees a strictly shorter retained segment. The procedure sorts neither discarded segment. Since indices remain absolute, the right recursion does not subtract
n from i.function Select(i; var a; N): T
require 1 <= i <= N
return Find(i-1,a,0,N)Thus rank is index . The boundary ranks return the minimum and maximum, and repeated values occupy as many ranks as their multiplicities in the multiset.
For an active segment of length , partitioning takes comparisons. If pivot choice costs at most linear time and always leaves at most an fraction on the searched side, the total is bounded by the geometric series , giving time.
Repeatedly choosing an extreme pivot while searching toward the other end retains lengths , giving worst-case time. The equality interval makes an all-equal input finish in one partition. Independent uniform random pivots give expected linear time for duplicate-aware Quickselect, but this is not a deterministic worst-case guarantee. More expensive pivot selection must be included in the cost rather than hidden inside the partition bound.
Each recursive call is a tail call: nothing remains to be computed after it returns. Replace it by an update of the retained bounds:
function Select(i; var a; N): T
require 1 <= i <= N
target := i-1
l := 0
r := N
while true do
Partition(a,l,r,m,n)
if target < m then
r := m
else if target >= n then
l := n
else
return a[target]The loop invariant retains the target order statistic in with . Each nonreturning iteration strictly decreases , because is nonempty. This proves termination and replaces recursive stack space by auxiliary space, apart from the pivot routine's own storage.
Articles by others on the same topic
There are currently no matching articles.