C++ Merge Sort PLEASE USE DATA FILE FOR USER INPUT - NO USER INPUT Data in file

Question

C++ Merge Sort

PLEASE USE DATA FILE FOR USER INPUT - NO USER INPUT

Data in file called A4.txt

1. Write a program that will read each line from A4.txt and store the numbers into an array. 2. Sort the number of that array using Merge sort algorithm (using recursion). 3. Show the output in file B4.txt. Note: In total there will be 15 lines in B4.txt, where each line will contain a sorted array. First two lines are given as sample. WO 1 Sample input: 2 41 53 97 67 62 82 93 54 34 11 62 29 16 96 61 95 25 62 75 90 18 51 41 54 94 7 96 5 17 95 s Sample output 6 11 16 29 34 41 53 54 61 62 62 67 82 93 96 97 7 5 7 17 18 25 41 51 54 62 75 90 94 95 95 96

Explanation / Answer

/**** c++ code to sort numbers using mergesort and store them in a file ***********/

#include <fstream>
#include <iostream>
#include <sstream>
#include <vector>

using namespace std;

void merge(vector<int> &arr , int l, int m, int r);

/* l is for left index and r is right index of the sub-array
of arr to be sorted */
void mergeSort(vector<int> &arr, int l, int r)
{
if (l < r)
{
int m = l+(r-l)/2; //Same as (l+r)/2 but avoids overflow for large l & h
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}

/* Function to merge the two haves arr[l..m] and arr[m+1..r] of array arr[] */
void merge(vector<int> &arr, int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;

/* create temp arrays */
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;
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++;
}

/* 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++;
}
}

int main() {
  
  
ifstream inFile("A4.txt");
if (!inFile) {
cerr << "File A4.txt not found." << endl;
return -1;
}

ofstream outFile("B4.txt");

// Using getline() to read one line at a time.
string line;
while (getline(inFile, line)) // reading one line at a time
{
vector<int> v; // vector to store integers in each line and sort them
if (line.empty()) continue;

// Using istringstream to read the line into integers.
istringstream iss(line);
int sum = 0, next = 0;
while (iss >> next)
{
v.push_back(next);
}

mergeSort(v,0,v.size()-1); // calling mergesort
  
for (int i = 0; i < v.size(); ++i)
{
outFile << v[i] <<" ";
}
outFile<< " ";
}

inFile.close();
outFile.close();
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.