Idempotent partition around median of 5?

Timon Gehr via Digitalmars-d digitalmars-d at puremagic.com
Fri Feb 5 13:48:58 PST 2016


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.)


More information about the Digitalmars-d mailing list