Merge Sort

[ltrane2003]

My directions are to create a program that will read two files containing a sorted number of integers and merge them into one with all the integers sorted in descending order. I am having a problem with the algorithm that does the sorting.

#include <iostream>
#include <fstream>
#include <cstdlib>
using namespace std;

int main(){
	char in_file_name[16], in_file_name2[16], out_file_name[16];
	ifstream fin, fin2;
	ofstream fout;
	cout<< "Enter two input file names (max 15 characters)\n";
	cin>> in_file_name>>in_file_name2;
	cout<< "enter one output file name (max 15 characters)\n";
	cin>> out_file_name;
	
	fin.open(in_file_name);
	if(fin.fail()){
	cout<<"Input file 1 opening failed!\n";
	exit(1);
	}
	
	fin2.open(in_file_name2);
	if(fin2.fail()){
	cout<<"Input file 2 opening failed!\n";
	exit(1);
	}
	
	fout.open(out_file_name);
	if(fout.fail()){
	cout<<"Output file opening failed!\n";
	exit(1);
	}
		int next;
		while(fin>>next){
		
		while(fin2>>next){
			
		int temp;
		for(int i = 0; i < next; i++){
        			 
                 for(int j = 0;j < next - 1; j++){
                			
                       if(j>j+1){
		        temp = j;
                       j = j+1;
                        j+1 = temp;
		}
	      }	
	    }
	  }	
	}
        fout<<next;
	fin.close();
	fin2.close();
	fout.close();		
		
	 return 0;
}

[jsmith]

Lines 33 and 35 both read into variable "next", so one must overwrite the other.

[ltrane2003]

I there another way to make the program read all of both files?

[ltrane2003]

I am just stuck with this thing. I cannot find any references for this type of program without it having something about an array. I am guessing you would use merge sort here but I am not sure of how to get the two files into one while sorting the integers in descending order.

[Gumbercules]

I made some quick but not polished or tested code to serve as an example. And the files probably were text files, not binary as mine assumes. Notice how it works, it looks at numbers from each lists, compares them, then puts the higher one into the new file. It then looks at the next number of the file where the number was taken, and compares that with the other number. This repeats till one file is empty, then it fills it with what's left of the other file.

#include <iostream>
#include <fstream>
using namespace std;
int main() {
	ifstream file1("1.dat", ios::binary), file1("2.dat", ios::binary);
	ofstream out("merged.dat", ios::binary);
	int int1, int2;
	file1 >> int1;
	file2 >> int2;
	while (true) {
		if (!file1.good()) { // file one is empty, just fill with file 2
			while (true) {
				file2.read((char*) &int2, sizeof(int));
				if (file2.good())
					out.write((char*) &int2, sizeof(int));
				else {
                                        file1.close();
                                        file2.close();
                                        out.close();
					exit(0);
                                }
			}
		} else if(!file2.good()) {
			while (true) {
				file1.read((char*) &int1, sizeof(int));
				if (file1.good())
					out.write((char*) &int1, sizeof(int));
				else {
                                        file1.close();
                                        file2.close();
                                        out.close();
					exit(0);
                                }
			}
		}
		if (int1 > int2) {
			out.write((char*) &int1, sizeof(int));
			file1.read((char*) &int1, sizeof(int));
		} else {
			out.write((char*) &int2, sizeof(int));
			file2.read((char*) &int2, sizeof(int));
		}
	}
}

[ltrane2003]

This is a little more advanced than where I am right now. Can this be scaled down some? I appreciate the help.

[auburnsgrt]

any thoughts? This is what i have so far but i don't know where to go!

Please help

#include <fstream>

#include <iostream>

#include <cstdlib>
#include <string>


int main( )

{

using namespace std;

char fileA[16], fileB[16], fileC[16];

void merge_sort(ifstream& arrayA, ifstream& arrayB, ifstream& arrayC);



ifstream in_stream1;

ifstream in_stream2;
ofstream out_stream;



cout << "This program will compare two files containing numbers\n"

<< "and write the combination to an output file in descending order.\n";

cout << "Enter the input file name (maximum of 15 characters):\n";

cin >> fileA;
cout << "Enter the input file name (maximum of 15 characters):\n";
cin >> fileB;

cout << "Enter the output file name (maximum of 15 characters):\n";

cin >> fileC;

cout << "I will read numbers from the files: \n";

cout << fileA " and"<< fileB " then \n";

cout << "write the numbers in descending order to \n";

cout << fileC << endl;



in_stream1.open(fileA);

if (in_stream1.fail( ))

{

cout << "Input file opening failed.\n";

exit(1);

}

in_stream2.open(fileB);

if (in_stream2.fail( ))

{

cout << "Input file opening failed.\n";

exit(1);

}


out_stream.open(fileC);

if (out_stream.fail( ))

{

cout << "Output file opening failed.\n";

exit(1);

}

merge_sort(arrayA, arrayB, arrayC);

in_stream.close();
out_stream.close();

cout<<"End of Program.\n";


return 0;

}


void merge_sort(ifstream& arrayA, ifstream& arrayB, ofstream& arrayC)
{
int indexA = 0; // initialize the Array Indices
int indexB = 0;
int indexC = 0;

while((indexA < arrayA.length( )) && (indexB < arrayB.length( ))
{
if (arrayA[indexA] < arrayB[indexB])
{
arrayC[indexC] = arrayA[indexA];
indexA++; //increase the index
}
else
{
arrayC[indexC] = arrayB[indexB];
indexB++; //increase the index
}
indexC++; //move to the next position in the new array
}
// Push remaining elements to end of new array when 1 feeder array is empty
while (indexA < arrayA.length( ))
{
arrayC[indexC] = arrayA[indexA];
indexA++;
indexC++;
}
while (indexB < arrayB.length( ))
{
arrayC[indexC] = arrayB[indexB];
indexB++;
indexC++;
}
}
return;
}

[CoDeReBeL]

One could do this:

#include <cstdlib>
#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

int main(int argc, char *argv[])
{
    try
    {
       int i;
       vector <int> v ;
       ifstream *fin = new ifstream ("numbers1.dat") ;
       while (*fin)
       {
             *fin >> i ;
             v.push_back (i) ;
             fin->sync() ;
       }
       fin->close() ;
       delete fin ;
       fin = new ifstream ("numbers2.dat") ;
       while (*fin)
       {
             *fin >> i ;
             v.push_back (i) ;
             fin->sync() ;
       }
       fin->close() ;
       delete fin ;
       sort (v.begin(), v.end()) ;
       reverse (v.begin(), v.end()) ; 
       vector<int>::iterator t = unique (v.begin(), v.end()) ;
       v.resize (t - v.begin()) ;
       ofstream fout ("numbers3.dat") ;
       for (vector<int>::iterator i = v.begin() ; i != v.end() ; i++) fout << *i << endl ;
       fout.close() ;
       return EXIT_SUCCESS;
    }
    catch (exception e)
    {
          cout << e.what() << endl ;
          return 1 ;
    }
}

In other words, why dance back and forth between the two input files? Chuck all the contents of both into a vector, sort it, reverse it, and output it to the third file, eliminating duplicate values.

[Gumbercules]

well, I think that kind of misses the point of the assignment, though it would work. And, you can sort the vector in reverse order using:
sort (v.begin(), v.end(), greater<int>)

[buffbill]

You can do this using two boolean functions more () and copy() providing the two files to be merged are sorted in increasing order. The bool functions would look like:

bool more(ifstream& fin,int& n)
{if(fin>>n)return true;
else return false;}

boolcopy(ofstream& fout,fstream& fin,int&n)
{fout<<" "<<n;
return more(fin,n);}

The driver would look like:

int main()
(
ifstream fin1("input file name")
ifstream fin2("other input file name")
ofstream fout("output file name")
int n1,n2;
bool more1=more(fin1,n1);
bool more2=more(fin2,n2);

while(more1 && more2)
   if(n1<n2)more1=cpy(fout,fin1n1);
   else more2=copy(fout,fin2,n2);
while (more1)
  more1=copy(fout,fin1,n1);
while(more2)
  more2=copy(fout,fin2,n2) 
  fout<<endl;
}

The include files are <iostream> and <fstream>