IMPLEMENT THE MERGE-SORT ALGORITHM USING C++. The input should be an ASCII file
ID: 3630945 • Letter: I
Question
IMPLEMENT THE MERGE-SORT ALGORITHM USING C++.
The input should be an ASCII file named ‘input.txt’ which contains the unsorted float-point numbers separated by blank space; the output should be an ASCII file named ‘output.txt’ contains the sorted float-point numbers separated by blank space. You also need to output the execution time.
Note: I should be able to input a text file with an arbitrary number of elements.
For example:
[input.txt] has 10 elements
54.6 78.9 45.6 32.9 34.5 12.3 5.6 8.7 37.5 2.3
or another instance
[input.txt] has 5 elements
67.8 4.5 6.9 2.5 7.8
-----------------------------------------------------------------------------
Any help will be great appreciated!
Explanation / Answer
#include <iostream>
#include <iomanip>
#include <fstream>
#include "windows.h"
using namespace std;
int main()
{
//PROTOTYPES
void mergeSort(double *arr, int n);
void selectionSort(double array[], int elems);
//LOCAL DECLARATIONS
fstream fin("input.txt", ios::in);
if (!fin)
{
cout << "Error opening input.txt file. Program aborting. ";
exit(1);
}
fstream fout("output.txt", ios::out);
if (!fout)
{
cout << "Error opening output.txt file. Program aborting. ";
exit(1);
}
double tempBuf;
int count = 0;
double *buf;
//for display time purpose
DWORD tstart;
DWORD tend;
DWORD tdif;
//PROCEDURES
//count how many elements in the file
while (!fin.eof())
{
fin >> tempBuf;
count++;
}
cout << "Count: " << count << endl;
//dynamic allocate double array
buf = new double[count];
//rewind fstream in
fin.clear();
fin.seekg(0);
//fill data to the array and display it
for (int i = 0; i < count; i++)
{
fin >> buf[i];
cout << buf[i] << " ";
}
fin.close();
cout << endl << endl;
//merge sort
tstart = GetTickCount();
mergeSort(buf, count);
tend = GetTickCount();
//display result
for (int i = 0; i < count; ++i)
{
cout << buf[i];
cout << " ";
}
//output to text file
for (int i = 0; i < count; ++i)
{
fout << buf[i];
if (i != count - 1) //to avoid a space at the end of the file
{
fout << " ";
}
}
fout.close();
cout << endl << endl;
//display execution/sort time
tdif = tend - tstart;
cout << "Process time: " << tdif << "ms" << endl;
//free memory
delete [] buf;
cout << endl;
cin.get();
return 0;
}
//---------------------------------------------------------
// FUNCTION DEFINITIONS
//---------------------------------------------------------
void mergeSort(double *arr, int n)
{
void merge(double *a, int p, double *b, int q, double *c, int n);
if(n > 1)
{
// copy the first half to array A
double *A;
A = new double[n/2];
int i;
for(i = 0; i < n/2; i++)
{
A[i] = arr[i];
}
// copy the second half to array B
double *B;
B = new double[n - n/2];
for(int j = 0; i < n; i++, j++)
{
B[j] = arr[i];
}
// sort them separately
mergeSort(A, n/2);
mergeSort(B, n - n/2);
// merge the two sorted arrays
merge(A, n/2, B, n - n/2, arr, n);
delete [] A;
delete [] B;
}
}
//---------------------------------------------------------
void merge(double *a, int p, double *b, int q, double *arr, int n)
{
int i,j,k;
i = j = k = 0;
while(i < p && j < q)
{
arr[k++] = (b[j] > a[i] ? a[i++] : b[j++]);
}
if(i == p)
{
// copy the remaing part in array 2
while(j < q)
{
arr[k++] = b[j++];
}
}
else
{
// copy the remaing part in array 1
while(i < p)
{
arr[k++] = a[i++];
}
}
}
OUTPUT
Count: 20
47.3132 83.4519 11.9167 33.1939 15.5465 97.259 10.3284 22.0297 38.5091 0.3721 97
.9429 86.817 14.7594 88.3793 36.3177 1.6984 5.1297 79.5723 15.7011 35.9598
0.3721 1.6984 5.1297 10.3284 11.9167 14.7594 15.5465 15.7011 22.0297 33.1939 35.
9598 36.3177 38.5091 47.3132 79.5723 83.4519 86.817 88.3793 97.259 97.9429
Process time: 0ms