#include <stdio.h>
#include <stdlib.h>


void swap(int *a , int *b) {
   int temp = *a;
   *a =  *b;
   *b =  temp;
}
void partition(int x[], int *left , int *right, int pivot) {
    do {
        while(x[*left] < pivot)
	       (*left)++;
	  while(x[*right] > pivot)
	      (*right)--;
 
	  if(*left < *right) {
            swap(&x[*left] , &x[*right]); //same swap as in selection sort
	      (*left)++;
	      (*right)--;
	  }
	  else if(*left == *right)
	       (*left)++;
     } while(*left <= *right);
}

void QuickSort(int x[], int start, int end) {
     int left = start, right = end, pivot = x[(start + end)/2];
     partition(x, &left, &right, pivot);
     if(start < right)
         QuickSort(x, start, right);
     if(left < end)
         QuickSort(x, left, end);
}
int main() {
  int i, x[]={2, 5, 9, 4, 0, 1, 6, 8, 7, 3};

  QuickSort(x,0, 9);

  for(i = 0; i < 10; i++)
    printf("%d ", x[i]);

  return 0;
}