Re: [gnugo-devel] RE: qsort() causes platform dependence

[Gunnar Farneback]

"Aguydude" wrote:
> You know, there's a better version of combsort.
> http://world.std.com/~jdveale/combsort.htm provides information. The
> gap table there will work for up to 4,000,000 items but can be
> increased to work with more. Anyways, 1.3 is not the optimal point to
> divide. One can go without the gap table but l'd consider using
> 1.279604943109628 instead of 1.3.

I see no justification for that number being optimal, just that's it
chosen in their implementation of gap tables and claimed to be a good
idea.

> All of the problems pointed out in the message so long ago
> (http://mail.gnu.org/pipermail/gnugo-devel/2001-December/000882.html)
> with data that doesn't sort well are reduced by using the gap table
> (which, AFAIK, was devised after the post). I don't have the
> knowledge to post a patch for its use but perhaps someone would like
> to do so.

Some kind of gap tables, possibly rather preliminary, were around when
I did the research for the function last year. For our purposes the
simplicity of the current implementation is more valuable than
avoiding degeneration for certain uncommon sequences.

What I'd like to see is a theoretical analysis of the algorithm. That
was something I couldn't find a year ago.

/Gunnar