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;
 }
 }
 }
}

• Jeff Mercado: 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.
• h4ck.b0x7: It's just to teach myself about data structures and how they work.

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.

• h4ck.b0x7: 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!!
• Loki Astari: @h4ck.b0x7: Sure. But as a learning exercise splitting the algorithm from the container would definitely be a worth trying.

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

• h4ck.b0x7: I don't see how you think the for loop is redundant....???
• Jamal: It's redundant because linked lists are traversed until NULL is encountered (you already have that in your while loop).
• h4ck.b0x7: That should look a little better.
• Loki Astari: 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.
• Jamal: Oh yeah, I forgot about the bubble sort; I was thinking in general.

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

• h4ck.b0x7: 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.
• microtherion: 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.
• Loki Astari: Bubble sort is also very good for short list. In the best case it is also O(n) (if the list is already sorted).
• Loki Astari: 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.
• h4ck.b0x7: Which variable names would you advocate changing Loki??