Module Quicksort2
let qsort_a_i (a : int array) =
let (s : (int × int) Stack.t) = Stack.create()
and 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; (* Austausch *)
i := !i+1; j:=!j-1)
else (i:=!i+1)
done;
!j) (* Rueckgabe *)
else p)
in
let p = ref 0 and r = ref ((Array.length a) - 1) and q = ref 0
in
Stack.push (!p, !r) s;
while Stack.length s > 0
do
let (p,r) = Stack.pop s
in
q := partition (p,r);
if (p < !q) then Stack.push ( p,!q) s else ();
if (!q< r) then Stack.push (!q+1, r) s else ();
done
January 31, 2002