int random_in_range(int a, int b)
{ return random() % (b - a + 1) + a; }

void swap(int & x, int & y)
{ int t = x;
  x = y;
  y = t; }

int partition(int A[], int min, int max)
{ int i = min, j = max, pivpos = random_in_range(min, max);
  int pivot = A[pivpos];
  while (j >= i)
  { while (i <= max) 
    { if (A[i] > pivot)
        break;
      i += 1; }
    while (j >= min)
    { if (A[j] < pivot)
        break;
      j -= 1; }
    if (i < j)
    { swap(A[i], A[j]);
      i += 1;
      j -= 1; } }
  if (pivpos > i)
  { swap(A[pivpos], A[i]);
    return i; }
  if (pivpos < j)
  { swap(A[pivpos], A[j]);
    return j; }
  return pivpos; }

void sort(int A[], int min, int max)
{ if (max - min < 1)
    return;
  int p = partition(A, min, max);
  sort(A, min, p - 1);
  sort(A, p + 1, max); }

void sort(int A[], int num)
{ sort(A, 0, num-1); }