Sunday, January 19, 2014

Sort a linked list using bubble sort

Merge sort looks like a best choice for sorting the linked list.At a first appearance, merge sort may be a good  selection since the middle element is required to subdivide the given list into 2 halves, but we can easily solve this problem by moving the nodes alternatively to 2 lists.
We have discussed the sorting options for linked list here. Here we will discuss about bubble sort

Pseudocode for bubble sort:
public void sortList()
{
    if (isEmpty())
    {
        System.out.println("An empty list is already sorted");
    }
    else if (getHead().getNext() == null)
    {
        System.out.println("A one-element list is already sorted");
    }
    else
    {
        Node current = getHead();
        boolean swapDone = true;
        while (swapDone)
        {
            swapDone = false;
            while (current != null)
            {
                if (current.getNext() != null && current.getData().getSurname().compareTo(current.getNext().getData().getSurname()) >0)
                {
                    CustomerFile tempDat = current.getData();
                    current.setData(current.getNext().getData());
                    current.getNext().setData(tempDat);
                    swapDone = true;
                }
                current = current.getNext();
            }
            current = getHead();
        }
    }
}

Source-http://stackoverflow.com/questions/7168164/sorting-linked-lists-in-c/7168300#7168300

0 comments:

Post a Comment