-
April 9th, 2011, 06:26 PM
#1
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());
-
April 9th, 2011, 06:29 PM
#2
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());
-
April 9th, 2011, 06:42 PM
#3
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.
-
April 9th, 2011, 06:47 PM
#4
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.
-
April 9th, 2011, 06:48 PM
#5
Re: What's the time complexity of sorting a list using list.sort()
I got it Russco,
Thanks a lot!
-
April 11th, 2011, 03:29 AM
#6
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 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.
-
April 11th, 2011, 09:36 AM
#7
Re: What's the time complexity of sorting a list using list.sort()
Originally Posted by ertss
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.
-
April 11th, 2011, 09:40 AM
#8
Re: What's the time complexity of sorting a list using list.sort()
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.
-
April 11th, 2011, 09:58 AM
#9
Re: What's the time complexity of sorting a list using list.sort()
Originally Posted by laserlight
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?
-
April 11th, 2011, 10:13 AM
#10
Re: What's the time complexity of sorting a list using list.sort()
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.
-
April 11th, 2011, 10:31 AM
#11
Re: What's the time complexity of sorting a list using list.sort()
Originally Posted by laserlight
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.
-
April 11th, 2011, 10:35 AM
#12
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.
-
April 11th, 2011, 10:51 AM
#13
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²(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 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.
-
April 11th, 2011, 11:18 AM
#14
Re: What's the time complexity of sorting a list using list.sort()
Originally Posted by monarch_dodra
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
-
April 11th, 2011, 12:09 PM
#15
Re: What's the time complexity of sorting a list using list.sort()
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.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|