Bubblesort on generic list in C#

Question

I'm working with a generic list in C#, but I have a problem when I try to sort the nodes using bubble sort method.

namespace ConsoleApplication1
{    

public class GenericList
{
    private class Node
    {
        // Each node has a reference to the next node in the list.
        public Node Next;           
        public int Data;
    }

    // The list is initially empty.
    private Node head = null;

    // Add a node at the beginning of the list with t as its data value.
    public void AddNode(int t)
    {
        Node newNode = new Node();
        newNode.Next = head;
        newNode.Data = t;
        head = newNode;
    }


//list length
        public int Size()
        {
            int listsize= 0;
            Node current = head;
            while (current != null)
            {
                listsize++;
                current = current.Next;
            }
            return listsize;            
        }

        //bubble sort
        public void bubblesort()
        {
            int size = Size();

            Node current = head;

            for (int i = 1; i < size; i++)
            {
                for (int j = 0; j < size - 1; j++)
                {


                    if (current.Data > current.Next.Data && current.Next!=null)
                    {
                        int temp = current.Data;
                        current.Data = current.Next.Data;
                        current.Next.Data = temp;
                    }

                }
            }

            head = current;
        }
     }
}

When I add more than 5 nodes to the list, the bubblesort method stops working(doesnt correctly sort the list). Can anyone helpme?

Answer 1

You'll need to clarify what you mean by "stops working"... fails? Core-dumps? Doesn't correctly sort the list?

The problem is you need to be resetting current back to head+1 on each iteration of i (before the j iteration).

If you wish to move the largest value up, then j should run up from 1 to size-i (since after first pass the biggest number will be at the top - no need to check it again). Or alternatively bring the smallest value down running j down from size-1 to i.

An alternative to the nested loop method: you could use a while / boolean / loop method (outside while, boolean indicating whether a change was made, for loop internal). There's a slight performance benefit from this when the data is already somewhat in order - it'll stop processing before the nested for method (which runs the maximum number of times even if the data is already sorted).

Answer 2

C'mon guys .. cut him some slack .. this is the google generation.

btw ..

http://www.google.co.uk/search?q=C%23+bubble+sort

..would get you some great examples.

Now for what is actually wrong with your code:

This code (from above)

    Node current = head;

    for (int i = 1; i < size; i++)
    {
        for (int j = 0; j < size - 1; j++)
        {


            if (current.Data > current.Next.Data && current.Next!=null)
            {
                int temp = current.Data;
                current.Data = current.Next.Data;
                current.Next.Data = temp;
            }

        }
    }

is exactly the same as saying:

    Node current = head;
            if (current.Data > current.Next.Data && current.Next!=null)
            {
                int temp = current.Data;
                current.Data = current.Next.Data;
                current.Next.Data = temp;
            }

You do not change the "current" node, i.e. you are always sorting first and 2nd item in your list.

I won't give you the full solution afterall that's what homework is for. In the loop make sure your current is always 'j'th item in your list when it start's the inner loop and you will get correct results.

Also you are getting the swapping bit slightly incorrect, you should swap the nodes not just the data. i.e. the node's Next field and what point's to current node needs to be updated. That should get you more brownie points than just swapping the data.

Also some debugging tip: Add a Print() function like this:

public void Print()
    {
        Node current = head;
        Console.Write("List: ");
        while (current != null)
        {
            Console.Write("{0} ", current.Data);
            current = current.Next;
        }
        Console.WriteLine("");
    }

And call it in your sorting loop, it will help you understand how the list is changing between each iteration .. that helps you understand where the problem might be.

List: 3 1 50 2 5 4
List: 3 1 50 2 5 4
List: 1 3 50 2 5 4
List: 1 3 50 2 5 4
List: 1 3 2 50 5 4
List: 1 3 2 5 50 4
List: 1 3 2 5 4 50
List: 1 2 3 5 4 50
List: 1 2 3 5 4 50
List: 1 2 3 4 5 50

Oh! man .. everytime I read the code I find something new which is wrong! ...

        if (current.Data > current.Next.Data && current.Next!=null)

should be

        if (current != null && current.Next!=null && current.Data > current.Next.Data)

Your code does not crash as it does not do anything at the moment.

Hope this helps.