Merge Sort
 

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 ) );

        }

    }

Re: Merge Sort
 

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.

Re: Merge Sort
 

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.

Re: Merge Sort
 

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.

Re: Merge Sort
 

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 =(

Re: Merge Sort
 

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

Re: Merge Sort
 

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?

Re: Merge Sort
 

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

Re: Merge Sort
 

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?

Re: Merge Sort
 

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.