Batuhan Aydın - 1 year ago 170
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> compare;
Node<T> temp;
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;

{
sorted.Next = minimum; // Adding minimum node to sorted part
}

first = first.Next;
}

}
``````

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> 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;
}
}
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download