(adsbygoogle = window.adsbygoogle || []).push({ google_ad_client: "ca-pub-2960223314593660", enable_page_level_ads: true }); C program for Merge sort and Quick Sort - TecGlance

Header Ads

C program for Merge sort and Quick Sort

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
void enterelements(int a[],int size)
{
   int i;
   for(i=1;i<=size;i++)
   {
      printf("\nEnter element%d: ",i);
      scanf("%d",&a[i]);                
   }
}
void merge(int a[],int p,int mid,int r,int size)
{
     int b[size],i,j,k;
     k=0;
     i=p;
     j=mid+1;
     while((i<=mid)&&(j<=r))
     {
        if(a[i]<a[j])
        {
           b[k]=a[i];
           k++;
           i++;          
        }
        else
        {
           b[k]=a[j];
           k++;
           j++;  
        }                    
     }
     while(i<=mid)
     {
        b[k]=a[i];
        k++;
        i++;          
     }
     while(j<=r)
     {
        b[k]=a[j];
        k++;
        j++;        
     }
     for(i=r;i>=p;i--)
     {
        a[i]=b[--k];              
     }
}
void mergesort(int a[],int p,int r,int size)
{
   int  mid;
   if(p<r)
   {
      mid=(int)floor((p+r)/2);
      mergesort(a,p,mid,size);
      mergesort(a,mid+1,r,size);
      merge(a,p,mid,r,size);    
   }  
}
int partition(int a[],int p,int r)
{
   int i,j,pivot,temp;
   pivot=a[p];
   i=p;
   j=r;
   while(1)
   {
      while((a[i]<pivot)&&(a[i]!=pivot))
      {
         i++;
      }
      while((a[j]>pivot)&&(a[j]!=pivot))
      {
         j--;
      }
      if(i<j)
      {
         temp=a[i];
         a[i]=a[j];
         a[j]=temp;    
      }  
      else
      {
         return j;
      }  
   }  
}
void quicksort(int a[],int p,int r)
{
   if(p<r)
   {
      int q;
      q=partition(a,p,r);
      quicksort(a,p,q);
      quicksort(a,q+1,r);    
   }
}
int main()
{
   int a[100],i,j,size,ch;
   printf("\nEnter the size of array: ");
   scanf("%d",&size);
   do
   {
        printf("\n\n..MENU..\n1. Merge Sort\n2. Quick Sort\n3. Exit\n\nEnter your choice: ");
        scanf("%d",&ch);        switch(ch)
        {
            case 1: enterelements(a,size);
                    printf("\nUnsorted elements are: ");
                    i=1;
                    while(i<=size)
                    {
                      printf(" %d",a[i]);
                      i=i+1;          
                    }
                    mergesort(a,1,size,size);
                    printf("\nSorted elements are: ");
                    i=1;
                    while(i<=size)
                    {
                      printf(" %d",a[i]);
                      i=i+1;          
                    }
                    break;
            case 2: enterelements(a,size);
                    printf("\nUnsorted elements are: ");
                    i=1;
                    while(i<=size)
                    {
                      printf(" %d",a[i]);
                      i=i+1;          
                    }  
                    quicksort(a,1,size);
                    printf("\nSorted elements are: ");
                    i=1;
                    while(i<=size)
                    {
                      printf(" %d",a[i]);
                      i=i+1;          
                    }
                    break;
            case 3: exit(0);
            default:printf("\nWrong choice!");
        }
   }while(1);
}

No comments

Powered by Blogger.