Printable View
There's a linked list "LIST" containing several nodes. Each node holds a value for an item, lets say x (can be 0 or a positive integer). What's the best way to sort these nodes with respect to x (in ascending order)?
For clarity, if there's something like the following:
NodeA (x=1) -> NodeB (x=4) -> NodeC (x=2)
the output should be: NodeA, NodeC, NodeB
Any help is greatly appreciated.
This includes examples of sorting a linked list. While you're at it, you can read the rest of the tutorial as well. ;)
If it is a standard library list, use the list's sort method. If it is a vector, use sort() from <algorithm>. If it is your own list type, then you have to create your own sorting code that implements a sort algorithm.
As a note, to use the methods Daved said you'll need to implement an operator< for your class type, which uses the criteria you choose.
I looked it up and it doesn't look like it works with vectors containing more than one item. e.g. each node in the vector has a number of items, and I would like to sort the vector by one of them. Any chances you know how this is done using sort()?Quote:
Originally Posted by Daved
Yes, you have to define your own sorting predicate. If you will always sort your nodes by the same criteria, then you can overload operator< as Cat mentioned. It isn't too difficult, just one function: bool operator<(const MyClass& left, const MyClass& right);. Make sure you return true only if left is less than right. That means you have to return false if they are equal. If you are comparing integers it should be simple.
If you want to be able to sort by different values at different times, you can do that as well. How complicated it is depends on your situation. If your class has two values, like name and id. You can create one sort that sorts by name and one that sorts by Id. For example, bool SortMyClassByName(const MyClass& left, const MyClass& right) and bool SortMyClassById(const MyClass& left, const MyClass& right).
If you use operator<, then it will be called automatically. If you use a sorting function like SortMyClassByName, then you have to specify that in the call to sort as the third parameter.
and then i'll do a bubble sort, right?
No, that's what sort does for you. It does the sort. You just tell it how to order the objects in your container.
std::sort is much faster than bubble sort for large datasets. I'm damn surprised by how many supposedly competent programmers still prefer bubble sort over other modern algorithms. It's like that's the only thing they teach in CS 101...