Previous Contents Next

Module Quicksort2

let qsort_a_i (a : int array) = 
   let (s : (int × intStack.t) = Stack.create()
   and partition ((pint),(rint)) =
     (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, !rs;
   while Stack.length s > 0
   do 
     let (p,r) = Stack.pop s
     in
     q := partition (p,r);
     if (p < !qthen Stack.push ( p,!qs else ();
     if (!qrthen Stack.push (!q+1, rs else ();
   done
January 31, 2002
Previous Contents Next