JAVA - sorting a linked list by descending order

Question

i tried to write a method that sort a linked list. this is java training for me.

the method should get a linked list with values and sort it with selection sort. but not the usual selection sort, but selection sort that find the biggest number and put it in the start of the linked list. until the list is sorted.

i tried follow the debugger but, i cant really understand what i did wrong.

this is what i tired:

public IntList selectionSort()
{
    IntNode tempMax = _head;
    IntNode current = _head;
    IntNode fromHere = null;
    IntNode toHere = _head;
    IntNode prev = null;
    while(toHere != null)
    {
        current = toHere;
        tempMax = toHere;
        while (current != null)
        {
            if (current.getNext() != null && current.getNext().getValue() > tempMax.getValue())
                {
                    prev = current;
                    tempMax = current.getNext();
                    current = current.getNext();
                }
            else current = current.getNext();      
        }
        prev.setNext(prev.getNext().getNext());
        tempMax.setNext(toHere);            
        if (fromHere == null)
            _head = tempMax;
        else fromHere.setNext(tempMax);
        fromHere = tempMax;
        toHere = fromHere.getNext();
    }
    return this;
}

enter image description here

Why don't you just move the values inside a IntNode rather than moving IntNode around. — UmNyobe
– UmNyobe, Commented Feb 7, 2012 at 12:33
Could you put in some comments into your code? I'm having a hard time keeping track of which variable is used for what. — G. Bach
– G. Bach, Commented Feb 7, 2012 at 13:01

Sideshow Bob · Accepted Answer · 2012-02-07 12:17:00Z

1

A few tips:

If you want the smallest number then current.getNext().getValue() > tempMax.getValue() should have a > instead of a <
Your code will also fail if the first element is already the minimum value, as you try to do something to null
I can see duplicated code in here too, current = current.getNext(). Pointer operations are generally hard to code, and writing clearer code sticking to the principle of Don't Repeat Yourself will probably help you see bugs!
It will help people here help you if you print compiler/runtime error messages

edited Feb 7, 2012 at 12:17

answered Feb 7, 2012 at 12:09

Sideshow Bob

4,7466 gold badges47 silver badges82 bronze badges

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

3 Comments

Yuval Levy Over a year ago

i know, but i want to sort from biggest to smaller.

UmNyobe Over a year ago

that's not what you say in the description

UmNyobe Over a year ago

if the first element is already the minimum value... yes use >=

UmNyobe · Accepted Answer · 2012-02-07 14:03:51Z

The main issue with your code, is that it misbehave when a node is already at the position it should be. If we execute with :

5 -> 1 -> 2 -> 3-> 4

prev will be null and we crash.

If we do with :

1 -> 4 -> 5 -> 3-> 2

at the first iteration you obtain

5 -> 4 -> 1 -> 3-> 2

So far so good.And then, after the loop of the second iteration

5 -> 4 -> 3-> 2 // prev still pointing at 4, 1 dissapears

5 -> 4 -> 4. // tempMax = toHere so tempMax->tempMax, and the other elements are gone

So the manifestation is that prev is invalid in some way. There is a quick fix, like skipping the repositioning when toHere is the maximum, but quick fixes are not what you need. You should :

Rethink about some special cases. Empty list, one element, list already sorted, list sorted in reverse, random order, (duplicate element??)
Write unit test for each case
Rewrite your algorithm, and avoid Oh yes, I forgot the case... . Dumb it down, you only need to replace the first element at each given step with the maximum found at this step.
Avoid variables which have redundant information. For example, tempMax should always be the next of prev, so prev alone is enough. Otherwise you are spending brain cells preserving consistency.
Test again the suite case.

Collectives™ on Stack Overflow

JAVA - sorting a linked list by descending order

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related