On 02/05/2016 04:41 PM, Fool 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)[...]
One swap usually decomposes into three moves. A cycle of length n can be
sorted with n + 1 moves. Corresponding to the seven integer partitions
of 5 we obtain:
5: 6
4 + 1: 5
3 + 2: 4 + 3
3 + 1 + 1: 4
2 + 2 + 1: 3 + 3
2 + 1 + 1 + 1: 3
1 + 1 + 1 + 1 + 1: 0
So we can do with seven moves instead of three swaps (nine moves). ;-)
The goal is to partition though, not to sort.
Six moves are sufficient. (And necessary. E.g. for 42310.)
