(suggestion) qsort 3 way partitioning

[Dean Scarff]

    Greetings,

I've been working on a 3 way partitioning algorithm for qsort.  I originally 
used the Bentley-McIlroy method, but I didn't like splitting then recombining, 
so I rewrote the glibc qsort.c revision 1.11 to use 3 way partitioning.

What I eventually came up with seems to be efficient, and some benchmarks show 
that its not too far behind libc for high entropy elements, and is 
significantly better for low entropy.  I didn't bother testing against an 
antiqsort, but it would be interesting to know the results of this.

Whether or not it's a good candidate for glibc I'm not sure.

I figure that with warnings like the one in The GNU C Library Reference Manual 
about 'stability' and using a compare function that avoids returning 0, most 
users of qsort have worked around its 'instability' with elements equal to the 
pivot.  I didnt check about C99 compliance but it should be fine as far as 
that's concerned.

the actual candidate that could be used in glibc is at:
http://www.proud-x.com/~p00ya/qsort/qsort-candidate.c

You can have a look at all my work on it at:
http://www.proud-x.com/~p00ya/qsort/
(sorry no makefile :/)


Cheers,
Dean Scarff
    
-- 
_______________________________________________
Get your free email from http://mymail.operamail.com

Powered by Outblaze