The UB problem is (partially) addressed by point 2: the algorithm must terminate for all inputs.
You can choose any sort algorithm that is
guaranteed to terminate and it will work. For example, a heap sort will work with a random predicate:
1 2 3 4 5 6 7 8 9
|
template <typename RandomAccessIterator>
void nonsense_sort( RandomAccessIterator begin, RandomAccessIterator end )
{
std::ranlux48 rng;
std::bernoulli_distribution bd( .5 );
auto compare = []( auto a, auto b ) -> bool { return bd( rng ); };
std::make_heap( begin, end, compare );
std::sort_heap( begin, end, compare );
}
|
It
works, because heap sort does not depend on the comparison predicate for termination.
However, there are valid issues that arise from reality. For example, I once used
qsort()
and a random predicate, because
qsort()
was
stated to be guaranteed to terminate. Sadly, not all implementations did that properly — implementation assumes a sane comparitor. (
qsort()
is not necessarily a quick sort.)
In cases like quick sort, there are also implementation issues: both the way the pivot is handled as well as the way that the subsections created in the divide step are handled make a huge difference in the correctness of the algorithm. Further, the method used for the partition step varies widely, and may fail for a crazy comparitor.
These are all issues with
std::sort()
, which is a modified quick sort that gives up and uses a heap sort if the quick sort finds itself in a worst-case scenario. Break the quick sort and you break the introsort.
C and C++ standards people like to write things that give implementations the widest latitude for creating an
efficient and still-correct library. Hence, comparitors will be marked as requiring a strict-weak ordering, which basically means that all distinct elements in a set must be comparable with the < operator. Specifically:
• x ≮ x
• x < y → y ≮ x
• x < y, y < z → x < z
A correct sort algorithm can require this basic premise.
This challenge is a bit of a round peg and square hole problem. You can easily create a quick sort that works with a random predicate — just mind your P’s and Q’s.
@
mbozzi
Yes, you are exactly correct. KFY is a reverse selection sort. :O)