Ohayon Daniel - 1 year ago 52

C# Question

`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?

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 Source

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;
}
```