Computer Science: 5th sem ADA Lab Program 3

Analysis and Design of Algorithms Lab.

Question 3

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

#include <iostream>

#include <conio.h>

#include <time.h>

using namespace std;

void merge(int *arr,int *a,int n1,int *b,int n2)

{

//function adds array a and b and stores in arr (arr=a+b)

int i=1,j=1,k=1;

while(i<=n1+n2 && j<=n1 && k<=n2)

{

if(a[j]<b[k])

arr[i++]=a[j++];

else

arr[i++]=b[k++];

}

while(i<=n1+n2 && j<=n1)

arr[i++]=a[j++];

while(i<=n1+n2 && j<=n2)

arr[i++]=b[j++];

}

void arrCopy(int *a,int i,int *b,int j,int n)

{

int end=i+n;

for(;i<=end;i++,j++)

a[i]=b[j];

}

void mergeSort(int *arr,int start,int n)

{

if(n>1)

{

int *a=new int[(n/2)+1];

int *b=new int[(n/2)+1];

arrCopy(a,1,arr,start,(n/2));

arrCopy(b,1,arr,(n/2)+1,n-(n/2));

mergeSort(a,1,(n/2));

mergeSort(b,1,n-(n/2));

merge(arr,a,(n/2),b,n-(n/2));

}

}

void main()

{

int n;

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

cout<<"Enter the array:";

int *arr=new int[n];

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

cin>>arr[i];

int start=clock();

mergeSort(arr,1,n);

cout<<"\n\nSorted array:\n";

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

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



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

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

getch();

}