DAA - Solved Question of QuickSort with Different Value of N

Write a program to sort a given set of elements using the Quicksort method and determine the time required to sort the elements. Repeat the experiment for different values of n, the number of elements in the list to be sorted, and plot a graph of the time taken versus n. The elements can be read from a file or can be generated using the random number generator.

Program:

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 
int partition(int a[], int l,int h) {
	int pivot=a[l]; 
	int i=l-1; 
	int j=h+1; 
	while(1){ 
		do
		j--; 
		while(a[j]>pivot); 
		do 
		i++; 
		while(a[i]<pivot); 
		if(i<j){ 
			int temp=a[i]; 	
			a[i]=a[j]; a[j]=temp; 
		}
		else 
			return j; 
	} 
}
void quickSort(int a[],int p,int r){ 
	if(r>p) { 
		int q=partition(a,p,r); 	
		quickSort(a,p,q); 
		quickSort(a,q+1,r); 
	} 
}
int main() { 
	int n; clock_t start, end; 
	double total_cputime;
	printf("Enter size of array : "); 
	scanf("%d", &n); 
	int a[n]; 
	printf("Best case: "); 
	for (int i = 0; i < n; i++) {
		 a[i] = 20; 
	}
	start = clock(); 
	quickSort(a,0,n-1); 
	end = clock(); 
	total_cputime = ((double)(end - start)) / CLOCKS_PER_SEC; 
	printf("\ntotal_cputime in second = %f\n", total_cputime); 
	printf("Worst case: "); 
	for (int i = 0; i < n; i++) { 
		 a[i] = i+1; 
	}
	start = clock(); 
	quickSort(a,0,n-1); 
	end = clock(); total_cputime = ((double)(end - start)) / CLOCKS_PER_SEC; 
	printf("\ntotal_cputime in second = %f\n", total_cputime); 
	printf("Avg case: "); 
	for (int i = 0; i < n; i++) { 
		a[i] = rand() % n; 
	}
	start = clock(); 
	quickSort(a,0,n-1); 
	end = clock(); 
	total_cputime = ((double)(end - start)) / CLOCKS_PER_SEC; printf("\ntotal_cputime in second = %f\n", total_cputime); 
	return 0;
}

Output

Enter size of array : 10000

Best case: 

total_cputime in second = 0.000695

Worst case: 

total_cputime in second = 0.113646

Avg case: 

total_cputime in second = 0.001620

Graph