Idempotent partition around median of 5?

[Andrei Alexandrescu via Digitalmars-d]

On 02/05/2016 10:13 AM, tn wrote:
> On Thursday, 4 February 2016 at 20:30:57 UTC, Timon Gehr wrote:
>> At most 6 comparisons, <=3 swaps, idempotent (optimal number of swaps):
>>
>> ...
>>
>
> Inspired by this, I made four other versions of the function that are
> shorter but make more swaps (at most 4, 6, 7 and 8 swaps respectively).
> Each makes 6 comparisons and should be idempotent.
>
> http://dpaste.dzfl.pl/1c53d8f432f7

Whoa, I missed this last night. Awesome work! Thanks! I'm kinda running 
out of time budget here for this particular subproblem, but I've got to 
do these justice and try them out as well.

> Here are the distributions of the number of swaps when tested with all
> 120 possible permutations as the input:
>
> testing 'partition5a' (by Timon Gehr)
>    0 swaps: 4 orderings
>    1 swaps: 32 orderings
>    2 swaps: 68 orderings
>    3 swaps: 16 orderings
> testing 'partition5b'
>    0 swaps: 4 orderings
>    1 swaps: 20 orderings
>    2 swaps: 42 orderings
>    3 swaps: 40 orderings
>    4 swaps: 14 orderings
[...]

Could you please add two simple calculations? Assuming uniform random 
distribution of data, compute the average number of swaps as a weighted 
average of orderings. Also, show the number of lines (one test or one 
swap per line) as a proxy for generated code size. That should provide 
good insights.


Thanks!

Andrei