BangaloreInstituteofTechnology
Department of Computer Science and Engineering
DESIGN AND ANALYSIS OF ALGORITHMS LAB (BCSL404)
Program 10
Design and implement C/C++ Program to sort a given set of n integer elements using Quick
Sort method and compute its time complexity. Run the program for varied values of n> 5000
and record the time taken to sort. 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.
Aim:
The aim of this program is to sort ‘n’ randomly generated elements using Quick sort and
Plotting the graph of the time taken to sort n elements versus n.
Definition: Quick sort is based on the Divide and conquer approach. Quick sort divides
array according to their value. Partition is the situation where all the elements before some
position s are smaller than or equal to A[s] and all the elements after position s are greater
than or equal to A[s].
Efficiency: Cbest(n) Є Θ(nlog2n), Cworst(n) ЄΘ(n2),Cavg(n)Є1.38nlog2n
Algorithm: Quick sort (A[l….r])
// Sorts a sub array by quick sort
//Input : A sub array A[l..r] of A[0..n-1] ,defined by its left and right indices l
//and r
// Output : The sub array A[l..r] sorted in non decreasing order
if l < r
s = Partition (A[l..r]) //s is a split position
Quick sort (A[l …s-1])
Quick sort (A[s+1…r])
ALGORITHM Partition (A[l…r])
//Partition a sub array by using its first element as a pivot
// Input : A sub array A[l…r] of A[0…n-1] defined by its left and right indices l and // r (l
< r)
// Output : A partition of A[l…r], with the split position returned as this function’s value
p=A[l]
i=l;
j=r+1;
repeat
delay(500);
repeat i= i+1 until A[i] >= p
repeat j=j-1 until A[J] <= p
Swap (A[i],A[j])
until I >=j
Swap (A[i],A[j]) // Undo last Swap when i>= j
Return j
Program:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// Function to partition the array
int partition(int a[], int low, int high) {
int pivot = a[low]; // Pivot element
int i = low,temp; // Index of smaller element
int j=high+1;// Index of largest element
while(i<=j)
{
do i++;while(pivot>=a[i]);
do j--;while(pivot<a[j]);
if(i<j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
temp=a[low];
a[low]=a[j];
a[j]=temp;
return j;
}
// Function to perform Quick Sort
void quickSort(int a[], int low, int high)
{
int k;
if(low>high) return;
// Partitioning index
k= partition(a, low, high);
// Separately sort elements after partition
quickSort(a, low, k - 1);// left part of pivot element
quickSort(a, k + 1, high); // right part of pivot element
}
int main()
{
srand(time(0)); // Seed for random number generation
int n;
printf("Enter the number of elements: ");
scanf("%d", &n);
int a[n];
printf("Randomly generated array:\n");
for (int i = 0; i < n; i++) {
a[i] = rand() % 1000; // Generating random numbers between 0 and 999
printf("%d ", a[i]);
}
a[n]=9999;
clock_t start=clock();
quickSort(a, 0, n - 1);
clock_t end=clock();
printf("\n Sorted array:\n");
for (int i = 0; i < n; i++) {
printf("%d ", a[i ]);}
printf("\n");
printf("Total time taken to sort %d elememts is %lf\n",n,((double)(end-
start)/CLOCKS_PER_SEC));
return 0;
}
