Linked List Sorting Algorithm

Question

I was working on a sorting algorithm for my linked list implementation and wanted to get other people's input/comments/critique. What do you think of it in all aspects, including style?

I was told that it is preferred to use a bool type for the changeFlag instead of using an int as it makes it more readable. Thoughts?

void LinkedList::sort()
{
    if (head != 0)
    {
        Node* current = head;
        Node* prev = 0;
        Node* tempNode = 0;
        bool changeFlag = false;
        for (int i = 0; i < length; i++)
        {
            while (current->next != 0)
            {
                tempNode = current->next;

                if (current->value > tempNode->value)
                {
                    changeFlag = true;
                    current->next = tempNode->next;
                    tempNode->next = current;
                    if (prev != 0)
                        prev->next = tempNode;
                    prev = tempNode;
                    if (head == current)
                        head = tempNode;
                    if (current->next == 0)
                        end = current;
                }
                else
                {
                    prev = current;
                    current = current->next;
                }
            }
            if (changeFlag == false)
                break;
            else
            {
                prev = 0;
                current = head;
                changeFlag = false;
            }
        }
    }
}

Answer 1

What I would take away from this is how the standard library does this.

It disassociates sorting algorithms from specific container types (by using iterators). Then you can write the sorting algorithm in a way that is independent of the actual container type.

What I dislike about your code is that when you move elements you basically re-order the list (you actually move the nodes). This is a complex operation taking many checks. Personally I would leave the actual nodes where they are and move the values between nodes. std::swap() can be used for this.

This:

               current->next = tempNode->next;
                tempNode->next = current;
                if (prev != 0)
                    prev->next = tempNode;
                prev = tempNode;
                if (head == current)
                    head = tempNode;
                if (current->next == 0)
                    end = current;

Can be replaced with:

                swap(current->value, tempNode->value);

With C++ new move semantics this is now very efficient.

EDIT: I was told that it is preferred to use a bool type for the changeFlag instead of using an int as it makes it more readable?? Thoughts?

Yes. Use the correct type. bool is a truth value it imparts meaning to the person reading the code. Humans need that extra meaning to help them understand the code better.

Answer 2

Giant problem that I see: your for loop is completely redundant. You go through the entire list in the inner while loop and then just continue checking the condition N times before you finish the outer for loop.

I think that you're taking an approach which is overly complicated for the given scenario. Because you're using a linked list specifically, I'd highly suggest using a merge sort, because you have the ability to easily separate the individual parts of the list. This would not only reduce the size of your code dramatically but it would also make it much more readable.

For you specifically, I'd suggest commenting your code more. And I mean, commenting the purpose of code, not what it does (// loop through list is unhelpful). If you think that they're unnecessary, do them anyway and then strip them once you're satisfied with the algorithm. That way, while you're writing code, you'll be sure that you know what different parts do (like this redundant for loop).

Answer 3

One of the problems of this code is that it implements a bubble sort, which is very inefficient ( O(n^2) running time) for large lists. As @AlexCharron suggests, use a merge sort, or alternatively, copy the list into a vector, sort that, and rebuild the list.

Another problem is that your naming convention does not distinguish between locals (e.g. prev) and data members (e.g. head).