How to sort linked list?
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 11 of 11

Thread: How to sort linked list?

  1. #1
    Join Date
    Nov 2006
    Posts
    42

    How to sort linked list?

    Hya friends,

    I am unable to find idea how to sort linked list , can anyone please explain this to me?
    what is the mechanism , how it should work etc

    Thanks a lot)

  2. #2
    Join Date
    Apr 1999
    Posts
    27,421

    Re: How to sort linked list?

    Quote Originally Posted by DaemonAkaDevil View Post
    Hya friends,

    I am unable to find idea how to sort linked list , can anyone please explain this to me?
    what is the mechanism , how it should work etc

    Thanks a lot)
    Code:
    #include <list>
    
    int main()
    {
       std::list<int> IntList;
      //..
       IntList.sort();
    }
    Regards,

    Paul McKenzie

  3. #3
    Join Date
    Nov 2006
    Posts
    42

    Re: How to sort linked list?

    Hya , thanks Paul McKenzie , but i don't want to use any built struct or function , i have created my own linked list class , now i want to ask
    How to sort them using bubble sort or merge sort , what should be mechanism , how to implement etc

    i am beginner , so it would be very helpful if anyone could teach me .

    Thanks

  4. #4
    Join Date
    Apr 1999
    Posts
    27,421

    Re: How to sort linked list?

    Quote Originally Posted by DaemonAkaDevil View Post
    Hya , thanks Paul McKenzie , but i don't want to use any built struct or function , i have created my own linked list class , now i want to ask
    How to sort them using bubble sort or merge sort , what should be mechanism , how to implement etc
    You're asking too many non-specific questions.

    You don't know what type of sort to use -- start with that. What sort do you want to use? Whatever that is, what problem do you have in implementing that sort?

    Regards,

    Paul McKenzie

  5. #5
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,276

    Re: How to sort linked list?

    Read about lists in general here: http://www.cplusplus.com/reference/stl/list/

    If you want to sort a range inside a list (as in with the algorithm sort), well list::sort does not provide this functionality. However, you can splice a range into a new list and sort that.

    But yeah, list provides a simple sort member method you should use.
    Is your question related to IO?
    Read this C++ FAQ LITE article at parashift by Marshall Cline. In particular points 1-6.
    It will explain how to correctly deal with IO, how to validate input, and why you shouldn't count on "while(!in.eof())". And it always makes for excellent reading.

  6. #6
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,276

    Re: How to sort linked list?

    Quote Originally Posted by DaemonAkaDevil View Post
    Hya , thanks Paul McKenzie , but i don't want to use any built struct or function , i have created my own linked list class , now i want to ask
    How to sort them using bubble sort or merge sort , what should be mechanism , how to implement etc

    i am beginner , so it would be very helpful if anyone could teach me .

    Thanks
    The problem with sorting a list is that it is not random access.

    So the EASIEST way to do it would be to create an array(/vector/deque) that holds pointers to all the elements in your list. By doing this, you are basically temporarily providing random access to your list.

    Simply sort this array/vector using your favorite sorting algorithm. Make sure you sort your pointers by what they point, and not a dumb address sort though.

    Once done, all you have to do is re-order your new list by the order in your array. You may need an extra list to do it though.

    There.

    This method is NlogN, so it is time optimal for a comparison sort, but it is N in space complexity, not optimal. Do you care? In-place list sort (optimal) is MUCH more complicated.
    Is your question related to IO?
    Read this C++ FAQ LITE article at parashift by Marshall Cline. In particular points 1-6.
    It will explain how to correctly deal with IO, how to validate input, and why you shouldn't count on "while(!in.eof())". And it always makes for excellent reading.

  7. #7
    Join Date
    Nov 2006
    Posts
    42

    Re: How to sort linked list?

    Quote Originally Posted by Paul McKenzie View Post
    You're asking too many non-specific questions.

    You don't know what type of sort to use -- start with that. What sort do you want to use? Whatever that is, what problem do you have in implementing that sort?

    Regards,

    Paul McKenzie
    Ok i want to implement merge sort , i just want to know basic idea , how to implement

  8. #8
    Join Date
    Nov 2006
    Posts
    42

    Re: How to sort linked list?

    Deleted
    Last edited by DaemonAkaDevil; September 2nd, 2010 at 04:05 AM. Reason: double post

  9. #9
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,276

    Re: How to sort linked list?

    Quote Originally Posted by DaemonAkaDevil View Post
    Ok i want to implement merge sort , i just want to know basic idea , how to implement
    That information can be found on wikipedia. We won't do it for you. We can help if you need help with a specific implementation detail.
    Is your question related to IO?
    Read this C++ FAQ LITE article at parashift by Marshall Cline. In particular points 1-6.
    It will explain how to correctly deal with IO, how to validate input, and why you shouldn't count on "while(!in.eof())". And it always makes for excellent reading.

  10. #10
    Join Date
    Aug 2010
    Posts
    77

    Re: How to sort linked list?

    Merge sort is a divide and conquer strategy. You subdivide the list into small lists, typically so small that insertion sort is faster on them, then you merge them two and two, having a pointer on each picking always the smaller out (or larger if you want to sort in descending order) and putting it a new list, which will contain the merged list of the two. You do this for all pairs. You will end up with about twice as big lists, half in number. Now you do the same thing again with these, until you end up with one single list.

  11. #11
    Join Date
    Jul 2002
    Location
    Portsmouth. United Kingdom
    Posts
    2,699

    Re: How to sort linked list?

    Make sure you've fully debugged how you implement swapping or moving elements in the linked list before you start on the sort algorithm (Don't forget to take into account head and tail elements).
    "It doesn't matter how beautiful your theory is, it doesn't matter how smart you are. If it doesn't agree with experiment, it's wrong."
    Richard P. Feynman

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center