Can anyone please tell me that which type of sorting technique (bubble, insertion, selection, quick, merge, count...) is implemented in the std::sort() function defined in the <algorithm> header file in C++?
views:
143answers:
3
+11
A:
Most implementations of std::sort use quicksort, but some use a hybrid algorithm like introsort, which combines quicksort, heapsort and insertion sort.
The only thing the standard requires is that std::sort somehow sort the data according to the specified ordering with a complexity of approximately O(N log(N)); it is not guaranteed to be stable. Technically, introsort better meets the complexity requirement than quicksort, because quicksort has quadratic worst-case time.
Charles Salvia
2009-12-03 14:18:11
A:
Do you mean std::sort? If so it can be implemented any way they want. Its probably Quick sort but could be radix or something else. As long as it produces you a sorted list in at least O(n log n) the implementation is fine, afaik.
Goz
2009-12-03 14:20:09
There is also a complexity requirement, that the algorithm be O(n log n). This isn't much of a restriction, since almost all common sorts meet this requerment. Is does prevent the use of Bogo sort (http://en.wikipedia.org/wiki/Bogo_sort).
KeithB
2009-12-03 14:23:16
Thanks, Post edited :)
Goz
2009-12-03 14:31:44
I suppose radix sort *isn't* allowed, (even though it might be efficient for certain data types) since it does not have logarithmic complexity, as it isn't base on comparisons.
Charles Salvia
2009-12-03 14:36:38
oh right? So if it did a O(1) that would be against the rules as well? (Ignoring the impossibility of such an algorithm).
Goz
2009-12-03 14:55:13
@Goz No, an O(1) implementation would be fine. The requirements are an upper bound on the complexity. They are generally set to the most efficient know implementation, but don't preclude some new data structure or algorithm that is more efficient.
KeithB
2009-12-03 16:40:33
+6
A:
C++ Standard ISO/IEC 14882:2003
25.3.1.1 sort
template<class RandomAccessIterator> void sort(RandomAccessIterator first, RandomAccessIterator last); template<class RandomAccessIterator, class Compare> void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);1 Effects: Sorts the elements in the range [first, last).
2 Complexity: Approximately N log N (where N == last - first) comparisons on the average.
There is no information about method but complexity is always N log N.
Alexey Malistov
2009-12-03 14:26:56