module: qsort

define constant <int> = limited(<integer>);
define constant <int-vector> = limited(<simple-vector>, of: <integer>);

define sealed inline method rnd (x :: <int>) 
 => (<int>);
  random(x);
end;

define sealed inline method swap (a :: <int-vector>, p :: <int>, q :: <int>)
 => (object);
  let tmp :: <int> = a[p];
  a[p] := a[q];
  a[q] := tmp;
end;

define sealed inline method partition (a :: <int-vector>, p :: <int>, q :: <int>) 
 => (<int>);
  let f :: <int> = p + rnd(q - p);
  swap(a, p, f);

  let pivot :: <int> = a[p];
  let i :: <int> = p;
  for (j from (p + 1) below q)
    if (a[j] <= pivot)
      i := i + 1;
      swap(a, i, j);
    end if;
  end;
  swap(a, p, i);
  i
end;
    
define sealed inline method quicksort (a :: <int-vector>, p :: <int>, q :: <int>)
  if (p < q)
    let r :: <int> = partition(a, p, q);
    quicksort(a, p, r - 1);
    quicksort(a, r + 1, q);
  end;
end;

//
begin
  let N :: <int> = 10000000;
  let test :: <int-vector> = make(<int-vector>, size: N, fill: 0);
  
  for(i from 0 below N)
    test[i] := rnd(N);
  end;

  quicksort(test, 0, N - 1);
end;