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.
