#include <iostream>
using namespace std;
int partition(int *a,int p,int r)
{
	int x=a[r];
	int i=p-1;//note i important which is used for 
				//storage the number smaller than flag x=a[r]
	for (int j=p;j<r;j++)
	{
		if (a[j]<x)// if a[j] smaller than x=a[r],
					//exchange a[i+1] and a[j]
		{
			i++;
			int t=a[j];
			a[j]=a[i];
			a[i]=t;
		}
	}
	int t=a[i+1];// i+1 is the a[r] final position
				//  exchange a[r] and a[i+1]
	a[i+1]=a[r];
	a[r]=t;
	return i+1; //return the a[r] final position i+1
}
void quicksort(int *a,int p,int r)
{
	if (p<r)//the position lower than the higher
	{
		int q=partition(a,p,r);//q is the a[r] final position
						// depart the arry[p...q-1] and arry[q+1...r]
		quicksort(a,p,q-1);
		quicksort(a,q+1,r);
	}
}
int main()
{
	int arry[]={3,2,1,4,5,6,9,8,7,0};
	quicksort(arry,0,9);
	for (int i=0;i<10;i++)
		cout<<arry[i]<<" ";
	cout<<endl;
}