Thread: Sorting a linked list (or vector)

  1. #1
    Registered User
    Join Date
    Nov 2005
    Location
    Canada
    Posts
    80

    Sorting a linked list (or vector)

    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.

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    This includes examples of sorting a linked list. While you're at it, you can read the rest of the tutorial as well.
    My best code is written with the delete key.

  3. #3
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    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.

  4. #4
    Registered User
    Join Date
    May 2003
    Posts
    1,619
    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.
    You ever try a pink golf ball, Wally? Why, the wind shear on a pink ball alone can take the head clean off a 90 pound midget at 300 yards.

  5. #5
    Registered User
    Join Date
    Nov 2005
    Location
    Canada
    Posts
    80
    Quote Originally Posted by Daved
    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.
    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()?

  6. #6
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    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.

  7. #7
    Registered User
    Join Date
    Nov 2005
    Location
    Canada
    Posts
    80
    and then i'll do a bubble sort, right?

  8. #8
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    No, that's what sort does for you. It does the sort. You just tell it how to order the objects in your container.

  9. #9
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    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...
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help with linked list sorting function
    By Jaggid1x in forum C Programming
    Replies: 6
    Last Post: 06-02-2009, 02:14 AM
  2. linked list problems (null values)
    By scwizzo in forum C++ Programming
    Replies: 2
    Last Post: 12-03-2008, 06:04 PM
  3. Linked List
    By jpipitone in forum C Programming
    Replies: 4
    Last Post: 03-30-2003, 09:27 PM
  4. Contest Results - May 27, 2002
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 06-18-2002, 01:27 PM