sort() or qsort()

[TAZ757]

hi everyone,

my question is what function sort or qsort is faster, and what complexy they are.

[tcs]

qsort: Average: O(n log(n))
sort: I don't know any algorithm called "sort".

[Duthomhas]

You can use "google" to get this information.

The C qsort() complexity is not specified, as it can be any algorithm (not necessarily quicksort).

The C++ std::sort() algorithm is usually an introsort, and should have a complexity of n log n.

If you are trying to choose which algorithm to use, go with the C++ one. You'd be wasting your time trying to optimize over that.

More on sorting can be found here. (Sorry it isn't all finished yet.)
http://www.cplusplus.com/faq/sequences/sequencing/sort-algorithms/

Remember, if your program is running slow, use a profiler to figure out exactly where it is running slowly.

Hope this helps.

[edit]
http://www.cplusplus.com/reference/algorithm/sort/
http://www.cplusplus.com/reference/cstdlib/qsort/

[tcs]

Thanks!

The C qsort() complexity is not specified, as it can be any algorithm (not necessarily quicksort).

I didn't knew it. Learned something more.

[D4S8vCM9]

@Duoas: thanks for the faq-link, not easy to find from "normal" navigation on cplusplus.com, but useful. Will bookmark it :-D

[Cubbi]

In practice, they have the same, optimal, algorithmic complexity (n log n) but sort() is often several times faster than qsort() on equivalent data due to inlining. For example, default sort() on a container of integers will be compiled to use std::less<int>::operator(), which will be inlined and the internals of std::sort() will be comparing the integers directly. On the other hand, qsort() will be making an indirect call through a function pointer for every comparison. Sometimes compilers can optimize through that, but it's nowhere as common.