Merge Sort fiasco!
I recently posted something similar, but the thread is lost, and posting more code blocks on there would be messy...
Here we are again, this time, I wrote a merge sort function that I thought worked. It sort of does. I have to read in a text file, containing some "Programming Proverbs". We have to stick it in a linked list, and then sort the list so that the words are printed in alphabetic order.
It starts to work. it prints two lines...
heres the relevant code (I omit cisio.java, because it is again, useless and has nothing to do with anything! :] )
Node.java
import java.util.*;
import java.text.*;
class Node
{
int numlines;
String Symbol;
int lines[];
Node next;
Node(Token t)
{
Symbol =new String(t.token);
lines =newint [200];
lines[0] = t.linenr;
numlines = 1;
next =null;
}
void addline(int n)
{
lines[numlines++] = n;
}
void display()
{
int i;
System.out.print(Symbol+" ");
for (i = 0; i<numlines; i++)
{
System.out.print(lines[i]+" ");
}
System.out.println();
}
}
Index4.java
import java.util.*;
class Index4
{
Node head;
Node p = head;
Index4()
{
head =null;
}
void display()
{
while (p!=null)
{
p.display();
p = p.next;
}
}
void add(Token t)
{
//See if this token is already on list
while(p!=null)
{
if(p.Symbol.equals(t.token))
{
p.addline(t.linenr);
return;
}
p = p.next;
}
//not found, add at start of list
p =new Node(t);
p.next = head;
head = p;
}
public Node merge_sort (Node list)
{
if (list ==null || list.next ==null)
return list;// checks for empty or single list
Node list2 = split (list);
list = merge_sort (list);
list2 = merge_sort (list2);
return merge (list, list2);
}
public Node split (Node list)
{
if (list ==null || list.next ==null)
returnnull;
Node list2 = list.next;
list.next = list2.next;
list2.next = split (list2.next);
return list2;
}
public Node merge (Node list, Node list2)
{
if (list ==null)
return list2;
if (list2 ==null)
return list;
if (list.Symbol.compareTo(list2.Symbol) >< 0)
{
list.next = merge (list.next, list2);
return list;
}
else
{
list2.next = merge (list, list2.next);
return list2;
}
}
}
Token.java
import java.util.*;
import java.text.*;
class Token
{
String token;
int linenr;
private StringTokenizer tokens;
public Token()
{
String s;
token =new String();
s = cisio.GetLine();
tokens =new StringTokenizer(s);
linenr = 1;
System.out.println(linenr+". "+s);
}
publicboolean getToken()
{
String s;
while(!tokens.hasMoreTokens())
{
if(cisio.eof())
returnfalse;
s = cisio.GetLine();
if(cisio.eof())
returnfalse;
tokens =new StringTokenizer(s);
linenr += 1;
System.out.println(linenr+". "+s);
}
token = tokens.nextToken();
returntrue;
}
publicvoid display()
{
System.out.println("Token ='"+token+"' line number = "+linenr);
}
}
Lab4.java (The testing program)
publicclass Lab4
{
publicstaticvoid main(String args[])
{
Token t =new Token();
Index4 index =new Index4();
while (t.getToken())
{
//t.display();
index.add(t);
}
index.merge_sort(index.p);
index.display();
}
}
I dont think I need to give the text file to be read in. Any chunk of text would do to test this...
It will print the entire linked list fine if I remove merge sort, so I know I jacked merge sort up...
take a look, any suggestions? ?
Thanks a bunch, as usual :)
[8453 byte] By [
Arkhana] at [2007-10-3 8:29:37]
> I recently posted something similar, but the thread
> is lost, a
No, it's not. On the left, where it says "Welcome [url http://forum.java.sun.com/profile.jspa?userID=572365]Arhkan[/url], click on your name, and you'll see your posting history.
> nd posting more code blocks on there would
> be messy...
Okay, fine. Pick it up here.
But find that other thread, and post there that the discussion is continued here, with a link to this thread, so that people don't waste their time duplicating each others' comments.
> Here we are again, this time, I wrote a merge sort
> function that I thought worked. It sort of does. I
> have to read in a text file, containing some
> "Programming Proverbs". We have to stick it in a
> linked list, and then sort the list so that the words
> are printed in alphabetic order.
>
> It starts to work. it prints two lines...
So what exactly is the problem? That it only prints two lines?
Okay, so you think it should be printing more. As you look at your code, you think you know what's going on. What various variables are set to, when varions if, while, etc. conditions become true or false. But clearly you're mistaken. You need to find out where. One or more steps is not doing what you think it is.
So how can you find out which steps you're mistaken about? You start with a file, and end up with 2 lines of output. Something inbetween goes wrong. How do you think you might go about figuring out which step inbetween is not doing what you think it's doing?
My previous thread didnt get any replies except like one rude one from a previous....thing.
Anyways...
When it reads the file in, it should print an index of every word in the list, in order. It only prints two words. It should continue to count every word, but it isn't. I've tried stepping through to find the problem, but no such luck. I cant see where its going wrong.
Did you take a look at it and maybe see where something is messed up?
I'm not going to read or compile and run your code.
If you put in print statements or use a debugger, and explain the exact step at which things are not what you expected, what you did expect, and what happened instead, then somebody will be happy to help you.
You wrote the code, so you should be able to say what you think is going to happen at each step along the way. If you can't walk through your code by hand for some small input sample (say 3 or 4 items, since you say it's dying after 2), and predict what you think should happen, then you need to take a step back and review the fundamentals.
Once you are able to find the point at which things differ from what you expect, we can move on from there.
Look man you don't have to tell me how to debug code. Im not that retarded.
Like I said, with my merge sort method, it should be sorting the list of words. It will print the entire list with the line # that the word appears on no problem, so I know the list is constructing itself properly. When I call merge sort and then have it display again, it will only print two things:
Wrong 12
Yet 10
This is the text file
1. PROGRAMMING PROVERBS
2.
3. Don't get suckered in by the comments -- they can be terribly misleading.
4. Debug only code.
5.
6. It is easier to change the specification to fit the program than vice versa.
7.
8. Technological progress has merely provided us with more efficient means for going backwards.
9.
10. The First Rule of Program Optimization: Don't do it. The Second Rule of Program Optimization (for experts only!): Don't do it yet.
11.
12. If the code and the comments disagree, then both are probably wrong.
13.
The merge sort isnt working right, can you look at that section of the code and see if you see something I dont?
> Look man you don't have to tell me how to debug code.Obviously, I do. This is a simple debugging issue, and you have neither solved it nor provided the information I asked for in order for me to help you.I don't need the attitude. Good luck. I'm out.
I told you what you asked for. During the merge sort method, its not merging/sorting like it should. Im sure if youd spend the whopping 30 seconds it takes to stare at the not so large method, you couldve easily just given a suggestion or two....instead of implying im a complete idiot.
Thanks.
> I told you what you asked for.
No, you did not. If you had, I would have used it.
. During the merge sort
> method, its not merging/sorting like it should.
I asked for details. "It doesn't work" tells me nothing.
> Im
> sure if youd spend the whopping 30 seconds it takes
> to stare at the not so large method, you couldve
> easily just given a suggestion or two....instead of
> implying im a complete idiot.
Yeah, being a sarcastic knobjockey will help.
I didn't imply you're a complete idiot. I provided you with advice on how to debug your code--or at least find enough information to enable somebody else to help you debug it. It was good advice. I've been a professoinal developer for 14 years, and it's how I do it. It's how every decent developer I know does it. Instead of following that advice, you decided to get all pissy.
Like I said, I'm done.
im not being sarcastic. Sorry for being pissy man, but when youve been sitting dicking with this thing for a week, and all youve gotten out of it is like 15 unworking lines of code, its hard to keep cool when someone explains the process of explaining a problem. Especially when the thing is due in a day.
I have no clue what the actual problem is. I call merge_sort, and it doesnt split the list down and down and down recursivley until it hits the base case properly. All i get is two lines when I should be getting the entire list, sorted. I suck at java. Thats why I posted it in the new to java section.
Do you have a better way of sorting a linked list besides a merge sort? The book for my class has TONS of sorting methods, that all apply to arrays, and none for linked lists.
> im not being sarcastic. Sorry for being pissy man,
> but when youve been sitting dicking with this thing
> for a week, and all youve gotten out of it is like 15
> unworking lines of code, its hard to keep cool when
> someone explains the process of explaining a problem.
If my explanation of the process annoys you, that's unfortunate. However, that doesn't alter the facts that a) it's necessary and b) you haven't done it.
To wit...
> I have no clue what the actual problem is. I call
> merge_sort, and it doesnt split the list down and
> down and down recursivley until it hits the base case
> properly. All i get is two lines when I should be
> getting the entire list, sorted.
This is merely a vague description of how the overall program doesn't meet the ultimate requirements. To fix it, you need to figure out which of the individual steps are not proceeding as you expect. In order to do that, you have to know what's going on at each of the individual steps, and you have to have a prediction as to what you think is going on.
So you take a small input sample, predict what you think will happen at each step, then observe each step with a debugger or print statements, and note which ones differ from what you expect. Then you say, "In this section of the code, I expected it to have 'abc' and 'def', but instead it had 'abcdef' and ''. What's going on?" Or something like that.
I'm not trying to be insulting. I don't know how to explain it any better than this.
> I suck at java.
> Thats why I posted it in the new to java section.
No problem there. I was trying to help you by guiding you through the steps needed to debug this kind of problem. You seem to be resistant to following them. I can't help you if that's the case.
> Do you have a better way of sorting a linked list
> besides a merge sort?
"Better" depends on your requirements. The problem isn't that you're using mergesort. The problem is that you're not analyzing your code's execution properly or thoroughly enough.
> The book for my class has TONS
> of sorting methods, that all apply to arrays, and
> none for linked lists.
Any method that works on an array can work on a LL and vice versa. Some are more efficient than others in terms of memory or speed on one type of data structure vs. the other, because of how they manipulate the list. Using the wrong sort for your data structure won't give you the wrong results, but it might make it slow.
Going to be perfectly honest with you.
First, I made a 3 line text file to sort....
I displayed the list inside of the merge sort method, and then the split method....and I honest to God have no clue what its doing.
can you tell me if the Merge_sort, split, and merge methods here have any logic error? The split and mergesort display calls shows the different lists, but I cant follow whats happening. -_- Its rather messy.
What I think is happening, is that when its "Splitting" its only taking the next link. the first time Display is called , List1 has a word and list2 has a word, so that 3rd word is getting ignored....
at least thats what I think ...could be wrong.
public void begin_merge()
{
Node p = head;
while(p!=null)
{
merge_sort(p);
p = p.next;
}
}
public Node merge_sort (Node list)
{
if (list == null || list.next == null)
return list; // checks for empty or single list
Node list2 = split (list);
list = merge_sort (list);
list2 = merge_sort (list2);
return merge (list, list2);
}
public Node split (Node list)
{
if (list == null || list.next == null)
return null;
Node list2 = list.next;
list.next = list2.next;
list2.next = split (list2.next);
return list2;
}
public Node merge (Node list, Node list2)
{
if (list == null)
return list2;
if (list2 == null)
return list;
if (list.Symbol.compareTo(list2.Symbol) < 0)
{
list.next = merge (list.next, list2);
return list;
}
else
{
list2.next = merge (list, list2.next);
return list2;
}
}
I do know that it is at least performing the compareTo. :) A start...
I also noticed that now that the text file only has 3 lines, the final result is it displaying just ONE line this time....any idea?
You're still not following my advice.
Take a list with, say, 6 elements. 5 3 6 1 2 4 or something. Manually step through the code as if you're the VM and figureout what you think should happen at each step. Use a debugger or println to see what actually happens at each step. See where expected vs. actual differ.
You can do them simultaneously. Predict one step. Observe that step. Repeat.
Good luck.
> You're still not following my advice.
>
> Take a list with, say, 6 elements. 5 3 6 1 2 4 or
> something. Manually step through the code as if
> you're the VM and figureout what you think should
> happen at each step. Use a debugger or println to see
> what actually happens at each step. See where
> expected vs. actual differ.
>
> You can do them simultaneously. Predict one step.
> Observe that step. Repeat.
>
> Good luck.
I did try that, and thats where everything got messy and confused me. Heh, if I understood what was happening, I probably wouldn't be asking for help.... :( But I am lost, hence my posting.
I get lost somewhere in the recursion that goes on, but I think something might be wrong with the split() method. That is where when I output the two lists, an entire word is excluded from the split.
List 1 becomes a word
List 2 becomes a word
in a list with 3 or more words, ...it ignores an entire word?
Could you please take a look at split() and see if theres a logic mistake or something that I'm not seeing?
EDIT: With the Java studio creator for Mac, I cant get the Debug to work right. I think it has something to do with cisio.java being present, so it has no way of getting any proper input.. great...
Message was edited by:
Arkhan
I'm taking off for the night, but here's what I'd do.
If you think split() is the culprit, then make sure it's doing what it should.
First, add a toString() method to your Node class that prints the data in a node followed by the next node. Something like this:
public String toString() {
String nextStr = (next != null) ? next.toString() : "null"; // null without quotes should also work, but this is more explicit.
return data + nextStr;
}
Then, each time split is called, I'd print out the before and after:
public Node split(Node list) {
System.out.println("Splitting: " + list);
// do the actual split
System.out.println("After split: " + list + "|" + list2);
return list2;
}
And then have main JUST call split on various lists: empty, 1 element, 2 element, 3 element, 4 element, 5 element.
You should see something like
splitting 1 2 3 4 5
splitting 3 4 5
splitting 5
after split: 5|null
splitting 2 4
splitting 4
after split: 4|null
splitting 2
after split: 2|null
after split: 2|4
after split: 3| 5
after split: 3 5|2 4
after split: 1 3 5 | 2 4
That's probably not quite right, as I'm rather tired and lazy, but the point is you'll see successive calls to split on list2 until you're down to empty or one item, and then it will all unravel and you'll see all the results.
You'll use the results of this test to see whether split is the problem, and to fix it if it is. If it's not, look at merge and mergeSort in a similar fashion.
One thing that can make recursion easier is to use a stack of papers or cards much like the call stack that method calls use. On a piece of paper, write down the values of parameters and variables as they change as the method flows. Then, when the method calls itself recursively, put a new paper on top and start fresh with the inputs for that method and track its internal varaibles as it executes. Keep doing this until you hit the terminal condition and return null or whatever. Then get rid of that top paper on the stack, and plug its return value into the proper place on the paper below--the one that called it recursively. As you build and unwind the stack this way, you'll be very closely mimicking what the VM is doing.
*frustration*
I put the displays in split, and get "Splitting: Node *insert hex here*" and then it prints null for the lists....
when toString was added, the program crashes with null point exception.
I entered it just as you sent it, only I changed data to Symbol, since thats the String in question.
Got the strangest feeling im not going to be getting credit for this assignment haha.
What the hell. I was bored. It looks to me like split() works.
public class Node<E> {
E data;
Node<E> next;
public static void main(String[] args) throws Exception {
Node<String> list = new Node<String>("A", null);
Node<String> tmp;
tmp = list.add("B");
tmp = tmp.add("C");
tmp = tmp.add("D");
tmp = tmp.add("E");
System.out.println("BEFORE SPLIT: " + list);
Node list2 = list.split(list);
System.out.println("AFTER SPLIT: " + list + "|" + list2);
}
Node(E data, Node<E> next) {
this.data = data;
this.next = next;
}
Node<E> add(E data) {
next = new Node<E>(data, null);
return next;
}
public Node<E> split (Node<E> list) {
System.out.println("splitting " + list);
if (list == null || list.next == null) {
System.out.println("returning null");
return null;
}
Node<E> list2 = list.next;
list.next = list2.next;
list2.next = split (list2.next);
System.out.println("after split: " + list + "|" + list2);
return list2;
}
public String toString() {
String nextStr = (next != null) ? next.toString() : "null"; // null without quotes should also work, but this is more explicit.
return data + " -> " + nextStr;
}
}
:; java -cp classes Node
BEFORE SPLIT: A -> B -> C -> D -> E -> null
splitting A -> B -> C -> D -> E -> null
splitting C -> D -> E -> null
splitting E -> null
returning null
after split: C -> E -> null|D -> null
after split: A -> C -> E -> null|B -> D -> null
AFTER SPLIT: A -> C -> E -> null|B -> D -> null
jverda at 2007-7-21 12:28:24 >
> *frustration*
>
> I put the displays in split, and get "Splitting: Node
> *insert hex here*" and then it prints null for the
> lists....
>
> when toString was added, the program crashes with
> null point exception.
Yes, there was a bug in my code. I fixed it. You should be able to find it from the stack trace and the code.
jverda at 2007-7-21 12:28:24 >
This looks weird:
public void begin_merge()
{
Node p = head;
while(p!=null)
{
merge_sort(p);
p = p.next;
}
}
I don't think it should break it, but it should be unnecessary.
merge_sort(p) should sort the whole list. You shouldn't have to then merge sort the last 4, then last 3, then last 2, etc.
jverda at 2007-7-21 12:28:24 >
Hm two things Im curious on.
First, you put split in the Node class, I stuck all of my sorting methods into the Index4 class, which contains Node head;, and then functions for adding to the list (Node p = head; p = p.next; stuff)....was I wrong to stick them there? Should the whole sort be taking place in the Node class, and not the Index4 class?
Next, my newbishness thought I needed something like begin_merge, since p is created locally in each method. Once the method ends, doesn't p go away? in Lab4.java I dont think I can call index.merge_sort(p); since there is no public p variable?
I think I may have some things jumbled up.
I appreciate the help. :) ..I have to go to work until 5, and then I'll be back here to try completing this thing...
EDIT: JVerd, I just noticed something wonderful. Rather then sort the entire list with an algorithm...is there a way to modify the Add method in Index4.java so that it sticks the new link in the right location based off of a compareTo()?
Message was edited by:
Arkhan
> First, you put split in the Node class, I stuck all
> of my sorting methods into the Index4 class, which
> contains Node head;, and then functions for adding to
> the list (Node p = head; p = p.next; stuff)....was I
> wrong to stick them there? Should the whole sort be
> taking place in the Node class, and not the Index4
> class?
No. What I did was a hack. I just wanted to whip up a quick test to see if split was working, so I just copied/pasted and then took the quickest route to get it running. And calling list.split(list) is a total hack.
> Next, my newbishness thought I needed something like
> begin_merge, since p is created locally in each
> method. Once the method ends, doesn't p go away?
Yes, but I'm not sure what you're saying here. Having begin_merge is fine, but it shouldn't need to loop. It can just call mergeSort on the first node in the list, which should sort the entire list.
That's something else I'd do differently, although you can make it work your way. For you, a node is both a node and a list. I would have a separate class SinglyLinkedList that contains head node as a member variable.
> EDIT: JVerd, I just noticed something wonderful.
> Rather then sort the entire list with an
> algorithm...is there a way to modify the Add method
> in Index4.java so that it sticks the new link in the
> right location based off of a compareTo()?
Yes, you can do that, assuming the assignment rules allow it. I assumed you were required to write a mergesort.
jverda at 2007-7-21 12:28:24 >
No, the assignment says produce an index thats in order. I assumed sorting the finished list was the best plan.
and then I thought about it and went "Wait. Why dont I just put them in order as I go"....
any suggestions on doing it that way?
I've gathered that I can do something like
if(symbol.compareTo(symbol.next) < 0) //if symbol to be inserted is less then next one, just insert it at the beginning of the list.
and then I can already use the one in add method to append the line numbers to the already present entry...
so the part that seems tricky is..adding it at the end of the list, I've never done that. Any precautions?
I've tried now to set up the add function in Index4.java so that it does the following:
If the list is empty, just add a link
If the item to be added is smaller then the current item, add it before it (start of list)
and then the huge issue...
If the item is bigger, keep stepping through the list until it finds the right place for it, and add it there. This is not working at all :( this is what I have thus far....
void add(Token t)
{
Node p = head;
//See if this token is already on list
while(p!=null)
{
if(p.Symbol.equals(t.token))//already present in list. Append line#
{
p.addline(t.linenr);
return;
}
else if(t.token.compareTo(p.Symbol) > 0) //if the thing to add is greater than current
{
while(p.next!=null)
{
if(t.token.compareTo(p.Symbol) > 0 && t.token.compareTo(p.next.Symbol) < 0)
{
Node newLink = new Node(t);
p.next = newLink;
newLink.next = null;
return;
}
p = p.next;
}
}
p = p.next;
}
p = new Node(t);
p.next = head;
head = p;
}
what happens when it is run, is that it isn't outputting the entire list now...it prints only 4 words...
EDIT: Continued here http://forum.java.sun.com/thread.jspa?threadID=781136 since the problem is no longer the same as the original topic. :)
Message was edited by:
Arkhan
