What's the time complexity of sorting a list using list.sort()
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 2 12 LastLast
Results 1 to 15 of 17

Thread: What's the time complexity of sorting a list using list.sort()

  1. #1
    Join Date
    Dec 2010
    Posts
    32

    Red face What's the time complexity of sorting a list using list.sort()

    Hi all,

    Could any tell me what's the difference between the two kinds of sorting function listed below?
    Do they all have nlogn time complexity? It looks like the later one is in the algorithm library while the first sort
    seems to be defined in the list header file? Thanks a lot.

    Code:
    #include <list>
    ... ...
    list<int> ilist;
    ......
    ......
    ilist.sort();
    and

    Code:
    #include <algorithm>
    #include <vector>
    ... ...
    vector<int> ivec;
    ... ...
    ... ...
    sort(ivec.begin(), ivec.end());

  2. #2
    Join Date
    Dec 2010
    Posts
    32

    Re: What's the time complexity of sorting a list using list.sort()

    And it looks like the second sort cannot be used on list type.
    If i do something like this, it doesn't work... why is that?
    Code:
    #include <algorithm>
    #include <list>
    ... ...
    list<int> ilist;
    ... ...
    ... ...
    sort(ilist.begin(), ilist.end());

  3. #3
    Join Date
    Nov 2008
    Location
    England
    Posts
    748

    Re: What's the time complexity of sorting a list using list.sort()

    Both are I think O(n log n).

    std::sort requires random access iterators, list only provides bidirectional iterators thats why std::sort wont work with lists.
    Get Microsoft Visual C++ Express here or CodeBlocks here.
    Get STLFilt here to radically improve error messages when using the STL.
    Get these two can't live without C++ libraries, BOOST here and Loki here.
    Check your code with the Comeau Compiler and FlexeLint for standards compliance and some subtle errors.
    Always use [code] code tags [/code] to make code legible and preserve indentation.
    Do not ask for help writing destructive software such as viruses, gamehacks, keyloggers and the suchlike.

  4. #4
    Join Date
    Nov 2008
    Location
    England
    Posts
    748

    Re: What's the time complexity of sorting a list using list.sort()

    Both are I think are amortized O(n log n).

    std::sort requires random access iterators but list only provides bidirectional iterators which is why list provides its own sort member function.
    Get Microsoft Visual C++ Express here or CodeBlocks here.
    Get STLFilt here to radically improve error messages when using the STL.
    Get these two can't live without C++ libraries, BOOST here and Loki here.
    Check your code with the Comeau Compiler and FlexeLint for standards compliance and some subtle errors.
    Always use [code] code tags [/code] to make code legible and preserve indentation.
    Do not ask for help writing destructive software such as viruses, gamehacks, keyloggers and the suchlike.

  5. #5
    Join Date
    Dec 2010
    Posts
    32

    Re: What's the time complexity of sorting a list using list.sort()

    I got it Russco,
    Thanks a lot!

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

    Re: What's the time complexity of sorting a list using list.sort()

    If you want a bit of background, there are two major sort alogrithms:
    -Quick sort
    -Merge sort

    Quick sort is an all around good sorting algorithm, that performs quite well against almost everything. This is usually the algorithm of choice for the STL's "sort" implementation (or the Introsort variant). It does require random access though.

    Merge sort is usually quite good, but not quite as good as quick sort. Its advantages are that it can work with bidirectional iterators (though the stl does not allow it). What makes merge sort interesting is that under certain circumstances, it can have phenomenal performance. In particular, it works very well with containers that handle the "merge"/"splice" operation.

    Taken these two considerations, it was decided that list would have its own sort (amongst other algorithms).
    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
    May 2009
    Posts
    2,413

    Re: What's the time complexity of sorting a list using list.sort()

    Quote Originally Posted by ertss View Post
    Do they all have nlogn time complexity? It looks like the later one is in the algorithm library while the first sort seems to be defined in the list header file?
    That's right, list::sort has O(N*logN) complexity too, at least according to this reference,

    http://www.cplusplus.com/reference/stl/

    (click on list at the cross-section of <list> and unique members in the Member map).

    If you find yourself performing lots of sorting on lists it may be the wrong data structure. For example a map sometimes is the better choise. It's kept sorted at all times.
    Last edited by nuzzle; April 11th, 2011 at 10:31 AM.

  8. #8
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,261

    Re: What's the time complexity of sorting a list using list.sort()

    Quote Originally Posted by nuzzle
    But note that to reach this low complexity the implementation must "cheat" somehow. The most common "trick" is to first turn the list into an ordinary array, sort it and then turn it back into a list again.
    It is not necessary to "cheat", as monarch_dodra pointed out.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  9. #9
    Join Date
    May 2009
    Posts
    2,413

    Re: What's the time complexity of sorting a list using list.sort()

    Quote Originally Posted by laserlight View Post
    It is not necessary to "cheat", as monarch_dodra pointed out.
    So you claim it's possible to sort a sequencial access sequence at O(N*logN) complexity?

    The last time I looked it was only possible by somehow providing random access to the sequence (which is what I called cheating).

    Do you have a reference?

  10. #10
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,261

    Re: What's the time complexity of sorting a list using list.sort()

    Quote Originally Posted by nuzzle
    So you claim it's possible to sort a sequencial access sequence at O(N*logN) complexity?

    The last time I looked it was only possible by somehow providing random access to the sequence (which is what I called cheating).

    Do you have a reference?
    Consider merge sort on an array: random access can be used to jump to the mid point so as to partition; other uses of random access do not provide any advantage over accessing the elements sequentially. But whether we jump to the mid point with random access or iterate to reach the mid point, we would still do work in linear time due to the merging. Therefore, we can accomplish merge sort of a linked list with the same time complexity.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  11. #11
    Join Date
    May 2009
    Posts
    2,413

    Re: What's the time complexity of sorting a list using list.sort()

    Quote Originally Posted by laserlight View Post
    But whether we jump to the mid point with random access or iterate to reach the mid point, we would still do work in linear time due to the merging. Therefore, we can accomplish merge sort of a linked list with the same time complexity.
    Well, I'll have to check this out. I remove the "cheating" part of my post.

  12. #12
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,261

    Re: What's the time complexity of sorting a list using list.sort()

    If you would like to analyse something more concrete than my pedestrian reasoning, take a look at this article on Mergesort for Linked Lists.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  13. #13
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,290

    Re: What's the time complexity of sorting a list using list.sort()

    If the merge sort is done "bottom up", you don't even need to linearly walk through the list. You just merge as you walk through. It does require a bit more book-keeping and recursion to avoid backtracking.

    One thing to note is that a list's sort is stable, and guaranteed O(n.log(n)), with 0(1) space overhead.

    The standard algorithm counterpart stable_sort (rather than sort) will give n log(n) only if O(n) space can be acquired. If the memory can't be acquired, then stable_sort degrades to O(n.log&#178;(n)).

    This is due to the inherent difference between algorithm::inplace_merge and list::merge's.

    These two differences make lists a very interesting container to use, instead of a classic RA container, when stable sort is involved (IMO).
    Last edited by monarch_dodra; April 11th, 2011 at 10:56 AM. Reason: punctuation
    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.

  14. #14
    Join Date
    Jul 2005
    Location
    Netherlands
    Posts
    2,012

    Re: What's the time complexity of sorting a list using list.sort()

    Quote Originally Posted by monarch_dodra View Post
    The standard algorithm counterpart stable_sort (rather than sort) will give n log(n) only if O(n) space can be acquired. If the memory can't be acquired, then stable_sort degrades to O(n.log˛(n)).

    This is due to the inherent difference between algorithm::inplace_merge and list::merge's.

    These two differences make lists a very interesting container to use, instead of a classic RA container, when stable sort is involved (IMO).
    Interesting. But wouldn't it be fair to state that the space requirement of stable_sort's fast variant can be met when elements are stored in a vector, given that they can also be stored in a list, which itself has an O(n) space overhead? In other words, if we store the elements in a vector instead of a list, wouldn't the difference in memory used by those containers be enough for stable_sort's fast variant?
    Cheers, D Drmmr

    Please put [code][/code] tags around your code to preserve indentation and make it more readable.

    As long as man ascribes to himself what is merely a posibility, he will not work for the attainment of it. - P. D. Ouspensky

  15. #15
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,261

    Re: What's the time complexity of sorting a list using list.sort()

    Quote Originally Posted by D_Drmmr
    But wouldn't it be fair to state that the space requirement of stable_sort's fast variant can be met when elements are stored in a vector, given that they can also be stored in a list, which itself has an O(n) space overhead?
    By O(n) space overhead, I think that you are talking about the fact that a linked list would need at least a pointer for each node, in addition to the actual data stored. However, this space overhead could be relatively small, depending on the size of each individual node's data, whereas the space overhead of an extra vector would be relatively large. Granted, we could sort a vector of pointers to elements of the vector instead, but that would not be sorting the original vector.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

Page 1 of 2 12 LastLast

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