Tuesday 3 November 2015

CPP program for merge sort - Data Structures

#include<iostream>           // Ref note
using namespace std;
int k[30];
void merge(int low,int mid,int high)
{
int i=low,j=mid+1,h=low;
int temp[30];           //temp is to contain the result(we may just print out inorder to avoid temp)
while(i<=mid && j<=high)         //i is for first half and j is for second half
{
   if(k[i]<=k[j])      // if first half element is lesser than second half
     {
        temp[h]=k[i];  
        i++;          
      }
    else
     {
      temp[h]=k[j];
       j++;          // increase corresponding iterative variable
     }
  h++;              // h is temp index
}
if(i>mid)          // if all first half elements are sorted and copied
{
   while(j<=high)  // copy the remaining elements from second half
    {
      temp[h]=k[j];
       j++;
       h++;
    }
}
else            // if all second half elements are copied and sorted
{
   while(i<=mid)  // copy the remaining elements of first half
   {
     temp[h]=k[i];
      i++;
      h++;
   }
}
i=low;
while(i<=high)  // just copying
{
k[i]=temp[i];
i++;
}


}

void mergesort(int low,int high)//this function splits the array into two until reaches single element and then merge
{
int mid;
if(low<high)
{
mid=(low+high)/2;
mergesort(low,mid);         //first half
mergesort(mid+1,high);      //second half
merge(low,mid,high);        //sort and merge the two halves
}
}


int main()
{
int n,i;
cout<<"\nEnter no of elements:";cin>>n;
cout<<"\nEnter the elements:";
for(i=1;i<=n;i++)
cin>>k[i];
mergesort(1,n);
cout<<"\nAfter sorting:";
for(i=1;i<=n;i++)
cout<<k[i]<<"\t";
return 0;
}

No comments:

Post a Comment