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());
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());
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.
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.
Re: What's the time complexity of sorting a list using list.sort()
I got it Russco,
Thanks a lot!
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).
Re: What's the time complexity of sorting a list using list.sort()
Quote:
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.
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.
Re: What's the time complexity of sorting a list using list.sort()
Quote:
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?
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.
Re: What's the time complexity of sorting a list using list.sort()
Quote:
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.
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.
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).
Re: What's the time complexity of sorting a list using list.sort()
Quote:
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?
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.
Re: What's the time complexity of sorting a list using list.sort()
I thought the O(n) space overhead for merge sort was when operating
on arrays. For linked list it is a constant amount.
If I recall correctly, the STL that shipped with VC++6 used 16 "empty"
linked lists, but Dinkumware suggested increasing to 32.
Re: What's the time complexity of sorting a list using list.sort()
Quote:
Originally Posted by
laserlight
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.
Yes, that's what I was referring to.
Quote:
Originally Posted by
laserlight
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.
Ok, I get it now. I was thinking that merge sort on a vector could just keep pointers to the original data and sort them. But then indeed the original data still wouldn't be sorted.
