Idempotent partition around median of 5?

[Xinok via Digitalmars-d]

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.