PROBLEM LINK:
Author: Hari Vege
DIFFICULTY:
Easy
PREREQUISITES:
Merge sort,level order traversal
PROBLEM:
It is to print level order traversal of merge sort tree
EXPLANATION:
Building a tree with index’s of array in merge sort tree and implementing level order on it.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
struct arry{
long int fi;
long int se;
int w;
};
void merge(long int arr[],long int l,long int m,long int r)
{
long int i, j, k;
long int n1 = m - l + 1;
long int n2 = r - m;
/* create temp arrays */
long int L[n1], R[n2];
/* Copy data to temp arrays L[] and R[] */
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
/* Merge the temp arrays back into arr[l..r]*/
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
/* Copy the remaining elements of L[], if there
are any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
/* Copy the remaining elements of R[], if there
are any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
/* l is for left index and r is right index of the
sub-array of arr to be sorted */
void mergeSort(long int arr[],long int l,long int r)
{
if (l < r)
{
// Same as (l+r)/2, but avoids overflow for
// large l and h
int m = l+(r-l)/2;
// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
int main() {
long int i,j,k,l,m,n,u,v,r,in;
cin>>i;
long int b[i],d[i];
struct arry a[2*i-2];
for(k=0;k<i;k++){
cin>>b[k];
d[k]=b[k];
}
// mergeSort(d,0,i-1);
n=i;
in=0;
l=0;
a[0].fi=0;
a[0].se=i;
r=0;
//cout<<i;
while(l<=((2*i)-2)){
float f=(a[l].se-a[l].fi)/2.0;
u=ceil(f);
u+=a[l].fi;
// cout<<l<<" "<<a[l].se<<" "<<a[l].fi<<" "<<u<<endl;
if(a[l].se-a[l].fi!=1){
in=a[l].fi;
n=a[l].se;
//cout<<r<<" ";
r++;
a[r].fi=in;
a[r].se=u;
//cout<<r<<" ";
r++;
a[r].fi=u;
a[r].se=n;
// cout<<r<<"\n";
}
l++;
//cout<<i<<endl;
}
for(v=0;v<=(2*i-2);v++){
cout<<v+1<<" person is given with these numbers :";
for(long int p=a[v].fi;p<a[v].se;p++){
cout<<b[p]<<" ";
}
cout<<endl;
}
cout<<"After Sorting the elements are : ";
mergeSort(b,0,i-1);
for(long int p=0;p<i;p++)
cout<<b[p]<<" ";
}