Author Topic: Merging two sorted files in sorted order ...  (Read 12351 times)

Offline David

  • Hero Member
  • *****
  • Posts: 625
    • View Profile
Merging two sorted files in sorted order ...
« on: April 02, 2016, 09:03:35 PM »


This is especially handy if a file is too big to sort in memory ...

you can break it up into halves (or sizes that will fit into memory to be sorted there) ...

sort each half (in memory ... and then write it to a sorted file) ...

then merge the two sorted files into one big sorted file.


See the demo and two small test files that follow:

Code: [Select]
// mergeTwoSortedFiles.cpp //  // 2016-04-01 //


// http://developers-heaven.net/forum/index.php/topic,46.0.html


#include <iostream>
#include <fstream>


using namespace std;

const char* FNAME_1 = "File_1.txt";
const char* FNAME_2 = "File_2.txt";
const char* FNAME_3 = "File_3.txt";

const int NUM_ON_LINE = 10;

bool merge( const char* name1, const char* name2, const char* name3 )
{
    ifstream fin1( name1 );
    ifstream fin2( name2 );
    ofstream fout( name3 );
   
    if( fin1 && fin2 && fout )
    {
        string word1, word2;
        bool one = false, two = false;
        if( fin1 >> word1 ) one = true;
        if( fin2 >> word2 ) two = true;
        int count = 0;
        //cout << "one = " << one << '\n'; // debugging //
        //cout << "two = " << two << '\n';
        if( one && two )
            for( ; ; )
            {
                ++ count;
                if( word1 <= word2 )
                {
                    fout << word1 << ' ';
                    if( ! (fin1 >> word1) ) break;
                }
                else
                {
                    fout << word2 << ' ';
                    if( ! (fin2 >> word2) ) break;
                }
                if( count % NUM_ON_LINE == 0 ) fout << '\n';
            }
       
        if( fin1 )
        {
            fout << word1 << ' ';
            if( ++count % NUM_ON_LINE == 0 ) fout << '\n';
            while( fin1 >> word1 )
            {
                fout << word1 << ' ';
                if( ++count % NUM_ON_LINE == 0 ) fout << '\n';
            }
        }
        if( fin2 )
        {
            fout << word2 << ' ';
            if( ++count % 10 == 0 ) fout << '\n';
            while( fin2 >> word2 )
            {
                fout << word2 << ' ';
                if( ++count % NUM_ON_LINE == 0 ) fout << '\n';
            }
        }
       
        fout.close();
        fin2.close();
        fin1.close();
       
        cout << "The number of words put into sorted order was : "
             << count << endl;
             
        return true;
    }
    // else ...
    cerr << "There was a problem opening";
    if( !fin1 ) cerr << " ... " << name1;
    if( !fin2 ) cerr << " ... " << name2;
    if( !fout ) cerr << " ... " << name3;
    return false;
}



int main()
{
    if( merge(FNAME_1, FNAME_2, FNAME_3) )
    {
        cout << "\n(Look in file '" << FNAME_3
             << "' to see the words merged in sorted order.)";
    }
   
    cout << "\n\nPress 'Enter' to continue/exit ... ";
    cin.get();
}


File_1.txt:

Code: [Select]
123 133 233 333 444 555 666 778 888 995
999


File_2.txt:

Code: [Select]
023 124 234 323 445 447 449 557 663 770
771 889 994 998 999
« Last Edit: April 02, 2016, 09:23:41 PM by David »