CODEWITHSUNDEEP
javaalgorithmsorting
Yuval Levy
Yuval Levy

Reputation: 2516

JAVA - sorting a linked list by descending order

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

Upvotes: 2

Views: 4287

Answers (2)

UmNyobe
UmNyobe

Reputation: 22890

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.

Upvotes: 1

Sideshow Bob
Sideshow Bob

Reputation: 4716

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

Upvotes: 1

Related Questions