CODEWITHSUNDEEP
java
user1766888
user1766888

Reputation: 409

Incorrect output for selection sort on linked list

Im having trouble with my linked list selection sort below:

public static void selectionSort(LN l) {
    for (LN r = l; r != null; r = r.next) {
        LN min = r;
        for (LN s = r; s != null; s = s.next)
            if (min.value > s.value)
                min = s;
        LN temp = r;
        r.value = min.value;
        min.value = temp.value;
    }
}

So for the input: 10, 4,6,2,1,7,9,8,5,3 I get the output: 1,1,1,1,1,3,3,3,3,3

What's wrong with the sort here?

Upvotes: 0

Views: 286

Answers (1)

ruakh
ruakh

Reputation: 183484

This:

        LN temp = r;
        r.value = min.value;
        min.value = temp.value;

is wrong. By setting temp equal to r, you're actually causing them to refer to the same object; so modifying r.value is equivalent to modifying temp.value. So the above ends up not really modifying min.value; it just sets min.value to what it already was.

Instead, you should write:

        int temp = r.value;
        r.value = min.value;
        min.value = temp;

Upvotes: 2

Related Questions