#include<iostream.h>
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
static int counter=0;
static int counter0=0;
void swap(int *a,int *b){
    int c;
	if(*a>*b){
		c=*a;
	    *a=*b;
		*b=c;
	}
}
int partition(int a[],int p,int r){
	int i=p;
	int	j=r+1;
	int x=a[p];  
    while(1){
		do{
			if(i<=r)
			counter++;
		}while(a[++i]<x);
		do{
			if(j>=p)
			counter++;
		}while(a[--j]>x);			 
		if(i>=j)
			break;
		 swap(&a[i],&a[j]);
		 counter0++;
		}
	a[p]=a[j];
	a[j]=x;	 
	counter0++;
	return j;
}
void qSort(int a[],int p,int r){	 
 	if(p<r)
	{
	int q=partition(a,p,r); 
	qSort(a,p,q-1);
	qSort(a,q+1,r);
	}
}
 

void main(){ 
	int i,n;
	cout<<"輸入比較個數：(不超過10000個）";
	cin>>n;
	if(n<=0||n>10000){
		cout<<"輸入非法！";	 
		return;
	} 
	int a[10000];
	cout<<"比較前為："<<endl;
	for(i=0;i<n;i++){
		a[i]=rand()%10000;
		cout<<a[i]<<' ';
	  	if(i%10==0) 	 	 
	 	cout<<endl; 
		}  
	cout<<endl;
    qSort(a,0,n-1);
	cout<<"比較后為："<<endl;
 	for(int j=0;j<n;j++){
		cout<<a[j]<<' ';
		if(j%10==0)
			cout<<endl;	 
	} 
	cout<<endl;
	cout<<"比較次數為：";
	cout<<counter<<endl;
	cout<<"實際交換次數為：";
	cout<<counter0<<endl;
	cout<<"理論比較次數：";
	cout<<log(n)/log(2)*n<<endl;
	
}