CODEWITHSUNDEEP
c++linked-listlogicbubble-sort
monkey doodle
monkey doodle

Reputation: 700

bubble sort linked list not sorting

Why won't my bubble sort algorithm sort the linked list? When given a list, and calling the method, it will output the same list. What's wrong with my current logic inside my for loop? 

private:
    IntNode *head, *tail;

node structure:

struct IntNode
{
    int data;
    IntNode * next;
};

bubble sort method:

void NodeSLList::SortList()
{
    if (head == NULL || head->next == NULL)
        return;

    IntNode * current = head;
    IntNode * nextElement = current->next;
    IntNode * temp = NULL;

    int changed = 1;


    while (changed)
    {
        changed = 0;
        for (current; (current != NULL) && (nextElement = NULL); )
        {
            if (current->data > nextElement->data)
            {
                temp = current->next;
                current->next = nextElement->next;
                nextElement->next = temp;
                changed = 1;
            }
            current = current->next;
            nextElement = nextElement->next;
        }

    }

}

Upvotes: 0

Views: 167

Answers (2)

sp2danny
sp2danny

Reputation: 7687

The problem is caused by assigning in the for-loop, instead of comparing.

If you are implementing a linked list, may I suggest using a sentry, instead of a head
and NULL as end. This removes all 'corner-cases' during inserts and removes.
A sentry-node always exists, contains no data, points to the first item,
and the last item points to it.

May I also suggest using Mergesort, it works well for linked list, running in O(NlogN),
and having no space overhead. You can find an implementation here

Upvotes: 1

The Dark
The Dark

Reputation: 8514

Try running it through a debugger. If you look at the value of current on the second time round the changed loop, you will see that current is still null, so the second time round the changed loop it will not go through the current loop.

Upvotes: 0

Related Questions