Idempotent partition around median of 5?

tn via Digitalmars-d digitalmars-d at puremagic.com
Fri Feb 5 07:13:56 PST 2016


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



More information about the Digitalmars-d mailing list