#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;
}
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