Merge sort program with out class and object:
#include<iostream.h>
#include<conio.h>
void merge(int *,int, int , int );
void merge_sort(int *arr, int p, int r)
{
int q;
if (p < r)
{
//divide the array at mid and sort independently using merge sort
q=(p+r)/2;
cout<<"\n\t First and second array elements:";
for (int i = 0; i < r+1; i++)
cout<<arr[i]<<" ";
merge_sort(arr,p,q);
merge_sort(arr,q+1,r);
//merge or conquer sorted arrays
merge(arr,p,q,r);
cout<<"\n Merged array elements:";
for (int k = 0; k < r+1; k++)
cout<<arr[k]<<" ";
}
}
// Merge sort
void merge(int *arr, int p, int q, int r)
{
int i, j, k, c[50];
i = p;
k = p;
j = q + 1;
while (i <= q && j <= r)
{
if (arr[i] < arr[j])
{
c[k] = arr[i];
k++;
i++;
}
else
{
c[k] = arr[j];
k++;
j++;
}
}
while (i <= q)
{
c[k] = arr[i];
k++;
i++;
}
while (j <= r)
{
c[k] = arr[j];
k++;
j++;
}
for (i = p; i < k; i++)
{
arr[i] = c[i];
}
}
// read input array and call mergesort
void main()
{
int myarray[30], num;
clrscr();
cout<<"Enter number of elements to be sorted:";
cin>>num;
cout<<"Enter "<<num<<" elements to be sorted:";
for ( int i = 0; i < num; i++)
cin>>myarray[i];
merge_sort(myarray, 0, num-1);
cout<<"\n Sorted array:";
for (i = 0; i < num; i++)
cout<<myarray[i]<<" ";
getch();
}
output:
Merge sort program with class and object :
#include<iostream.h>
#include<conio.h>
class mergesort
{
public:
int i,n;
int arr[10];
public:
void getarray();
void partition(int * ,int ,int);
void sortit(int *, int , int, int);
void display();
};
// get the array to be sorted from the user
void mergesort::getarray()
{
cout<<"Enter Array size: ";
cin>>n;
cout<<"unsorted array: ";
for(int i=0;i<n;i++){
cin>>arr[i];
}
}
// recursively divide the array into sub arrays until all sub
// arrays contain only one element
void mergesort::partition(int *arr, int p, int r)
{
int q;
if(p<r)
{
q=(p+r)/2;
cout<<"\n\tfirst and second array element :";
for(i = 0 ; i <r+1; i++)
cout<<arr[i]<<" ";
// sort the left sub array
partition(arr,p,q);
// sort the right sub array
partition(arr,q+1,r);
sortit(arr,p,q,r);
{
cout<<"\nmerged a
rray element :";
for(int k = 0 ; k <r+1; k++ )
cout<<arr[k]<<" ";
}
}
}
void mergesort::sortit(int *arr, int p, int q, int r)
{
int i,j,k,l,b[20];
l=p;
i=p;
j=q+1;
while((l<=q)&&(j<=r))
{
if(arr[l]<=arr[j])
{
b[i]=arr[l];
l++;
}else{
b[i]=arr[j];
j++;
}
i++;
}
if(l>q){
for(k=j;k<=r;k++){
b[i]=arr[k];
i++;
}
}
else
{
for(k=l;k<=r;k++){
b[i]=arr[k];
i++;
}
}
for(k=p;k<=r;k++){
arr[k]=b[k];
}
}
void mergesort::display(){
cout<<"\n The sorted element :";
for(int i = 0 ; i < n; i++){
cout<<arr[i]<<" ";
}
}
void main(){
clrscr();
mergesort ms;
ms.getarray();
ms.partition(ms.arr,0,ms.n-1);
ms.sortit(ms.arr,0,ms.n,ms.n);
ms.display();
getch();
}
Output:
Explanation:
Merge sort animation video link:
https://www.youtube.com/watch?v=4VqmGXwpLqc
No comments:
Post a Comment