//here Im posing different ways of Merge sort programs, you can follow whichever you want
Merge Sort
Merge Sort
What is Merge Sort algorithm? How to implement Merge Sort in C++?
Merge Sort is a divide and conquer algorithm.
In the best/ average/ worst case it gives a time complexity of O(n log n).
Conceptually, a merge sort works as follows:
If the list is of length 0 or 1, then it is already sorted. Otherwise:
Divide the unsorted list into two sublists of about half the size.
Sort each sublist recursively by re-applying the merge sort.
Merge the two sublists back into one sorted list.
Example:
#include <iostream.h>
const int MAX = 5 ;
class array
{
private :
int *a ;
int size ;
int count ;
public :
array( ) ;
array ( int sz ) ;
void add ( int num ) ;
void display( ) ;
void merge_sort(int low,int high);
void merge(int low,int mid,int high);
~array( ) ;
} ;
array :: array( )
{
count = size = 0 ;
a = NULL ;
}
array :: array( int sz )
{
count = 0 ;
size = sz ;
a = new int[sz] ;
}
void array :: add ( int num )
{
if ( count < size )
{
a[count] = num ;
count++ ;
}
else
cout << "\nArray is full" << endl ;
}
void array :: display( )
{
for ( int i = 0 ; i < count ; i++ )
cout << a[i] << "\t" ;
cout << endl ;
}
void array :: merge_sort(int low,int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
merge_sort(low,mid);
merge_sort(mid+1,high);
merge(low,mid,high);
}
}
void array :: merge(int low,int mid,int high)
{
int h,i,j,b[50],k;
h=low;
i=low;
j=mid+1;
while((h<=mid)&&(j<=high))
{
if(a[h]<=a[j])
{
b[i]=a[h];
h++;
}
else
{
b[i]=a[j];
j++;
}
i++;
}
if(h>mid)
{
for(k=j;k<=high;k++)
{
b[i]=a[k];
i++;
}
}
else
{
for(k=h;k<=mid;k++)
{
b[i]=a[k];
i++;
}
}
for(k=low;k<=high;k++) a[k]=b[k];
}
array :: ~array( )
{
delete a ;
}
void main( )
{
array a ( MAX ) ;
a.add ( 11 ) ;
a.add ( 2 ) ;
a.add ( 9 ) ;
a.add ( 13 ) ;
a.add ( 57 ) ;
cout << "\nMerge sort.\n" ;
a.merge_sort (0,4) ;
cout << "\nArray after sorting: " << endl ;
a.display( ) ;
}
Example 2: without using classes
#include <iostream>using namespace std;void merge(int*,int*,int,int,int);void mergesort(int *a, int*b, int low, int high){ int pivot; if(low<high) { pivot=(low+high)/2; mergesort(a,b,low,pivot); mergesort(a,b,pivot+1,high); merge(a,b,low,pivot,high); }}void merge(int *a, int *b, int low, int pivot, int high){ int h,i,j,k; h=low; i=low; j=pivot+1; while((h<=pivot)&&(j<=high)) { if(a[h]<=a[j]) { b[i]=a[h]; h++; } else { b[i]=a[j]; j++; } i++; } if(h>pivot) { for(k=j; k<=high; k++) { b[i]=a[k]; i++; } } else { for(k=h; k<=pivot; k++) { b[i]=a[k]; i++; } } for(k=low; k<=high; k++) a[k]=b[k];}int main(){ int a[] = {12,10,43,23,-78,45,123,56,98,41,90,24}; int num; num = sizeof(a)/sizeof(int); int b[num]; mergesort(a,b,0,num-1); for(int i=0; i<num; i++) cout<<a[i]<<" "; cout<<endl;}/*Non recursive method
*/
/*********************************************************
-> This C++ program is to perform Merge sort
using iterative method.
using iterative method.
-> This program works in microsoft vc++ 6.0 environment.
-> The numbers are sorted in increasing order.
**********************************************************/
#include<iostream.h>
class sorting
{
private:
double *array;
int n;
public:
void input();
void output();
void mergesort();
};
class sorting
{
private:
double *array;
int n;
public:
void input();
void output();
void mergesort();
};
void sorting::input()
{
cout<<”****************************************************\n”
<<”This program sorts numbers in increasing order”
<<”\n\t\tusing Merge sort iterative technique\n”
<<”****************************************************\n”;
{
cout<<”****************************************************\n”
<<”This program sorts numbers in increasing order”
<<”\n\t\tusing Merge sort iterative technique\n”
<<”****************************************************\n”;
cout<<”Enter how many numbers you are going to enter for sorting ::”;
cin>>n;
array=new double[n];
cout<<”Now enter your elements ::\n”;
for(int i=0;i<n;i++)
cin>>array[i];
}
cin>>n;
array=new double[n];
cout<<”Now enter your elements ::\n”;
for(int i=0;i<n;i++)
cin>>array[i];
}
void sorting::mergesort()
{
double *temp=new double[n];
int l1,l2,u1,u2,i;
int size=1,j,k;
while(size<n)
{
l1=0;
k=0;
while(l1+size<n)
{
l2=l1+size;
u1=l2-1;
u2=(l2+size-1<n)?l2+size-1:n-1;
for(i=l1,j=l2;i<=u1&&j<=u2;k++)
if(array[i]<=array[j])
temp[k]=array[i++];
else
temp[k]=array[j++];
for(;i<=u1;k++)
temp[k]=array[i++];
for(;j<=u2;k++)
temp[k]=array[j++];
l1=u2+1;
}
for(i=l1;k<n;i++)
temp[k++]=array[i];
for(i=0;i<n;i++)
array[i]=temp[i];
{
double *temp=new double[n];
int l1,l2,u1,u2,i;
int size=1,j,k;
while(size<n)
{
l1=0;
k=0;
while(l1+size<n)
{
l2=l1+size;
u1=l2-1;
u2=(l2+size-1<n)?l2+size-1:n-1;
for(i=l1,j=l2;i<=u1&&j<=u2;k++)
if(array[i]<=array[j])
temp[k]=array[i++];
else
temp[k]=array[j++];
for(;i<=u1;k++)
temp[k]=array[i++];
for(;j<=u2;k++)
temp[k]=array[j++];
l1=u2+1;
}
for(i=l1;k<n;i++)
temp[k++]=array[i];
for(i=0;i<n;i++)
array[i]=temp[i];
size*=2;
}
}
}
}
void sorting::output()
{
cout<<”Now the sorted numbers are ::\n”;
for(int i=0;i<n;i++)
cout<<array[i]<<’\t’;
cout<<endl;
}
{
cout<<”Now the sorted numbers are ::\n”;
for(int i=0;i<n;i++)
cout<<array[i]<<’\t’;
cout<<endl;
}
int main()
{
sorting obj;
obj.input();
obj.mergesort();
obj.output();
return 0;
}
/**********************************************************************
{
sorting obj;
obj.input();
obj.mergesort();
obj.output();
return 0;
}
/**********************************************************************
****************************************************
This program sorts numbers in increasing order
using Merge sort iterative technique
****************************************************
Enter how many numbers you are going to enter for sorting ::7
Now enter your elements ::
1.7
1.6
1.5
1.4
1.3
1.2
1.1
Now the sorted numbers are ::
1.1 1.2 1.3 1.4 1.5 1.6 1.7
Press any key to continue
This program sorts numbers in increasing order
using Merge sort iterative technique
****************************************************
Enter how many numbers you are going to enter for sorting ::7
Now enter your elements ::
1.7
1.6
1.5
1.4
1.3
1.2
1.1
Now the sorted numbers are ::
1.1 1.2 1.3 1.4 1.5 1.6 1.7
Press any key to continue
************************************************************************/
//example 3:
//merge sort using classes
#include<iostream.h>
#include<conio.h>
#include<process.h>
class array
{
private:
int *a;
public:
int n;
void create();
void display();
void merge_sort(int low,int high);
void merge(int low,int mid,int high);
};
void array::create()
{
cout<<"how many no's\n";
cin>>n;
a=new int[n];
cout<<"enter elements \n";
for(int i=0;i<=n-1;i++)
cin>>a[i];
}
void array::display()
{
cout<<"sorted no's \n";
for(int i=0;i<=n-1;i++)
cout<<a[i]<<"\n";
}
void array::merge_sort(int low, int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
merge_sort(low,mid);
merge_sort(mid+1,high);
merge(low,mid,high);
}
}
void array::merge(int low,int mid,int high)
{
int h,i,j,b[20],k;
h=low;
i=low;
j=mid+1;
while((h<=mid)&&(j<=high))
{
if(a[h]<=a[j])
{
b[i]=a[h];
h++;
}
else
{
b[i]=a[j];
j++;
}
i++;
}
if(h>mid)
{
for(k=j;k<=high;k++)
{
b[i]=a[k];
i++;
}//for
}//if
else
{
for(k=h;k<=mid;k++)
{
b[i]=a[k];
i++;
}
}
for(k=low;k<=high;k++)
a[k]=b[k];
}//merge()
void main()
{
array obj;
obj.create();
obj.merge_sort(0,obj.n-1);
obj.display();
getch();
}
/*
how many no's
9
enter elements
8
6
12
7
4
13
2
1
3
sorted no's
1
2
3
4
6
7
8
12
13
*/
//merge sort using classes
#include<iostream.h>
#include<conio.h>
#include<process.h>
class array
{
private:
int *a;
public:
int n;
void create();
void display();
void merge_sort(int low,int high);
void merge(int low,int mid,int high);
};
void array::create()
{
cout<<"how many no's\n";
cin>>n;
a=new int[n];
cout<<"enter elements \n";
for(int i=0;i<=n-1;i++)
cin>>a[i];
}
void array::display()
{
cout<<"sorted no's \n";
for(int i=0;i<=n-1;i++)
cout<<a[i]<<"\n";
}
void array::merge_sort(int low, int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
merge_sort(low,mid);
merge_sort(mid+1,high);
merge(low,mid,high);
}
}
void array::merge(int low,int mid,int high)
{
int h,i,j,b[20],k;
h=low;
i=low;
j=mid+1;
while((h<=mid)&&(j<=high))
{
if(a[h]<=a[j])
{
b[i]=a[h];
h++;
}
else
{
b[i]=a[j];
j++;
}
i++;
}
if(h>mid)
{
for(k=j;k<=high;k++)
{
b[i]=a[k];
i++;
}//for
}//if
else
{
for(k=h;k<=mid;k++)
{
b[i]=a[k];
i++;
}
}
for(k=low;k<=high;k++)
a[k]=b[k];
}//merge()
void main()
{
array obj;
obj.create();
obj.merge_sort(0,obj.n-1);
obj.display();
getch();
}
/*
how many no's
9
enter elements
8
6
12
7
4
13
2
1
3
sorted no's
1
2
3
4
6
7
8
12
13
*/
No comments:
Post a Comment