Finding the probable best candidate?

[Forest Simmons]

On Wed, 20 Feb 2002, Rob LeGrand wrote:

> Forest wrote:
> > > Unfortunately, at least according to my simulations so far, BSBS is much
> > > worse at SU given sincere votes than BSSE or Black.
> >
> > I knew that, but that's part of the inevitable tradeoff.  The higher the
> > SU in this class of methods, the less likely that the votes will be
> > sincere.
> >
> > My guess is ...
> >
> > SU:        Borda > Black > BSSE > BSBS > Inverse Nanson > Schulze
> >
> > Likelihood of sincere
> > ballots  : Borda < Black < BSSE < BSBS < Inverse Nanson < Schulze
> 
> Very interesting!  Has anyone come up with an objective measure of
> manipulability?  Nanson itself has an average SU much worse than Schulze or
> even Ranked Pairs, and Baldwin (Borda-elimination) is even worse.  I wonder
> whether Inverse Nanson would really beat Schulze on SU.  Worth a try, though .

Inverse Nanson should really be called Inverse Baldwin. Tom Ruen was still
going by Blake's old nomenclature when he came up with that.

> . .
> 
> > Usually in insertion sort the new guy is tested against the middle of the
> > previously sorted guys.  Bubble sort starts the new guy at the bottom and
> > lets him work up one place at a time.  Insertion sort is efficient on the
> > order of n*log(n) comparisons, while bubble sort requires about n*n/2
> > comparisons.
> >
> > Sink sort is bubble sort in reverse.
> 
> I see.  Your sink sort is what I've heard called bubble sort,

I might be wrong, but I think of bubbles going up (like the new guy
percolating upward) and sinkers going down.

Of course, in computer science the root of a binary tree is at the top,
and the leaves are at the bottom :-)

> and your bubble
> sort I've heard called insertion sort.  I'd never seen an O(n log n) insertion
> sort before, but the scheme you describe certainly makes sense.  I'd guess that
> the number of actual swaps would still be O(n^2), though.

When you test in the middle of each subsection of previously ordered
items you end up doing about base two log(m) tests when m items have
already been sorted.  So the maximum number of tests per item is
O(log(n)).  If you have n items to sort the total is O(n log(n)), same as
merge sort.

Forest