On Thursday, 4 February 2016 at 01:33:54 UTC, Era Scarecrow wrote:
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.
The order of a,b and d,e don't matter because we're partitioning,
not sorting. So this problem can be solved in six comparisons.
I'm not sure of the max swaps, seems like it could be 4 if
done right, but that might be impractical.
I believe that's correct. Each swap can move at least one element
into it's final position. After three swaps, there may be two
elements which are still out of place, and swapping them will
move them both into their final position. Thus, four swaps max.
:-)
A solution to this problem does exist: Build a tree of if-else
branches for all the different possibilities (2^6=64) and
hard-code the optimal sequence of swaps. However, this function
would be huge so this isn't very practical. Ideally, we want to
minimize the size of the function as much as possible, adding in
a few extra swaps if necessary.
I'll take a crack at it this weekend. It sounds like an
interesting problem.
