Module Quicksort1
Imperative implementation of quicksort, using (integer) arrays
let qsort_a_r (a: int array) =
let partition ((p: int), (r: int)) =
(if (p < r) then
(
let x = a.(p) (* Pivot *)
and i = ref p and j = ref r and h = ref 0
in
while (!i)£(!j)
do
while a.(!i) < x do i := !i + 1; done;
while a.(!j) > x do j := !j - 1; done;
if (!i)<(!j)
then
(h := a.(!i); a.(!i) ¬ a.(!j); a.(!j) ¬ !h; (* exchange *)
i := !i+1; j:=!j-1)
else (i:=!i+1)
done;
!j) (* return *)
else p)
in let rec qsort((p: int), (r: int)) =
if (p < r)
then
(let q = ref 0
in
q := partition(p,r);
qsort(p,!q);
qsort(!q+1,r))
else
()
in qsort(0, Array.length a - 1)
Pages last (re-)generated October 28, 2002 (Martin Steffen)