Quicksort (with bounded stack usage).


procedure sort( var r : ArrayToSort; lo, up : integer ); var i, j : integer; tempr : ArrayEntry; begin while up>lo do begin i := lo; j := up; tempr := r[lo]; {*** 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; {*** Sort recursively, the smallest first ***} if i-lo < up-i then begin sort(r,lo,i-1); lo := i+1 end else begin sort(r,i+1,up); up := i-1 end end end;

Pascal source (413b.sort.p)



© Addison-Wesley Publishing Co. Inc.