On Thursday, 4 February 2016 at 01:24:15 UTC, Andrei Alexandrescu
wrote:
This appears a simple problem: given numbers a, b, c, d, e,
swap them around so as to place the median in c and partition
the others around it. I.e. the postcondition is: a <= c && b <=
c && c <= d && c <= e.
<snip>
So there's got to be a better solution. Your challenge - should
you choose to accept it :o) - is an algorithm that does the
partitioning in 6 comparisons and <= 9 swaps, which is
idempotent: when applied twice, it always does 0 swaps.
Well if we look at it, the max compares for optimal sorting
algorithm is the log2 of the max combinations in how the elements
could be arranged; !5 = 120 or 7 compares.
I'm not sure of the max swaps, seems like it could be 4 if done
right, but that might be impractical.
