recent

Merge sort and quick sort Algorithm analysis and design

Sort a given set of elements using the Quick sort method and determine the time required to sort the elements.
Repeat the experiment for different values of n, the number of elements in the list to be sorted and plot a graph of the time taken versus n.

implement a parallelized Merge Sort algorithm to sort a given set of elements and determine the time required to sort the elements.
Repeat the experiment for different values of n, the number of elements in the list to be sorted and plot a graph of the time taken versus
The elements can be read from a file or randomly.
using both Recursive and iterative approch.


Header.h
void merge(int *a,int low,int mid,int high);
void merge_sort(int *a,int low,int high);
int partition(int *a,int p,int r);
void quick_sort(int *a,int p,int r);
int partition1(int *a,int p,int r);
void q_iter(int *a,int p,int r);


Main.c 
#include<stdio.h>
#include<stdlib.h>
#include<sys/time.h>
#include "header.h"

void main()
{
    int i,n;
    int *a,*b,*c,*d;
    struct timeval tim;
    double time_start,time_end;
    printf("\nEnter n:");
    scanf("%d",&n);
    a=(int *)malloc(n*sizeof(int));
    b=(int *)malloc(n*sizeof(int));
    c=(int *)malloc(n*sizeof(int));
    d=(int *)malloc(n*sizeof(int));
    for(i=0;i<n;i++)
    {
        a[i]=rand()%100;
    }   
   
    for(i=0;i<n;i++)
    {
        b[i]=a[i];
        c[i]=a[i];
        d[i]=a[i];
    }
   
    printf("\nBefore merge_rec sorting:\n");
    for(i=0;i<n;i++)
    {
        printf("%d\n",b[i]);
    }
   
    gettimeofday(&tim,NULL);
    time_start=(double)tim.tv_sec + (double)(tim.tv_usec/1000000.0);
    merge_sort(b,0,n-1);
    gettimeofday(&tim,NULL);
    time_end=(double)tim.tv_sec+(double)(tim.tv_usec/100000.0);
   
    printf("\nAfter merge_rec sorting:\n");
    for(i=0;i<n;i++)
    {
        printf("%d\n",b[i]);
    }
   
    printf("Execution time :%1f",time_end-time_start);
    printf("\n");
   
    printf("\nBefore quick_rec sorting:\n");
    for(i=0;i<n;i++)
    {
        printf("%d\n",c[i]);
    }
   
    gettimeofday(&tim,NULL);
    time_start=(double)tim.tv_sec + (double)(tim.tv_usec/1000000.0);
    quick_sort(c,0,n-1);
    gettimeofday(&tim,NULL);
    time_end=(double)tim.tv_sec+(double)(tim.tv_usec/100000.0);
   
    printf("\nAfter quick_rec sorting:\n");
    for(i=0;i<n;i++)
    {
        printf("%d\n",c[i]);
    }
   
    printf("Execution time :%1f",time_end-time_start);
    printf("\n");
 
    printf("\nBefore qucik_itr sorting:\n");
    for(i=0;i<n;i++)
    {
        printf("%d\n",d[i]);
    }
   
    gettimeofday(&tim,NULL);
    time_start=(double)tim.tv_sec + (double)(tim.tv_usec/1000000.0);
    q_iter(d,0,n-1);
    gettimeofday(&tim,NULL);
    time_end=(double)tim.tv_sec+(double)(tim.tv_usec/100000.0);
   
    printf("\nAfter quick_itr sorting:\n");
    for(i=0;i<n;i++)
    {
        printf("%d\n",d[i]);
    }
   
    printf("Execution time :%1f",time_end-time_start);
    printf("\n");
}




 m_itr.c
 void merge_itr(int *a,int low,int high)
{
    int i,j;
    while()
}




 merge2.c
void merge(int *a,int n){
    int aux[n];
    int i,j,k,lower1,lower2,upper1,upper2,size=1;
    while(size<n){
        k=0,lower1=0;
          while((lower1+size)<n){
               lower2=lower1+size;
            upper1=lower2-1;
            upper2=(lower2+size-1<n)?(lower2+size-1):(n-1);
            for(i=lower1,j=lower2;i<=upper1&&j<=upper2;k++){
                if(a[i]<=a[j])
                    aux[k]=a[i++];
                else
                    aux[k]=a[j++];
            }
            for(;i<=upper1;k++)
                aux[k]=a[i++];
            for(;j<=upper2;k++)
                aux[k]=a[j++];
            lower1=upper2+1;
        }
          
            for(i=0;i<n;i++)
                a[i]=aux[i];
            size=size*2;
    }  
         
}




merge_sort.c
void merge(int *a,int low,int mid,int high)
{
    int i,j,k,n;
    int *b;
    n=high-low+1;
    i=low;
    j=mid+1;
    k=low;
    b=(int *)malloc(n*sizeof(int));
    while(i<=mid && j<=high)
    {
        if(a[i]<a[j])
        {
            b[k]=a[i];
            i++;
            k++;
        }
        else if(a[i]>a[j])
        {
            b[k]=a[j];
            j++;
            k++;
        }
        else
        {
            b[k]=a[i];
            k++;
            i++;
            b[k]=a[j];
            k++;
            j++;
        }
    }
    while(i<=mid)
    {
        b[k]=a[i];
        i++;
        k++;
    }
    while(j<=high)
    {
        b[k]=a[j];
        j++;
        k++;
    }
    k=low;
    while(k<=high)
    {
        a[k]=b[k];
        k++;
    }
}

void merge_sort(int *a,int low,int high)
{
    int mid;
    mid=(low+high)/2;
    if(low<high)
    {
        merge_sort(a,low,mid);
        merge_sort(a,mid+1,high);
        merge(a,low,mid,high);
    }
}




 qiter.c
int partition1(int *a,int p,int r)
{
    int i,j,x,temp;
    x=a[r];
    i=p-1;
    for(j=p;j<r;j++)
    {
        if(a[j]<=x)
        {
            i=i+1;
            temp=a[i];
            a[i]=a[j];
            a[j]=temp;
        }
    }
    temp=a[r];
    a[r]=a[i+1];
    a[i+1]=temp;
    return i+1;
}

void q_iter(int *a,int p,int r)
{
    int i,j,q,n,top;
    n=r-p+1;
    top=-1;
    int *stack;
    stack=(int *)malloc(n*sizeof(int));
    stack[++top]=p;
    stack[++top]=r;
    while(top>=0)
    {
        r=stack[top--];
        p=stack[top--];
        q=partition1(a,p,r);
        if(p<q-1)
        {
            stack[++top]=p;
            stack[++top]=q-1;
        }
        if(q+1<r)
        {
            stack[++top]=q+1;
            stack[++top]=r;
        }
    }
}




 quick_sort.c
int partition(int *a,int p,int r)
{
    int i,j,x,temp;
    x=a[r];
    i=p-1;
    for(j=p;j<r;j++)
    {
        if(a[j]<=x)
        {
            i=i+1;
            temp=a[i];
            a[i]=a[j];
            a[j]=temp;
        }
    }
    temp=a[r];
    a[r]=a[i+1];
    a[i+1]=temp;
    return i+1;
}

void quick_sort(int *a,int p,int r)
{
    int q;
    if(p<r)
    {
        q=partition(a,p,r);
        quick_sort(a,p,q-1);
        quick_sort(a,q+1,r);
    }
}




Total.c
#include<stdio.h>
#include<stdlib.h>

void merge(int *a,int low,int mid,int high)
{
    int i,j,k,n;
    int *b;
    n=high-low+1;
    i=low;
    j=mid+1;
    k=low;
    b=(int *)malloc(n*sizeof(int));
    while(i<=mid && j<=high)
    {
        if(a[i]<a[j])
        {
            b[k]=a[i];
            i++;
            k++;
        }
        else if(a[i]>a[j])
        {
            b[k]=a[j];
            j++;
            k++;
        }
        else
        {
            b[k]=a[i];
            k++;
            i++;
            b[k]=a[j];
            k++;
            j++;
        }
    }
    while(i<=mid)
    {
        b[k]=a[i];
        i++;
        k++;
    }
    while(j<=high)
    {
        b[k]=a[j];
        j++;
        k++;
    }
    k=low;
    while(k<=high)
    {
        a[k]=b[k];
        k++;
    }
}

void merge_sort(int *a,int low,int high)
{
    int mid;
    mid=(low+high)/2;
    if(low<high)
    {
        merge_sort(a,low,mid);
        merge_sort(a,mid+1,high);
        merge(a,low,mid,high);
    }
}

void main()
{
    int *a;
    int i,n;
    printf("\nEnter n:");
    scanf("%d",&n);
    a=(int *)malloc(n*sizeof(int));
    for(i=0;i<n;i++)
    {
        a[i]=rand()%100;
    }
    printf("\nBefore sorting:\n");
    for(i=0;i<n;i++)
    {
        printf("%d\n",a[i]);
    }
    merge_sort(a,0,n-1);
    printf("\nAfter sorting:\n");
    for(i=0;i<n;i++)
    {
        printf("%d\n",a[i]);
    }
}

#include<stdio.h>
#include<stdlib.h>

int partition(int *a,int p,int r)
{
    int i,j,x,temp;
    x=a[r];
    i=p-1;
    for(j=p;j<r;j++)
    {
        if(a[j]<=x)
        {
            i=i+1;
            temp=a[i];
            a[i]=a[j];
            a[j]=temp;
        }
    }
    temp=a[r];
    a[r]=a[i+1];
    a[i+1]=temp;
    return i+1;
}

void quick_sort(int *a,int p,int r)
{
    int q;
    if(p<r)
    {
        q=partition(a,p,r);
        quick_sort(a,p,q-1);
        quick_sort(a,q+1,r);
    }
}

void main()
{
    int i,n;
    int *a;
    printf("\nEnter n:");
    scanf("%d",&n);
    a=(int *)malloc(n*sizeof(int));
    for(i=0;i<n;i++)
    {
        a[i]=rand()%100;
    }
    printf("\nBefore sorting:\n");
    for(i=0;i<n;i++)
    {
        printf("%d\n",a[i]);
    }
    quick_sort(a,0,n-1);
    printf("\nAfter sorting:\n");
    for(i=0;i<n;i++)
    {
        printf("%d\n",a[i]);
    }
}

#include<stdio.h>
#include<stdlib.h>

int partition(int *a,int p,int r)
{
    int i,j,x,temp;
    x=a[r];
    i=p-1;
    for(j=p;j<r;j++)
    {
        if(a[j]<=x)
        {
            i=i+1;
            temp=a[i];
            a[i]=a[j];
            a[j]=temp;
        }
    }
    temp=a[r];
    a[r]=a[i+1];
    a[i+1]=temp;
    return i+1;
}

void q_iter(int *a,int p,int r)
{
    int i,j,q,n,top;
    n=r-p+1;
    top=-1;
    int *stack;
    stack=(int *)malloc(n*sizeof(int));
    stack[++top]=p;
    stack[++top]=r;
    while(top>=0)
    {
        r=stack[top--];
        p=stack[top--];
        q=partition(a,p,r);
        if(p<q-1)
        {
            stack[++top]=p;
            stack[++top]=q-1;
        }
        if(q+1<r)
        {
            stack[++top]=q+1;
            stack[++top]=r;
        }
    }
}

void main()
{
    int i,n;
    int *a;
    printf("\nEnter n:");
    scanf("%d",&n);
    a=(int *)malloc(n*sizeof(int));
    for(i=0;i<n;i++)
    {
        a[i]=rand()%100;
    }
    printf("\nBefore sorting:\n");
    for(i=0;i<n;i++)
    {
        printf("%d\n",a[i]);
    }
    q_iter(a,0,n-1);
    printf("\nAfter sorting:\n");
    for(i=0;i<n;i++)
    {
        printf("%d\n",a[i]);
    }




OUTPUT
n=10
Execution time of merge_rec sort:0.000002
Execution time of quick_rec sort:0.000001
Execution time of quick_itr sort:0.000001


n=100
Execution time of merge_rec sort:0.000027
Execution time of quick_rec sort:0.000013
Execution time of quick_itr sort:0.000012


n=1000
Execution time of merge_rec sort:0.000340
Execution time of quick_rec sort:0.000182
Execution time of quick_itr sort:0.000149


 
Powered by Blogger.