#include <iostream.h>
#include <stdlib.h>
#include <time.h>
#include <windows.h>

int split(int A[],int m,int n);
void quicksort(int A[],int low,int high);

void main()
{
	srand(time(0));
	int n;
	cout<<"請輸入數組規模n:";
	cin>>n;

	int *a;
	a=new int[n+1];
	for(int i=1;i<=n;i++)
	{
		a[i]=rand();
	}
	cout<<"生成隨機數組為:"<<'\n';
	for(i=1;i<=n;i++)
	{
		cout<<a[i]<<'\t';
	}
	cout<<endl;
	quicksort(a,1,n);
	cout<<"快速排序后數組為:"<<'\n';
	for(i=1;i<=n;i++)
	{
		cout<<a[i]<<'\t';
	}
	cout<<endl;
	delete a;

}	

void quicksort(int A[],int low,int high)
{
	int w;
	if(low<high)
	{
		w=split(A,low,high);
		quicksort(A,low,w-1);
		quicksort(A,w+1,high);
	}
}

int split(int A[],int low,int high)
{
	int i=low,t,w;
	int x=A[low];
	for(int j=low+1;j<=high;j++)
	{
		if(A[j]<=x)
		{
			i=i+1;
			if(i!=j)
			{
				t=A[i];
				A[i]=A[j];
				A[j]=t;
			}
		}
	}
	t=A[low];
	A[low]=A[i];
	A[i]=t;
	w=i;
	return w;
}