Hi there-
I am trying to use Merge Sort on a linked list. I have it for the most
part but I need some help debugging my program. It's running, but its
not giving the correct output. Instead it's simply reversing the order
of the linked list, not sorting it in numerical order like it should.
I have a base linked list class which I have created. This works
perfectly and it useful for creating a linked list of different types
of objects. Here is a link to this code, so you can see it and
understand it. It's pretty simple, but since the merge sort I'm trying
to do is being intergrated into the class, I'll let you see what the
class looks like by itself first to get an understanding of it:
http://www.hiddentreasurehosting.com/source/basiclinkedlist.cpp
The basic linked list version has an Anything class, which you'll see
can be inheritied by any other object and then you can use virtual and
apply_to_all any function you like. Very useful for printing out the
linked list while using different objects' print methods.
Now here is the link to my current linked list source code which
include the Merge Sort in the class and doesn't work:
http://www.hiddentreasurehosting.com/source/linkedlistnotworking.cpp
I may be going about it all wrong, but I am sure the algorithm itself
is correct and I must have made some errors when trying to move it
inside my program. I have gotten most of it from a very reliable
source and compiled it outside of my class and it worked perfectly. In
case you would like to see this in action, (the merge sort algorithm
working perfectly) I've also included a link to that here:
http://www.hiddentreasurehosting.com/source/msexample.cpp
The problem I'm having is trying to integrate the two together,
placing the Merge Sort right in the linked list class. Now when I am
trying to move the Merge Sort in the Linked List I ran into a few
problems. To make it easier to read/write from now on I'll refer to
the basic working Linked List version as BLL and the version thats not
working with Merge Sort as the MS.
First off, you'll notice that in the BLL version, the line of code,
"Link *realdata"
is a protected member, but in the MS version I had to move it to
"public" in order to be able to access the head of the linked list in
the main like this, "mylist.merge_sort( &mylist.realdata );"
I also think that maybe I am comparing the wrong piece of data in my
merge sort comparisons. Just a guess, thats why I'm here for help.
The list is being reversely sorted, not numerically sorted like it's
supposed to be. (it might actually not even be reversely sorted, it
could be a coincidence, i'm not sure) I just know it's not working and
I can't figure out why.
Thanks alot for your help on this one, if you have any
questions/clairification needed, just post and I'll respond very
promptly. Also if I get a good answer I'll leave a nice tip! Thanks
alot for all the help! |
Hi balzack-ga,
Okay, I've added merge to your linked list code.
I'm uploading the code to my server now. This
link
http://nms.lcs.mit.edu/~gch/google/mergesort.zip
will be active shortly.
dogbite-ga |
Clarification of Answer by
dogbite-ga
on
24 Apr 2003 00:46 PDT
Hi balzack,
I'm just confirming that I have uploaded
the code to my server and the link is
now active. The code is commented, but
please let me know if you have any questions
about it.
Good luck!
dogbite-ga
|
Request for Answer Clarification by
balzack-ga
on
24 Apr 2003 07:37 PDT
Wow, thanks for the quick help. I don't have time at the moment to
take a look, i was just seeing if anyone had further questions. I will
check the code later on today and make sure I have no questions.
Thanks for the quick response.
|
Clarification of Answer by
dogbite-ga
on
24 Apr 2003 08:26 PDT
Hi balzack,
Nope, no questions from this end.
I'm glad you're happy with the
response time.
dogbite-ga
|
Request for Answer Clarification by
balzack-ga
on
24 Apr 2003 23:27 PDT
OK, after looking thru the code I have a few questions, but overall
great job:
int size2 = numberOfElements % 2 ? size1 + 1 : size1;
can you explain what this means? i believe its some kind of and
if/else statement, but i dont know the syntax cause i myself never use
it. if you could convert it to an if/else i'd appreciate it.
also what is the point of adding this to the Integer:public Anything
class? i realize you're defining the '<' but what does it do exactly?
bool operator< (Anything &a)
{
Integer& i = dynamic_cast<Integer&> (a);
return value < i.value;
}
also say i added another class with strings to be added to the linked
list. it would look something like this:
class MyString:public Anything, public string
{ public:
MyString(string & s):string(s) {}
MyString(char * s):string(s) {}
MyString(void):string() {}
virtual void print(void) {printf(" %s ", this->c_str()); }
};
how would i need to change the custom operator to handle that as well?
one last thing. the part where the algorithm is actually comparing the
data...i'm trying to make it easy for me to follow through the
algorithm so i understand it completely, so i'm trying to add a line
like:
cout << "comparing " << ((first -> data)) << " to " << ((mid -> data))
<< endl;
to print out the comparisions of data being made each step along the
way. this prints memory addresses, how can i get it to print out the
actual data?
other than that everything looks great. thanks again for the help.
|
Clarification of Answer by
dogbite-ga
on
25 Apr 2003 06:37 PDT
Hi balzack,
I put a new version of the code here:
http://nms.lcs.mit.edu/~gch/google/mergesort2.zip
And, let me address your questions one
at a time:
1) "int size2 = numberOfElements % 2 ? size1 + 1 : size1;"
- you're exactly right -- that is a compact syntax
for an if/else statement. i have expanded it
to a standard if/else block in the new code.
2) bool operator< (Anything &a)
- again, you're right -- this is overloading the '<'
operator. This is needed because the '<' comparison
operator will not automatically work on the Anything
class (or its subtypes). The function takes in another
object of its type and returns whether it is 'smaller'
than the inputed object.
3) I have included an example MyString class in the
code. That class must overload any abstract virtual
(keyword virtual and assigned to zero in an ancestor)
functions. As such, it must overload the operator<.
It must also overload the toString() function that I
also added to the new code.
4) I added a virtual toString() function that returns a
string holding its value. I also added a cout
statement that prints out the comparisons you want.
I hope helps clear things up.
dogbite-ga
|
Request for Answer Clarification by
balzack-ga
on
26 Apr 2003 22:34 PDT
OK great, just one last question that I have.
Integer& i = dynamic_cast<Integer&> (a);
and
MyString& s2 = dynamic_cast<MyString&> (a);
Could you just explain what these two statements are doing?
Thanks alot for the help.
|
Clarification of Answer by
dogbite-ga
on
27 Apr 2003 07:27 PDT
Hello balzack-ga,
The operator< function takes an Anything
reference because it is overriding the
virtual operator< function in the parent
Anything class. As such, the Anything
reference needs to be cast into an Integer
reference or a MyString reference.
So the dynamic_cast syntax casts, or names,
the Anything object to the proper subclass.
Does that make sense?
dogbite-ga
|
Request for Answer Clarification by
balzack-ga
on
27 Apr 2003 15:21 PDT
OK, that makes sense now but why when you setup:
virtual bool operator< (Anything &i) = 0;
Does it need to be set to zero? (I really think this is the last question =) )
Thanks again for all the help.
|
Clarification of Answer by
dogbite-ga
on
27 Apr 2003 15:47 PDT
Hey balzack-ga,
Yes, you should set it to zero
in the parent. That way you force
all implementing subclasses to
implement that function. Each
subclass will most likely have a
different meaning for "<", so you
should force them to implement it.
dogbite-ga
|
,
0 Comments
)