Merge Sort

Please support our C++ advertiser: Intel Parallel Studio Home
Reply

Join Date: Sep 2007
Posts: 20
Reputation: The Midnighter is an unknown quantity at this point 
Solved Threads: 0
The Midnighter The Midnighter is offline Offline
Newbie Poster

Merge Sort

 
0
  #1
Feb 25th, 2008
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:

  1. while ( !fin.eof() )
  2. {
  3. if ( !fin.eof() )
  4. {
  5. do
  6. {
  7. curr = next;
  8.  
  9. fin >> next;
  10.  
  11. fout1 << curr << endl;
  12. }
  13. while ( !fin.eof() && (curr <= next) );
  14. }
  15.  
  16. if ( !fin.eof() )
  17. {
  18. do
  19. {
  20. curr = next;
  21.  
  22. fin >> next;
  23.  
  24. fout2 << curr << endl;
  25. }
  26. while ( !fin.eof() && (curr <= next ) );
  27. }
  28. }
Reply With Quote Quick reply to this message  
Join Date: Jul 2005
Posts: 1,678
Reputation: Lerner is a name known to all Lerner is a name known to all Lerner is a name known to all Lerner is a name known to all Lerner is a name known to all Lerner is a name known to all 
Solved Threads: 262
Lerner Lerner is online now Online
Posting Virtuoso

Re: Merge Sort

 
0
  #2
Feb 25th, 2008
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.
Last edited by Lerner; Feb 25th, 2008 at 5:23 pm.
Reply With Quote Quick reply to this message  
Join Date: Sep 2007
Posts: 20
Reputation: The Midnighter is an unknown quantity at this point 
Solved Threads: 0
The Midnighter The Midnighter is offline Offline
Newbie Poster

Re: Merge Sort

 
0
  #3
Feb 26th, 2008
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.
Reply With Quote Quick reply to this message  
Join Date: Jul 2005
Posts: 1,678
Reputation: Lerner is a name known to all Lerner is a name known to all Lerner is a name known to all Lerner is a name known to all Lerner is a name known to all Lerner is a name known to all 
Solved Threads: 262
Lerner Lerner is online now Online
Posting Virtuoso

Re: Merge Sort

 
0
  #4
Feb 26th, 2008
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.
  1. //attempt to read value from file into next
  2. fin >> next;
  3.  
  4. //while success reading from file into next
  5. while ( fin.good())
  6. {
  7. do
  8. {
  9. //assign next to curr
  10. curr = next;
  11.  
  12. //write curr to file #1
  13. fout1 << curr << endl;
  14.  
  15. //read in next value from file
  16. fin >> next;
  17.  
  18. //while able to read something into next and
  19. //if prior last reading <= next reading
  20. }while (fin.good() && curr <= next);
  21. }
  22.  
  23. //if something in next at end of first do/while loop
  24. if(fin.good())
  25. {
  26. do
  27. {
  28. curr = next;
  29. fin >> next;
  30.  
  31. //write curr into file #2
  32. fout2 << curr << endl;
  33. }while( fin.good() && curr <= next);
  34. }
  35. }
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.
Reply With Quote Quick reply to this message  
Join Date: Sep 2007
Posts: 20
Reputation: The Midnighter is an unknown quantity at this point 
Solved Threads: 0
The Midnighter The Midnighter is offline Offline
Newbie Poster

Re: Merge Sort

 
0
  #5
Feb 27th, 2008
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:
  1. Michael Dillon
  2. Classname ClassMark
  3. 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 =(
Last edited by The Midnighter; Feb 27th, 2008 at 9:14 am.
Reply With Quote Quick reply to this message  
Join Date: Jul 2005
Posts: 1,678
Reputation: Lerner is a name known to all Lerner is a name known to all Lerner is a name known to all Lerner is a name known to all Lerner is a name known to all Lerner is a name known to all 
Solved Threads: 262
Lerner Lerner is online now Online
Posting Virtuoso

Re: Merge Sort

 
0
  #6
Feb 27th, 2008
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
  1. Classname Classmark
  2. Michael Dillon
  3. Teachername TeacherSomething
  4.  
  5. or
  6.  
  7. Michael Classmark
  8. Classname Dillon
  9. Teachername TeacherSomething
Reply With Quote Quick reply to this message  
Join Date: Sep 2007
Posts: 20
Reputation: The Midnighter is an unknown quantity at this point 
Solved Threads: 0
The Midnighter The Midnighter is offline Offline
Newbie Poster

Re: Merge Sort

 
0
  #7
Feb 27th, 2008
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?
Reply With Quote Quick reply to this message  
Join Date: Jul 2005
Posts: 1,678
Reputation: Lerner is a name known to all Lerner is a name known to all Lerner is a name known to all Lerner is a name known to all Lerner is a name known to all Lerner is a name known to all 
Solved Threads: 262
Lerner Lerner is online now Online
Posting Virtuoso

Re: Merge Sort

 
0
  #8
Feb 27th, 2008
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.
  1. //read file, storing information in two containers of your choice, say vectors, depending on column location in file.
  2. int i = 0;
  3. vector <string> v1;
  4. vector <string> v2;
  5. while(fin >> v1[i])
  6. fin >> v2[i++];
  7.  
  8. //ask user to select which column (which means which vector) they want to sort
  9. cout << "enter 1 if you want to sort column 1 and two if you want to sort column 2" << endl;
  10. int choice;
  11. cin >> choice;
  12. if(choice == 1)
  13. mergeSort(v1); //sort container 1
  14. else
  15. mergeSort(v2); //sort container 2
Reply With Quote Quick reply to this message  
Join Date: Sep 2007
Posts: 20
Reputation: The Midnighter is an unknown quantity at this point 
Solved Threads: 0
The Midnighter The Midnighter is offline Offline
Newbie Poster

Re: Merge Sort

 
0
  #9
Feb 27th, 2008
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?
Reply With Quote Quick reply to this message  
Join Date: Feb 2008
Posts: 16
Reputation: sohguanh is an unknown quantity at this point 
Solved Threads: 2
sohguanh sohguanh is offline Offline
Newbie Poster

Re: Merge Sort

 
0
  #10
Feb 28th, 2008
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.
Reply With Quote Quick reply to this message  
Reply

This thread is more than three months old.
Perhaps start a new thread instead?
Message:


Thread Tools Search this Thread



About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC