5
\$\begingroup\$

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;
            }
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ If you asked me, sorting a linked list is rather pointless. If you needed to sort a list, you wouldn't use a linked list. There are other list types better suited for sorting and a linked list isn't one of them. \$\endgroup\$ – Jeff Mercado Jun 1 '13 at 20:51
  • \$\begingroup\$ It's just to teach myself about data structures and how they work. \$\endgroup\$ – h4ck.b0x7 Jun 2 '13 at 2:11
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thank you very much Loki!!! Like you mentioned above, the STL does this for us. I was doing it just as a learning experience. I appreciate your input!! \$\endgroup\$ – h4ck.b0x7 Jun 2 '13 at 23:57
  • \$\begingroup\$ @h4ck.b0x7: Sure. But as a learning exercise splitting the algorithm from the container would definitely be a worth trying. \$\endgroup\$ – Martin York Jun 5 '13 at 1:06
2
\$\begingroup\$

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).

\$\endgroup\$
  • 1
    \$\begingroup\$ I don't see how you think the for loop is redundant....??? \$\endgroup\$ – h4ck.b0x7 Jun 2 '13 at 1:36
  • \$\begingroup\$ It's redundant because linked lists are traversed until NULL is encountered (you already have that in your while loop). \$\endgroup\$ – Jamal Jun 2 '13 at 4:55
  • \$\begingroup\$ That should look a little better. \$\endgroup\$ – h4ck.b0x7 Jun 2 '13 at 10:50
  • \$\begingroup\$ A doubly nested loop is required for bubble sort. Each iteration of the inner loop moves one item to the top of the list. Thus you need to use the outer loop n times to bubble all the values into the correct order. \$\endgroup\$ – Martin York Jun 2 '13 at 17:37
  • \$\begingroup\$ Oh yeah, I forgot about the bubble sort; I was thinking in general. \$\endgroup\$ – Jamal Jun 2 '13 at 17:53
0
\$\begingroup\$

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).

\$\endgroup\$
  • \$\begingroup\$ What kind of naming scheme do you recommend?? I know the bubble sort isn't the most efficient, but I was doing this just to teach myself how data structures work. \$\endgroup\$ – h4ck.b0x7 Jun 2 '13 at 1:39
  • \$\begingroup\$ Three naming schemes I am familiar with are (1) suffix member variables with an underscore (head_); used at Google, for instance. (2) prefix member variables with m_ (m_Head); also widely used, I believe. (3) prefix member variables with an f (fHead); used at Apple, for instance. Any of these is preferable over no differentiation at all, in my opinion. \$\endgroup\$ – microtherion Jun 2 '13 at 15:01
  • 1
    \$\begingroup\$ Bubble sort is also very good for short list. In the best case it is also O(n) (if the list is already sorted). \$\endgroup\$ – Martin York Jun 2 '13 at 17:33
  • \$\begingroup\$ PS. Totally disagree with using prefix/suffix to distinguish members from local variables. If you need to do this then you have already made bad choices in the names of you members. To me adding the prefix/suffix is just a code smell that there are other fundamental problems. I do agree that you (the original poster) has chosen some bad names that makes it confusing. The best way is to choose variable names that make it more obvious what you are doing. \$\endgroup\$ – Martin York Jun 2 '13 at 17:53
  • \$\begingroup\$ Which variable names would you advocate changing Loki?? \$\endgroup\$ – h4ck.b0x7 Jun 2 '13 at 23:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.