hi everyone,

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

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

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/

The C

The C++

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/

Last edited on

Thanks!

I didn't knew it. Learned something more.

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

I didn't knew it. Learned something more.

closed account (*D4S8vCM9*)

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

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.
Topic archived. No new replies allowed.