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.