Is there a significant difference between the following two approaches? Way 1 uses sort or partial_sort, depending on the size of the vector while way 2 always uses partial_sort. I find way 2 more appealing because my predicate is a bit more complicated than in the example, so I don't want to repeat it. But I wonder if partial_sort performs worse than sort because it is not meant to be used to sort the whole range, which is why I tend to use way 1.
int main()
{
std::vector<double> vec;
vec.push_back(1.0);
vec.push_back(3.0);
vec.push_back(2.0);
vec.push_back(5.0);
vec.push_back(4.0);
vec.push_back(9.0);
const size_t numBest = 3;
const size_t numTotal= vec.size();
#if WAY1
if (numTotal < numBest)
{
std::sort(vec.begin(), vec.end(), std::not2(std::less<double>()));
}
else
{
std::partial_sort(vec.begin(), vec.begin() + numBest, vec.end(), std::not2(std::less<double>()));
vec.resize(numBest);
}
#elif WAY2
{
const size_t numMiddle = numTotal < numBest ? numTotal : numBest;
std::partial_sort(vec.begin(), vec.begin() + numMiddle, vec.end(), std::not2(std::less<double>()));
vec.resize(numMiddle);
}
#endif
// now vec contains the largest numBest results.
return 0;
}
Some testing yielded that partial_sort is significantly worse (factor of 4 in my usecase) than sort if if has to sort the whole range. This indicates that way 1 is to be preferred. It seems that partial_sort is only meant for sorting a small fraction of the whole range. I tested in Visual Studio 2010.
According to sgi doc, partial_sort uses heapsort, sort uses introsort:
partial_sort(first, last, last) has the effect of sorting the entire range [first, last), just like sort(first, last). They use different algorithms, however: sort uses the introsort algorithm (a variant of quicksort), and partial_sort uses heapsort. See section 5.2.3 of Knuth (D. E. Knuth, The Art of Computer Programming. Volume 3: Sorting and Searching. Addison-Wesley, 1975.), and J. W. J. Williams (CACM 7, 347, 1964). Both heapsort and introsort have complexity of order N log(N), but introsort is usually faster by a factor of 2 to 5.
So, it is normal partial_sort is 4 times slower than sort.
I have checked my VS2017 library, and found the implementation of partial_sort and sort. And it is similar with SGI.
template<class _RanIt,
class _Pr> inline
void _Partial_sort_unchecked(_RanIt _First, _RanIt _Mid, _RanIt _Last,
_Pr& _Pred)
{ // order [_First, _Last) up to _Mid, using _Pred
if (_First == _Mid)
return; // nothing to do, avoid violating _Pop_heap_hole_unchecked preconditions
_Make_heap_unchecked(_First, _Mid, _Pred);
for (_RanIt _Next = _Mid; _Next < _Last; ++_Next)
if (_DEBUG_LT_PRED(_Pred, *_Next, *_First))
{ // replace top with new largest
_Iter_value_t<_RanIt> _Val = _STD move(*_Next);
_Pop_heap_hole_unchecked(_First, _Mid, _Next, _STD move(_Val), _Pred);
}
_Sort_heap_unchecked(_First, _Mid, _Pred);
}
template<class _RanIt,
class _Diff,
class _Pr> inline
void _Sort_unchecked1(_RanIt _First, _RanIt _Last, _Diff _Ideal, _Pr& _Pred)
{ // order [_First, _Last), using _Pred
_Diff _Count;
while (_ISORT_MAX < (_Count = _Last - _First) && 0 < _Ideal)
{ // divide and conquer by quicksort
pair<_RanIt, _RanIt> _Mid =
_Partition_by_median_guess_unchecked(_First, _Last, _Pred);
_Ideal /= 2, _Ideal += _Ideal / 2; // allow 1.5 log2(N) divisions
if (_Mid.first - _First < _Last - _Mid.second)
{ // loop on second half
_Sort_unchecked1(_First, _Mid.first, _Ideal, _Pred);
_First = _Mid.second;
}
else
{ // loop on first half
_Sort_unchecked1(_Mid.second, _Last, _Ideal, _Pred);
_Last = _Mid.first;
}
}
if (_ISORT_MAX < _Count)
{ // heap sort if too many divisions
_Make_heap_unchecked(_First, _Last, _Pred);
_Sort_heap_unchecked(_First, _Last, _Pred);
}
else if (2 <= _Count)
_Insertion_sort_unchecked(_First, _Last, _Pred); // small
}