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
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
testing 'partition5c'
0 swaps: 4 orderings
1 swaps: 14 orderings
2 swaps: 25 orderings
3 swaps: 30 orderings
4 swaps: 26 orderings
5 swaps: 16 orderings
6 swaps: 5 orderings
testing 'partition5d'
0 swaps: 4 orderings
1 swaps: 14 orderings
2 swaps: 24 orderings
3 swaps: 29 orderings
4 swaps: 26 orderings
5 swaps: 16 orderings
6 swaps: 6 orderings
7 swaps: 1 orderings
testing 'partition5e'
0 swaps: 4 orderings
1 swaps: 12 orderings
2 swaps: 19 orderings
3 swaps: 25 orderings
4 swaps: 25 orderings
5 swaps: 18 orderings
6 swaps: 11 orderings
7 swaps: 5 orderings
8 swaps: 1 orderings
