Selection by tail recursion


function select( s : integer; var r : RecordArray; lo, up : integer ) : typekey; var i, j : integer; tempr : ArrayEntry; begin s := s+lo-1; if (s<lo) or (s>up) then Error {*** selection out of bounds ***} else begin while (up>=s) and (s>=lo) do begin i := lo; j := up; tempr := r[s]; r[s] := r[lo]; r[lo] := tempr; {*** split file in two ***} while i<j do begin while r[j].k > tempr.k do j := j-1; r[i] := r[j]; while (i<j) and (r[i].k<=tempr.k) do i := i+1; r[j] := r[i] end; r[i] := tempr; {*** select subfile ***} if s<i then up := i-1 else lo := i+1 end; select := r[s].k end end;

Pascal source (522.sel.p)



© Addison-Wesley Publishing Co. Inc.