Bubblesort implementation using linked-list only partially works

Question

I am trying to use bubble sort to sort a list of items. I am aware that this is not the most effective method of sorting; however, I require this method to work before moving on to better things. My current code partially sorts a list, but I cannot see what I am doing wrong.

public class ListComponents
{
    public int Priority;
    public string Name;
    public ListComponents Next;
}

public void bubblesort()
{
    ListComponents Current = Head; 
    int temp = 0;
    bool swapped = true;

    while (swapped)
    {
        Print(); // Debug Function to print each swap
        Current = Head.Next; // RESET CURRENT TO HEAD + 1 ON EACH ITERATION?
        swapped = false;
        for (int sort = 0; sort < (size - 1); sort++) //Size defined as # of items in list
        {
            if (Current != null && 
                Current.Next != null && 
                Current.Priority> Current.Next.Priority)
            {
                temp = Current.Priority;
                Current.Priority= Current.Next.Priority;
                Current.Next.Priority= temp;
                Current = Head; // POTENTIAL ISSUE?
                swapped = true;
            }
        }
    }
}

My debug print function shows the following, showing how the values are almost in order:

List: 4 2 1 3  (Inital List Order)
List: 1 4 2 3  (First Swap)
List: 1 2 4 3  (Second Swap)

The issue seems to be with setting the 'Current' value, although I cannot see where this is not working.

This doesn't seem to be the entire code sample. I see a variable `size` which has not been defined anywhere; will you please edit to add the required code? — feralin, Mar 25 '13 at 21:33
The line marked POTENTIAL ISSUE certainly seems to be a pretty strong clue that something is wrong there. — Eric Lippert, Mar 25 '13 at 21:36
Also, your debug output is clearly showing that something is deeply wrong. The correct output for a bubble sort starting with 4-2-1-3 is 2-1-3-4 after the first pass, then 1-2-3-4 after the second pass. — Eric Lippert, Mar 25 '13 at 21:39
@EricLippert - the line 'Current = Head;' is indeed wrong i think. But cant figure out what this should be. — ZeeeeeV, Mar 25 '13 at 21:40
Looking closer at your code: you seem to be iterating over a linked list and at the same time mixing that with the code for iterating over an array. This seems a bit messed up. — Eric Lippert, Mar 25 '13 at 21:44
@EricLippert if I had to guess, I think this code might have started off as C++ and then got transliterated to C#. Just a hunch. — Reacher Gilt, Mar 25 '13 at 21:47
@EricLippert i was under the impression that it doesn't matter if the list is an array or a linked list, the methodology is the same? Or am i wrong there?. Is there a different implementation for a linkedlist? — ZeeeeeV, Mar 25 '13 at 21:49
@ZeeeeeV But swapping two items in an array is much easier. No need to deal with *next* s — I4V, Mar 25 '13 at 21:52
You might want to start off by working your way through the inner loop and paying attention to which element of the list Current points to. It took a bit to work out how your first element was ever getting swapped. — ThatBlairGuy, Mar 25 '13 at 21:55
@ZeeeeeV: The algorithm is the same, yes. But typically if you are working with a linked list then you do not know the size, so it seems very odd to be referencing the size. The key thing to understand is that you need to know *when you are on the last element*. You can do that with an array by checking when you are at size - 1. You can do that with a linked list by checking when you are at current.Next == null. — Eric Lippert, Mar 25 '13 at 21:58

score 13 · Answer 1 · edited Mar 25 '13 at 23:11

My advice: start over. This is a mess.

Here's how I would tackle problems like this when I was a beginner. Start by writing the code in pseduo-code:

void BubbleSort(ListComponent head)
{
    if the list is of zero length then it is already sorted, so return
    if the list is of length one then it is already sorted, so return
    Otherwise, the list is of length two or more. Therefore we know that
    a first item exists and a second-last item exists.
    Our strategy is: run down the list starting with the first item
    and ending with the second-last item. If at any time the current
    item and the one following it are out of order, swap their elements.
    If we made no swaps then the list is sorted, return. 
    If we made one or more swaps then the list might not be sorted, so 
    run down the list again.
}

OK, now we can start translating that into code.

void BubbleSort(ListComponent head)
{
    // if the list is of zero length then it is already sorted, so return
    if (head == null) return; 

    // if the list is of length one then it is already sorted, so return
    if (head.Next == null) return; 

    // Otherwise, the list is of length two or more. Therefore we know that
    // a first item exists and a second-last item exists.

    // Our strategy is: run down the list starting with the first item
    // and ending with the second-last item. 

    for (ListComponent current = head; 
        current.Next != null; 
        current = current.Next)
    {

        If at any time the current item and the one following it
        are out of order, swap their elements.
    }

    If we made no swaps then the list is sorted, return. 
    If we made one or more swaps then the list might not be sorted, so 
    run down the list again.
}

OK, I've translated some of that English into code. Can you translate the rest?

Thats the best tutorial/advice i have received in a long time. I will defenetly be using pseduo-code in the future to plan what i am trying to achieve. I implemented (in below answer) maybe slightly different to yours, however, works perfectly. Thanks!. — ZeeeeeV, Mar 25 '13 at 22:19
@ZeeeeeV: Awesome! Your solution looks good. Two more things you can do to improve the likelihood that you get it correct are (1) test cases, and (2) postconditions. A "postcondition" is the thing that has to be true when the method is done; the post condition of a sort is that *the number of out-of-order elements is zero*. You can then write a little method that takes a list and tells you true if there are zero out-of-order elements, false otherwise. After you sort your list, call `Debug.Assert(ZeroOutOfOrderElements(head))`. Now your code will automatically fail if you violate the condition. — Eric Lippert, Mar 25 '13 at 22:27
@ZeeeeeV: Also, you see that by taking the early-out for the trivial cases I not only made the program fast for those cases, I greatly simplified the logic in the loop. If you know that the list has two items then you don't even need to check for the cases where current is null or current.next is null. Here's another example of a situation where I used these techniques to write correct code: http://stackoverflow.com/questions/921180/how-can-i-ensure-that-a-division-of-integers-is-always-rounded-up/926806#926806 — Eric Lippert, Mar 25 '13 at 22:29

score 0 · Answer 2 · answered Aug 02 '14 at 01:30

Another example with a simple class with 2 properties. This is NOT for arrays but for a simple class simulating pointers... Made just for fun !

class MyLinkedList
{
MyLinkedList nextNode;
int data;

public void OrderListBubbleAlgoritm(ref MyLinkedList head)
{
    bool needRestart = true;
    MyLinkedList actualNode = head; //node Im working with        
    int temp;

    while (needRestart)
    {
        needRestart = false;
        actualNode = head;
        while (!needRestart && actualNode.nextNode != null)
        {
            if (actualNode.nextNode.data >= actualNode.data) //is sorted
            {
                actualNode = actualNode.nextNode;
            }
            else
            {
                //swap the data
                temp = actualNode.data;
                actualNode.data = actualNode.nextNode.data;
                actualNode.nextNode.data = temp;

                needRestart = true;
            }
        }
    }
}
}

Remember to use bubble sorting just with small quantity of data.
It's performance is: O(n^2)

Bubblesort implementation using linked-list only partially works

2 Answers2