Idempotent partition around median of 5?

[Ivan Kazmenko via Digitalmars-d]

On Thursday, 4 February 2016 at 01:24:15 UTC, Andrei Alexandrescu 
wrote:
> 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.

Here's my take at it.

It's idempotent and does exactly 6 comparisons and 0-8 swaps.
The advantages to counter the not-so-good stats are that it has a 
flat structure, and is not hard to reason about.

The idea is to process the following steps:

1. Find the minimum of {b, c, d, e} in three comparisons, and put 
it into b.
The structure is: b < d, c < e, b < c.
Note that d and e were not compared if no swaps were made.

2. Find the minimum of {a, c, d, e} in two more comparisons, and 
put it into a.
The structure is: a < d, c < e, a < c.
Note that a and b were not compared if no swaps were made.

3. Find the minimum of {c, d, e} in one more comparison, and put 
it into c.
The structure is: c < d, c < e.
Note that d and e were not compared if no swaps were made.

In the end, we have a < c, b < c, c < d, c < e.
Additionally, if these inequalities held initially, everything is 
left in place regardless of the results of comparisons of (a, b) 
and (d, e).

In code:
-----
import std.algorithm;
import std.exception;
import std.range;
import std.stdio;

void p5 (ref int a, ref int b, ref int c, ref int d, ref int e)
{
     if (d < b) {swap (b, d);}
     if (e < c) {swap (c, e);}
     if (c < b) {swap (b, c); swap (d, e);}
     if (d < a) {swap (a, d);}
     if (c < a) {swap (a, c); swap (d, e);}
     if (d < c) {swap (c, d);}
}

void main ()
{
     auto a = 5.iota.array;
     do
     {
         auto b = a.dup;
         p5 (b[0], b[1], b[2], b[3], b[4]);
         auto c = b.dup;
         p5 (c[0], c[1], c[2], c[3], c[4]);
         writeln (a, " -> ", b, " -> ", c);
         enforce (b[0] < b[2] && b[1] < b[2] &&
             b[2] < b[3] && b[2] < b[4]);
         enforce (equal (b, c));
     }
     while (nextPermutation (a));
}
-----

Another interesting task would be to make the function stable, 
but I don't see how it is possible with such flat structure.

Ivan Kazmenko.