Computer Science: 5th sem ADA Lab Program 7

Analysis and Design of Algorithms Lab.

Question 7.

//Sort a given set of elements using quick sort method and determine the time required to sort the elements

#include <iostream>

#include <conio.h>

#include <time.h>

using namespace std;

void swap(int &a,int &b)

{

int tmp=a;a=b;b=tmp;

}

int partition(int *arr,int start,int end)

{

int pivot=arr[start];

int i=start,j=end+1;

do {



do {

i++;

}while(arr[i]<pivot);

do {

j--;

}while(arr[j]>pivot);

swap(arr[i],arr[j]);

}while(i<j);

swap(arr[i],arr[j]);

swap(arr[start],arr[j]);

return j;

}

void quickSort(int *arr,int start,int end)

{

if(start<end)

{

int p=partition(arr,start,end);

cout<<"\n";

for(int i=start;i<=end;i++)

cout<<arr[i]<<" ";

quickSort(arr,start,p-1);

quickSort(arr,p+1,end);

}

}

void main()

{

int n;

cout<<"Enter the size of the array:";cin>>n;

cout<<"Enter the array:\n\n";

int *arr=new int[n+1];

for(int i=0;i<n;i++)

cin>>arr[i];



cout<<"\nQuick Sorting...\n\n";

int start=clock();

quickSort(arr,0,n-1);

int time1=(clock()-start)/CLK_TCK;

cout<<"\nTime taken:"<<time1<<"\n\n";

cout<<"\n";

for(int i=0;i<n;i++)

cout<<arr[i]<<" ";

getch();

}