CODEWITHSUNDEEP
c++sorting
farah
farah

Reputation: 93

the number of comparisons done in std::sort()

How can I count the number of comparisons that happens in The standard C++ STL sort function when sorting a vector with n integers?

Upvotes: 1

Views: 1055

Answers (2)

ShadowRanger
ShadowRanger

Reputation: 155353

To complement the observational approach, you can read the documentation. On complexity, std::sort must be:

O(N·log(N)), where N = std::distance(first, last) comparisons on average. (until C++11)

O(N·log(N)), where N = std::distance(first, last) comparisons. (since C++11)

Obviously, big-O notation can mask some constant factors, but in general, expect it to be proportionate to N·log(N) (where the log is base 2, like all good CS logs).

Upvotes: 2

Thomas Russell
Thomas Russell

Reputation: 5970

One quick, non-intrusive way is to use a lambda function. you can use a lambda if you are using C++11 or above, so something like the following:

unsigned int numComparisons = 0U;
std::vector<unsigned int> someContainer;
// Fill container, etc.
std::sort( 
    std::begin(someContainer), 
    std::end(someContainer),
    [&numComparisons]( unsigned int lhs, unsigned int rhs ) 
    {
        ++numComparisons;
        return lhs < rhs;
    }
);

std::cout << numComparisons << " comparisons were performed in std::sort" << std::endl;

Upvotes: 7

Related Questions