Previous Contents Next

Module Quicksort1

Imperative implementation of quicksort, using (integer) arrays
let qsort_a_r (aint array) =
   let partition ((pint), (rint)) =
     (if (p < rthen 
       (
       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((pint), (rint)) =
     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)
January 31, 2002
Previous Contents Next