c++sortingqsort

qsort in C++ is slow

I have 9 values in the form of a matrix and need to compute the median from these values as part of a simulation process.

I use std::qsort which results in the process running slow (as this process iterates several times).

Is there a better sorting algorithm that I could use?

Solution

  • Sorting to get a median is very inefficient. You could use STL nth_element instead:

    #include <algorithm>

// Assuming you keep the elements in a vector v of size len

std::nth_element( v.begin(), v.begin()+len/2, v.end() );
median = v[len/2];

 //... or, if the elements are in a simple array v[len], then

std::nth_element( v, v+len/2, v+len );
median = v[len/2];

    Note: the nth_element will modify the vector/array v. Make a copy first if you need to preserve the original.