Merge Sort on Strings in Java - Linked List

Question

I have an excercise in which I have to insert into a linked list a string. Suppose the String is the following:

"Java Coding Is Great"

After the Merge Sort, the linked list is supposed to look like that:

coding >>> great >>> is >>> java.

The problem is that in my Merge Sort code I recieve the following:

 great >> is >> java >> coding

All the words are sorted BUT THE FIRST WORD (Head of the original list) is not.

I have two classes: TextList and WordNode.

The WordNode class has two attributes:

String _word; WordNode _next; //an address to the next link

The TextList class has only one attribute: an address of the head of the linked list:

WordNode _head;

I have a constructor in which I insert the String randomly into a linked list. in the end it starts merge sotring the list. This algorithem is for this excercise.

public TextList(String text){
     String s=""; int index=text.length();
    //we will stop at the end of the String.
    for (int i=text.length()-1; i>=0; i--){
        //if we reached a space, insert each string in appropriate order, 
        //the first word is the head of the string and last word points to null.
        if (!(text.charAt(i)>='a' && text.charAt(i)<='z')){ 
            s=text.substring(i,index);
            _head=new WordNode(s,_head);
            s="";
            index=i;
        }
        if (i==1){
            s=text.substring(i-1,index);
            _head=new WordNode(s,_head);
        }
    }

//start merge sotring the list.
    this._head=this._head.mergeSort();
}

Merge Sort Methods: mergeSort, merge and split: (These are in the WordNode class):

Merge Sort method

public WordNode mergeSort(){
    return mergeSort(this);
}
private WordNode mergeSort(WordNode h){
    // Sort h by recursively splitting and merging
    if (h==null || h._next==null)
        return h;
    else{
        WordNode evens=h.splitOdds();
        WordNode odds=h.splitEvens();
        return mergeSort(odds).merge(mergeSort(evens)); 
    }
}

Merge Method

private WordNode merge(WordNode h){
        //method merges this's list with h's list

        //if h is null, just return this.
        if (h==null){
            return this;
        }
        if (this._word.compareTo(h._word)<0){
            if (this._next==null)
                return new WordNode(this._word,h);
            else
                return new WordNode(this._word,this._next.merge(h));
        }
        else
            return new WordNode (h._word, merge(h._next));

    }

Split Methods: one for even positions, one for odd positions.

private WordNode splitOdds(){
    boolean flag=true;
    WordNode odds=null;
    WordNode ptr=this;
    while (ptr!=null){  
        if(flag)
        odds=new WordNode(ptr._word,odds);
        ptr=ptr.getNext();
        flag=!flag;
    }
    return odds;
}
//MUST BE INITILIZED ON HEAD
    private WordNode splitEvens(){
        boolean flag=true;
        WordNode evens=null;
        WordNode ptr=this._next;
        while (ptr!=null){
            if (flag)
                evens=new WordNode(ptr._word,evens);
                ptr=ptr.getNext();
                flag=!flag;
            }



        return evens;
    }

Please help me figure out what's wrong. Unfortently, I can not use a third class, and I can't use pointers to the start of the list or to the end of the list.

Posting more times the same question won't help you finding the answer. Please delete one of the two and wait for an answer. — BackSlash
– BackSlash, Commented Jun 8, 2013 at 14:33
@BackSlash - I made real progress here, as the code almost works. thank you for paying attention - how can I delete my previous question? — Assaf
– Assaf, Commented Jun 8, 2013 at 14:34
Don't delete it. Delete this question instead, and update the old one with all new details. — BackSlash
– BackSlash, Commented Jun 8, 2013 at 14:35
@BackSlash, that doesn't make any sense. Why would he delete the new question, which has a much higher probability of actually being answered? — Steve P.
– Steve P., Commented Jun 8, 2013 at 14:56
This is probably just a typo, but you have : this._head=this._head.mergeSort();, yet your mergeSort method takes a WordNode. — Steve P.
– Steve P., Commented Jun 8, 2013 at 15:01

rossum · Accepted Answer · 2013-06-08 14:34:16Z

1

Can you use your debugger to single-step through your code? That will help you pinpoint the problem. Even a few judiciously placed breakpoints will help.

Start with a list containing only a single entry: "Java". See what happens.

Then try a two-entry list: "Java Coding". See what happens in that case.

Work out what is happening in the simple cases and then work up to the more complex ones.

answered Jun 8, 2013 at 14:34

rossum

15.7k2 gold badges26 silver badges40 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

Assaf Over a year ago

Tried that now... so far didn't succeed figuering out. Maybe any other idea?

rossum Over a year ago

Crude solution, which doesn't get to the root of the problem. Add a spurious entry to the start of the list: "AAAAAAA", sort and then remove the spurious entry.

Steve P. Over a year ago

@Alan How could you not find anything out using the debugger? Did you try to use it and realize that you didn't now how to use it? Not trying to be rude, but it must have helped you figure something out...

Assaf Over a year ago

@Steve P. Maybe the problem is with the head - it keeps going back to the END of the linked list after merging, I just can't get why.

Assaf Over a year ago

@rossum - that may work, but I will have to go thorugh all the list for that, right? I think this might work but as you suggested - won't get to the root of the problem.

|

Assaf · Accepted Answer · 2013-06-08 18:29:29Z

1

The problem here was a bit funny.

In my constructor I have carried a space with each word I have inserted to my list.

I fixed that by this code:

            s=text.substring(i+1,index);

instead of:

            s=text.substring(i,index);

The credit is to NormR from DevForum for the answer.

answered Jun 8, 2013 at 18:29

Assaf

1,1244 gold badges16 silver badges38 bronze badges

Comments

qpaycm · Accepted Answer · 2013-06-18 09:47:31Z

Nice, but I don't like your solution to merge() in WordNode. On one hand you can compare each node you prefer to like this:

this._word.compareTo(h._word);

But in that case merge() and split() both private, so I think the better way is to put them into TextList and mergeSort() without overloading. You need to sort all nodes in linked list anytime you add a node, not just a part of it anyway. That's why this

this._head = this._head.mergeSort();

and this

public WordNode mergeSort(){
    return mergeSort(this);
}

looks useless in WordNode.
On the other hand if you put your call to mergeSort into TextList like this

this._head = this.mergeSort(this._head);

and mergeSort into this one in TextList

 public WordNode mergeSort(WordNode n){

 }

it's already better but you can do even much better by reducing more time and space compexity of the way you split your list to odds and evens like this

int counter = 1;    //  nodes counter helps to know if the current node is odd or even
WordNode L = null,  //  odd nodes
         R = null;  //  even nodes
while(h != null)
{
    if(counter%2 == 0)
        R = new WordNode(h.getWord(), R, h.getWordCounter());
    else
        L = new WordNode(h.getWord(), L, h.getWordCounter());
    //  
    h = h.getNext();
    counter++;
}

When you put it together you get something like this(don't forget words counter)

public WordNode mergeSort(WordNode h){
    int counter = 1;    //  nodes counter helps to know if the current node is odd or even
    WordNode L = null,  //  odd nodes
             R = null;  //  even nodes
    while(h != null)
    {
        if(counter%2 == 0)
            R = new WordNode(h.getWord(), R, h.getWordCounter());
        else
            L = new WordNode(h.getWord(), L, h.getWordCounter());
        //  
        h = h.getNext();
        counter++;
    }
    return merge(mergeSort(L), (mergeSort(R)));
}

what is left now is to finish merge() like this and again don't forget words counter

private WordNode merge(WordNode L, WordNode R)
{   
    while(L != null || R != null)
    {
        if(L != null && R != null)
            if(L.getWord().compareTo(R.getWord()) <= 0)
                return new WordNode(L.getWord(), merge(L.getNext(), R), L.getWordCounter());
            else
                return new WordNode(R.getWord(), merge(L, R.getNext()), R.getWordCounter());
        else if(L != null)
            return new WordNode(L.getWord(), merge(L.getNext(), R), L.getWordCounter());
        else if(R != null)
            return new WordNode(R.getWord(), merge(L, R.getNext()), R.getWordCounter());
    }
    return null;
}

say hello to proffessor Rosenstein ;-)

Collectives™ on Stack Overflow

Merge Sort on Strings in Java - Linked List

3 Answers 3

8 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

8 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related