#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <limits.h>
    
    void swap(int *x, int *y)
    {
    	int temp = *x;
    	*x = *y;
    	*y = temp;
    	return ;
    }
    
    int median3(int a[], int left, int right)//Uses median of three partitioning technique
    {
    	int center = (left + right)/2;
    	if (a[center] < a[left]) 
    		swap(&a[left],&a[center]);
    	if (a[right] < a[left])
    		swap(&a[left],&a[right]);
    	if (a[right]< a[center])
    		swap(&a[center],&a[right]);
    	
    	swap(&a[center], &a[right - 1]);//since the largest is already in the right.
    	return a[right - 1];
    }
    
    void quicksort(int a[], int left, int right)
    {
      if (left < right) {
    	int pivot = median3(a,left,right);
        if (left == right - 1) return;
    	int i = left;
    	int j = right - 1;
    	for ( ; ;) {
    		while(a[++i]<pivot) {} 
    		while(pivot<a[--j]) {} 
    		if ( i < j)
    			swap(&a[i],&a[j]);
    		else
    			break ;
    	}
    	swap(&a[i],& a[right -1]);
    	quicksort(a,left,i-1);
    	quicksort(a,i+1,right);
      }
    	return ;
    }
    
    int main(int argc, char* argv[])
    {
    	int i;
    	int a[] = {8,1,4,9,6,3,5,2,7,0};
    	quicksort(a,0,9);
    	for ( i = 0 ; i < 10 ; i++)
    		printf("%d\n",a[i]);
    	return 0;
    }