in C++, elements are read in from a text file. first term sets array size. Merge
ID: 3748697 • Letter: I
Question
in C++, elements are read in from a text file. first term sets array size.
MergeSort Description Implement the mergesort algorithm for sorting an array of integers. Input structure Each case starts with an integer number which indicates the number of elements to be sorted. Then, the elements follow, one per line. You can assume the input is correctly structured (i.e., no data are missing. Output structure Output the sorted sequence separeted by";" (in non-decreasing order). Do not insert spaces or a new line at the beginning or at the end of any elementExplanation / Answer
If you have any doubts, please give me comment...
#include<iostream>
#include<fstream>
using namespace std;
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arr[], int l, int r)
{
if (l < r)
{
int m = l+(r-l)/2;
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
int main(){
char file[100];
cout<<"Enter input filename: ";
cin>>file;
ifstream in;
in.open(file);
if(in.fail()){
cout<<"Unable to open input file"<<endl;
return 0;
}
while(!in.eof()){
int n;
in>>n;
int *arr = new int[n];
for(int i=0; i<n; i++)
in>>arr[i];
mergeSort(arr, 0, n-1);
for(int i=0; i<n; i++){
cout<<arr[i];
if(i!=n-1)
cout<<",";
}
}
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.