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

• UmNyobe: Why don't you just move the values inside a IntNode rather than moving IntNode around.
• G. Bach: Could you put in some comments into your code? I'm having a hard time keeping track of which variable is used for what.

Answer 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

• Yuval Levy: i know, but i want to sort from biggest to smaller.
• UmNyobe: that's not what you say in the description
• UmNyobe: if the first element is already the minimum value... yes use >=

Answer 2

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.