Description:
Merge sort is
based on the divide-and-conquer paradigm. Its worst-case running time has a lower order of
growth than insertion sort. Since we are dealing with subproblems, we state
each subproblem as sorting a subarray A[p .. r]. Initially, p = 1 and r = n, but these values change as we recurse through
subproblems.
Algorithm
To sort A[p .. r]:
1. Divide Step
If a given array A has zero or one element,
simply return; it is already sorted. Otherwise, split A[p .. r] into two subarrays A[p .. q] and A[q + 1 .. r],
each containing about half of the elements of A[p .. r]. That is, q is the halfway point of A[p .. r].
2. Conquer Step
Conquer by recursively sorting the two subarrays A[p .. q] and A[q + 1 .. r].
3. Combine Step
Combine the elements back in A[p .. r] by merging the two sorted subarrays A[p .. q] and A[q + 1 .. r] into
a sorted sequence. To accomplish this step, we will define a procedure MERGE (A, p, q, r).
Note that the
recursion bottoms out when the subarray has just one element, so that it is
trivially sorted.
Solution:
#include<stdio.h>
#include<omp.h>
#include<stdlib.h>
void mergesort(int
a[],int n);
void merge(int
a[],int b[],int
c[],int,int);
void main()
{
int
n,i,a[1000],choice,num;
double start_time,end_time;
FILE *fp;
char
f_name[10];
label:printf("\nEnter
your choice :\nPress 1 to read numbers from file\nPress 2 to generate random
numbers\nPress 3 to take numbers from keyboard \nPress 4 to exit");
scanf("%d",&choice);
switch(choice)
{
case
1:printf("Enter the filename:");
fflush(stdin);
gets(f_name);
fp=fopen(f_name,"r");
if(fp==NULL)
{
printf("Error!!
File not found");
goto
label;
}
i=0;
while(fscanf(fp,"%d",&num)!=EOF)
{
a[i]=num;
i++;
}
n=i;
break;
case
2:printf("Enter the number of elements\n");
scanf("%d",&n);
for(i=0;i<n;i++)
{
a[i]=rand()%100;
}
break;
case
3: printf("Enter the number of elements\n");
scanf("%d",&n);
printf("\nEnter %d elements:",n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
break;
default:exit(0);
}
printf("\nThe
unsorted array is:");
for(i=0;i<n;i++)
printf("\t%d",a[i]);
omp_set_num_threads(5);
start_time=omp_get_wtime();
mergesort(a,n);
end_time=omp_get_wtime();
printf("\n The sorted array is :");
for(i=0;i<n;i++)
printf("\t%d",a[i]);
printf("\nTime
taken=%.2f\n",end_time-start_time);
}
void mergesort(int
a[],int n)
{
int
b[1000],c[1000],i,j=0;
if(n>1)
{
for(i=0;i<n/2;i++)
b[i]=a[i];
for(i=n/2;i<n;i++)
{
c[j]=a[i];
j++;
}
#pragma
omp parallel
mergesort(b,n/2);
#pragma
omp parallel
mergesort(c,j);
#pragma
omp parallel
merge(b,c,a,n/2,j);
}
}
void merge(int
b[],int c[],int
a[],int p,int
q)
{
int
i=0,j=0,k=0,x;
while((i<p)&&(j<q))
{
if(b[i]<=c[j])
a[k++]=b[i++];
else
a[k++]=c[j++];
}
if(i==p)
{
#pragma
omp parallel for
for(x=j;x<q;x++)
a[k++]=c[x];
}
else
{
#pragma
omp parallel for
for(x=i;x<p;x++)
a[k++]=b[x];
}
}
OUTPUT 1 :
Enter your choice :
Press 1 to read numbers from file
Press 2 to generate random numbers
Press 3 to take numbers from keyboard
Press 4 to exit
2
Enter the number of elements
100
The unsorted array is: 83 86 77 15 93 35 86 92 49 21 62 27 90 59 63 26 40 26 72 36 11 68 67 29 82 30 62 23 67 35 29 2 22 58 69 67 93 56 11 42 29 73 21 19 84 37 98 24 15 70 13 26 91 80 56 73 62 70 96 81 5 25 84 27 36 5 46 29 13 57 24 95 82 45 14 67 34 64 43 50 87 8 76 78 88 84 3 51 54 99 32 60 76 68 39 12 26 86 94 39
The sorted array is : 2 3 5 5 8 11 11 12 13 13 14 15 15 19 21 21 22 23 24 24 25 26 26 26 26 27 27 29 29 29 29 30 32 34 35 35 36 36 37 39 39 40 42 43 45 46 49 50 51 54 56 56 57 58 59 60 62 62 62 63 64 67 67 67 67 68 68 69 70 70 72 73 73 76 76 77 78 80 81 82 82 83 84 84 84 86 86 86 87 88 90 91 92 93 93 94 95 96 98 99
Time taken=0.00
Parallel implementation is taking longer time than serial implementation.
ReplyDelete