#include <stdio.h>
#include <time.h>
#define MAX_SIZE 5001
void SWAP(int *a, int *b){
int temp;
temp=*a;
*a=*b;
*b=temp;
}
void quicksort(int a[], int left, int right)
{
int pivot,i,j;
if(left<right){
i=left;
j=right+1;
pivot = a[(left+right)/2];
do{
do i++; while (a[i] <pivot && i<j);
do j--; while (a[j] >pivot);
if(i<j) SWAP(&a[i], &a[j]);
} while(i<j);
SWAP(&a[left], &a[j]);
quicksort(a, left, j-1);
quicksort(a, j+1, right);
}
}
void main()
{
int i,n,step = 500;
int a[MAX_SIZE];
double duration;
for(i=1; i<=10; i++)
{
a[i] = rand();
}
printf(" n time\n");
for(n=0; n<=5000; n+=step)
{
clock_t start = clock();
long repetition= 0;
do
{
repetition++;
for(i=0; i<n; i++)
a[i] =n-i;
quicksort(a, 1,10);
}while(clock() -start <1000);
duration = ((double) (clock() -start))/CLOCKS_PER_SEC;
duration/=repetition;
printf("%6d %f\n", n,duration);
if(n==1000) step =1000;
}
}