Ohayon Daniel Ohayon Daniel - 1 month ago 10
C# Question

How to sort an IntNode list

class IntNode
{
public int value { get; set; }
public IntNode next { get; set; }

public IntNode(int value)
{
this.value = value;
this.next = null;
}

public IntNode(int value, IntNode next)
{
this.value = value;
this.next = next;
}

public bool HasNext ()
{
return (this.next != null);
}

public override string ToString()
{
if (this.HasNext())
return this.value + " --> " + this.next;
else
return this.value + ". [end]";
}
}


If I am getting the first node of a list, how can I sort the list from smallest to highest?

Example:

for the list


5,-4,8,12,5,71,13,0


that list will be returned


-4,0,5,5,8,12,13,71


I have tried to do it but I can`t figure it out... Thanks!

What I have tried:

static IntNode Sort (IntNode head)
{
IntNode pos = head.next;
IntNode max = head;
IntNode current = head;

while (current != null)
{
while (pos != null)
{
if (pos.value > max.value) max = pos;
pos = pos.next;
}
head.next = max.next;
max.next = head;
head = max;
pos = current;
max = current;
current = current.next;
}
return head;
}


this is my homeword so pls help.

Answer

First, you need to be clear about your idea of how the algorithm for sorting is supposed to work. It helps to write it down in normal language.

From your code I see that you wander through your list and try to compare the current item with the next. That sounds like the right approach. The condition is right but the moving of values does not work in you solution.

if (pos.value > max.value)

The basic idea of sorting is moving the items. In other words :

while it is not sorted yet and while the next element is not null and if the current item is larger than the next exchange the values then move to the next element and do it again.

// in the beginning you only need one helping IntNode variable
IntNode current = head;
// and a flag to stop the sorting
bool sorted = false;

I would suggest to switch the values

//    the condition for the comparison
if (current.value > current.next.value)
{
    int temp = current.value;
    current.value = current.next.value;
    current.next.value = temp;
    // set the flag the a sort procedure has been made as indicator that it might still not be sorted
    sorted = false;
}

The rest are 2 while-loops and a boolean variable to stop the outer loop.

EDIT:

Since you seem to have figured it out on your own, for the sake of completeness here is my version of the sorting method:

public static IntNode Sort(IntNode head)
{
    IntNode current = head;
    bool sorted = false;

    while (!sorted)
    {
        // assume that at this run you actually finished your sorting job
        sorted = true;
        // set the current element to the first position
        current = head;

        while (current.next != null)
        {
            if (current.value > current.next.value)
            {
                int temp = current.value;
                current.value = current.next.value;
                current.next.value = temp;
                // apparently you found an element that was not sorted, so you might not be done yet
                sorted = false;
            }
            // move one element forward
            current = current.next;
        }
    }
    return head;
}