All rights are reserved by Niteesh Kumar.. Theme images by Storman. Powered by Blogger.

Followers

Total Pageviews

Blog Archive

Follow by Email

Translate

Wednesday, 28 December 2016

Program to implement Merge sort and also draw it's plot.

OBJECTIVE-Write a program to implement Merge sort and also draw it's plot.
 

ALGORITHM-
MergeSort(arr[], l,  r)
If r > l
     1. Find the middle point to divide the array into two halves: 
             middle m = (l+r)/2
     2. Call mergeSort for first half:  
             mergeSort(arr, l, m)
     3. Call mergeSort for second half:
              mergeSort(arr, m+1, r)
     4. Merge the two halves sorted in step 2 and 3:
              merge(arr, l, m, r) 



To draw the plot we need to know the execution time for every single input size so for that purpose we are using clock() function here which will give us time after each execution.

CLOCKS_PER_SEC is used to convert time in seconds.



#include<stdio.h>
#include<stdlib.h>
#include<time.h>
void merge(long int a[],long int l,long int m,long int r)
{
    long int i,j,k;
    long int n1=m-l+1;
    long int n2=r-m;
    long int la[n1],ra[n2];
    for(i=0;i<n1;i++)
    la[i]=a[l+i];
    for(j=0;j<n2;j++)
    ra[j]=a[m+1+j];
    i=0;j=0;k=l;
    while(i<n1 && j<n2)
    {
        if(la[i]<=ra[j])
        {
            a[k]=la[i];
            i++;
            k++;
        }
        else
        {
            a[k]=ra[j];
            j++;
            k++;
        }
    }
    while(i<n1)
    {
        a[k]=la[i];
        i++;
        k++;
    }
    while(j<n2)
    {
            a[k]=ra[j];
            j++;
            k++;
    }
}
void mergesort(long int a[],long int l,long int r)
{
    if(l<r)
    {
        int m=l+(r-l)/2;
        mergesort(a,l,m);
        mergesort(a,m+1,r);
        merge(a,l,m,r);
    }
}
int main()
{
    double start,end,total;
    start=clock();
    long int i,a[1000000];
    long int n;
    printf("Enter number of inputs:");
    scanf("%ld",&n);
    for(i=0;i<n;i++)
    // we are generating random inputs here    you can also use scanf or cin here to take manual input.
    a[i]=rand()%1000000;
    mergesort(a,0,n-1);
    printf("sorted array\n");
    for(i=0;i<n;i++)
    printf("%ld\t",a[i]);
    printf("\n");
    end=clock();
    total=(double)(end-start)/CLOCKS_PER_SEC;
    printf("Time taken=%lf\n",total);
return 0;
}


// run the code in your compiler to see the output. 

0 on: "Program to implement Merge sort and also draw it's plot."