Merge Sort

[The Midnighter]

Alright, so I've got a Merge Sort program working that accepts a text file, and is supposed to split the data from that one text file, into TWO different text files. This is however, just putting them into one =x Any idea as to why?

here's part of my code:

while ( !fin.eof() )
    {
        if ( !fin.eof() )
        {
            do
            {
                curr = next;

                fin >> next;

                fout1 << curr << endl;
            }
            while ( !fin.eof() && (curr <= next) );
        }

        if ( !fin.eof() )
        {
            do
            {
                curr = next;

                fin >> next;

                fout2 << curr << endl;
            }
            while ( !fin.eof() && (curr <= next ) );
        }
    }

[Lerner]

There are several concerns with the code snippet you posted.

First, don't use eof() in the while conditionals.

Second, the if statements are superfluous.

Third, the first time through the loop, current will always be placed in the file associated with fout1. That may or may not be appropriate, I can't say for sure.

Fourth, assuming the rest of the file is set up right, that is---fout1 and fout2 are actually associated with files that are different from each other, current and next have valid assignment and <= operators defined, etc, and assuming the file that's being read in isn't already in sorted order, then you should end up with something in both files. I can't be as certain that the right stuff shows up in the right file, but something should show up in both files.

[The Midnighter]

Something does indeed show up in each file, I'm using the input file "inline.txt" which contains a-z.

When the program runs, it puts everything in the fout1 text file, except the last character in "inline.txt" which is 'm', and that goes in the fout2 file. I have noooooo idea why.

[Lerner]

Here's a modified version of the posted code snippet.
It's commented so you know what I think is more
appropriate syntax to do what I think you are trying
to do.

//attempt to read value from file into next
fin >> next;

//while success reading from file into next
while ( fin.good())    
{        
  do
  {
    //assign next to curr
    curr = next;

    //write curr to file #1
    fout1 << curr << endl;

    //read in next value from file
    fin >> next;

    //while able to read something into next and 
    //if prior last reading <= next reading
    }while (fin.good() && curr <= next);
  }
   
  //if something in next at end of first do/while loop
  if(fin.good())
  {         
    do
    {
      curr = next;
      fin >> next;

      //write curr into file #2
      fout2 << curr << endl;
    }while( fin.good() && curr <= next);
  }
}

Here's a sample input file and an assessment
of what I think the snippet will do. I've not
compiled the code snippet so I can't swear on
a stack of bibles that this is what it would do,
but it's what I think it would do

assume input file is: a c b d h g

outside while loop
next = a

inside first do/while loop
curr = a
a written to file #1
next = c
a < c so stay in first do/while

curr = c
c written to file #1
next = b
c > b so go to second do/while

curr = b
next = d
b written to file #2
b < d so stay in second do/while

curr = d
next = g
d written to file #2
d < g so stay i second do/while

curr = g
next = h
g written to file #2
g > h so go back to beginning loop

curr = h
fin fails because it finds eof()
h written to file #1
first do/while loop fails because fin is in the failed state

if statement false because fin is in the failed state so
second do/while loop not entered

outer while loop fails because fin in failed state

Code snippet completed.

At end of code snippet:
file #1 has ach
file #2 has bdg
fin is in failed state and can't be reused until it is cleared.

Without a sample input, expected output and observed oupt I can't
go further with your code.

[The Midnighter]

You're right, I should have just shown you the code.
I'm currently not having any problems with my merge sort, it's working it's just that it looks a little funny in the two temp files. That's okay though, my real worry is this:

Say I have input of:

Michael              Dillon
Classname         ClassMark
Teachername     TeacherSomething

I'm trying to get the program to accept that input, and ask the user which column they want the data sorted for. I'm trying this right now:

http://midnighter.ath.cx/SortingMerges.cpp

You can see in void mergeSort(); what I was trying to do.. (Accept a number as the column number, and then sort by that, by doing a while loop: while ( in >> line )
inside of a for loop: for (int i=0;i<choice;i++)
in hopes that it would stop after the user's choice. Didn't quite work out like that though, I think I have my logic backwards =(

[Lerner]

I don't understand? If the user says sort by column two do you want the output to be:

Classmark
Dillon
TeacherSomething

If so are the items in column one linked to the items in colum two or not? That is do you want

Classname      Classmark
Michael           Dillon
Teachername  TeacherSomething

or

Michael           Classmark
Classname      Dillon
Teachername  TeacherSomething

[The Midnighter]

Sorry I'm horrible with explainations.

By sorting by which column they choose, I mean this:

The columns would look the same, the column containing: "Michael", "Classname", "Teachername" would be column 1, so they could sort by column 1, or column 2, which would contain "Classmark", "Dillon", "Teachersomething"

Know what I mean?
So I could use a switch case perhaps and switch between which column to sort by. Know what I mean?

[Lerner]

Sorry, still not understanding what you are trying to sort and what the posted sample was.

Are Michael, Classname, etc examples of what's to be found in the file and are to be sorted or are they header names for the column which contain some other information that would be sorted?

Since the example shows there is always at least one space between the two columns and no spaces allowed within information within each column, then the >> operator can be used to separate the two columns into two containers and one or both of the containers could be sorted.

//read file, storing information in two containers of your choice, say vectors, depending on column location in file.
int i = 0;
vector <string> v1;
vector <string> v2;
while(fin >> v1[i])
   fin >> v2[i++];

//ask user to select which column (which means which vector) they want to sort
cout << "enter 1 if you want to sort column 1 and two if you want to sort column 2" << endl;
int choice;
cin >> choice;
if(choice == 1)
   mergeSort(v1);  //sort container 1
else
   mergeSort(v2); //sort container 2

[The Midnighter]

Actually yeah, that's pretty much exactly what I need. My only problem is getting mergeSort(vX) to work properly. I thought... about your idea, using the >> operator, I don't think that's going to work too well as there can be spaces in the record names... I'm thinking maybe getline with the tab as the delimiter?

[sohguanh]

Are you doing an assignment for school or course or seminar or training? In the real world outside nowadays C++ application programmer do not re-invent the wheel for common algorithms which include your mergesort. The C++ STL algorithms library should have some classes that do sorting. And if still not enough there is Boost library (Open Source) with more algorithms and classes to help us. Imagine a ready made Regular Expression class to use!!!!!!

If you are a C++ library writer with some commercial company to compete with STL and Boost then I would think re-invent can be an idea if you think you can beat the performance of the STL defined sort algorithm performance criteria.

[The Midnighter]

This is indeed for my class, my teacher wants us to understand the core workings of C++'s libraries so we don't have to rely on them, just incase I suppose. It's not a bad way to learn, it's just that there isn't enough documentation to get it working.