// quicksort in C
int swap(int *a, int *b)
{
  int t = *a;
  *a = *b;
  *b = t;
}

int partition(int a[], int n)
{
  int left = 0;
  int right = n - 1;
  // mai mici               mai mari
  // vvvvvv                 vvvvv
  // 4    3    8    7    6    9
  //           ^         ^
  //          left     right
  // 
  // 4    3    7    8    6    9
  //                ^    ^
  //              left right
  // 
  // 4    3    7    6    8    9
  //                     ^
  //              left right
  while (left < right) {
    if (a[right] > a[left]) {
      right--;
    } else if (a[left + 1] <= a[right]) {
      swap(&a[left], &a[left + 1]);
      left++;
    } else {
      swap(&a[left + 1], &a[right]);
    }
  }
  return left;
}

int qs(int a[], int n)
{
  if (n > 0) {
    int pos = partition(a, n);
    qs(a, pos);
    qs(a + pos + 1, n - pos - 1);
  }
}