Batuhan Aydın Batuhan Aydın - 28 days ago 20
C# Question

Selection Sort on a Singly Linked List

As I checked, I find the right minimum value and previous node.After that the only thing I need to do is swapping nodes.However, after implementing this code the output is nothing.

After drawing the question I thought the problem is sorted part.So I added one more node which name is sorted but still I couldn't solve my problem.

public void selectionSort()
{

Node<T> first = head;
Node<T> previous = head;
Node<T> minimum = head;
Node<T> compare;
Node<T> temp;
Node<T> sorted = head;
while (first.Next != null)
{
sorted = minimum; // with this I'm finding the last sorted node
minimum = first;
compare = first.Next;

while (compare.Next != null)
{
if (minimum.Value.CompareTo(compare.Next.Value) > 0)
{
previous = compare; // Need previous node to changing connections
minimum = compare.Next; // Saving minimum value
}
compare = compare.Next;
}
// Swapping nodes
temp = first;
previous.Next = first;
first.Next = minimum.Next;
minimum.Next = temp.Next;

if ( temp != head)
{
sorted.Next = minimum; // Adding minimum node to sorted part
}

first = first.Next;
}


}

Answer

I renamed the variables from your code to more meaningful ones:

  • currentOuter tracks the current node in the outer loop
  • previousCurrentOuter tracks the previous node of the current node in the outer loop
  • currentInner tracks the current node in the inner loop
  • previousCurrentInner tracks the previous node of the current node in the inner loop
  • minimum tracks the minimum node
  • previousMinimum tracks the node previous to the minimum node

previousMinimum, previousCurrentOuter, minimum and currentOuter are required for the swapping process.

previousCurrentInner or previousCurrentOuter are needed to determine the previousMinimum node: if the minimum doesn't correspond to the current element in the outer loop, then previousCurrentInner is used, otherwise previousCurrentOuter.

Code:

public void selectionSort<T>() where T:IComparable
{
    Node<T> currentOuter = head;
    Node<T> previousCurrentOuter = null;
    Node<T> minimum;
    Node<T> previousMinimum = null;

    while (currentOuter != null) {
        minimum = currentOuter;

        Node<T> previousCurrentInner = currentOuter;
        Node<T> currentInner = currentOuter.Next;

        while (currentInner != null) {
            if (currentInner.Value.CompareTo(minimum.Value) < 0) {
                minimum = currentInner;
                previousMinimum = previousCurrentInner;
            }

            previousCurrentInner = currentInner;
            currentInner = currentInner.Next;
        }

        if (!Object.ReferenceEquals(minimum, currentOuter)) {
            Node<T> temp = minimum.Next;

            if (previousMinimum.Next != null) previousMinimum.Next = currentOuter;
            if (previousCurrentOuter != null) previousCurrentOuter.Next = minimum;

            minimum.Next = currentOuter.Next;
            currentOuter.Next = temp;
        }

        previousCurrentOuter = currentOuter;
        previousMinimum = currentOuter;
        currentOuter = currentOuter.Next;
    }
}
Comments