src/test/resources/scripts/benchmark.av

fn swap(xs, l, r) {
  let temp = xs[l];
  xs[l] = xs[r];
  xs[r] = temp; 
}

fn partition(xs, l, r, p)  {
  while l <= r {
    while xs[l] < p  {
      l = l+1;
    }
    while xs[r] > p {
      r = r -1;
    } 
    if l <= r {
      swap(xs, l, r);
       l = l+1;
       r = r -1;
    }
  }
  return l;
}

fn qsort0(xs, l, r) {
  if l >= r {
    return;
  }
  
  let p = xs[(l+r)/2];
  let i = partition(xs, l, r, p);
  qsort0(xs, l, i-1);
  qsort0(xs, i, r);
}

qsort = lambda(xs) ->
  qsort0(xs, 0, count(xs)-1);
  return xs;
end;

fn rand_list(n) {
  let a = seq.list();
  for i in range(0, n) {
    seq.add(a, rand(n));
  }
  return a;
}


let n = 100000;
{
  ## warm up
  for i in range(0, 10000) {
    let a = rand_list(5);
    qsort(a);
  }
}
{
  ## benchmark
  println("Begin benchmark...");
  start = now();
  for i in range(0, n) {
    let a = rand_list(50);
    qsort(a);
  }
  cost = now() - start;
  println("cost: " + cost + " ms, n: " + n);
  println(cost/double(n) +" ms/ops");
}