Idempotent partition around median of 5?

[tn via Digitalmars-d]

On Friday, 5 February 2016 at 21:42:41 UTC, Xinok wrote:
> On Friday, 5 February 2016 at 15:13:56 UTC, 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
>>
>> ...
>
> Very nice! I'm curious, to both you and Timon, how did you go 
> about writing these and coming up with the solutions? I'm not 
> sure if I could come up with these results myself and so 
> quickly at that.

I basically just started from Timons solution and made is smaller 
by replacing branches by swaps. The outermost structure of Timons 
code looks like this:

   if (a[0] < a[1]) {
     do something 1
   } else {
     do something 2
   }

I replaced the above by

   if (a[0] < a[1]) {
     swap(a[0], a[1]);
   }
   do something 1

So adding one swap just about halved the size of the code. Now 
"do something 1" again has two branches:

   if (a[2] < a[3]) {
     do something 1.1
   } else {
     do something 1.2
   }

So we can do the same trick again and replace it by

   if (a[2] < a[3]) {
     swap(a[2], a[3]);
   }
   do something 1.1

And so on. (When doing subsequent swaps we also need to make sure 
to not break the conditions achieved by the previous swaps.)

However, the swap of a[0] and a[1] in the first replacement would 
break idempotence, so I also had to change which elements are 
compared (and swapped). So in my code we first compare a[0] and 
a[2], then a[1] and a[3], and so on.