[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
(suggestion) qsort 3 way partitioning
From: |
Dean Scarff |
Subject: |
(suggestion) qsort 3 way partitioning |
Date: |
Wed, 11 Dec 2002 11:35:18 +0800 |
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
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- (suggestion) qsort 3 way partitioning,
Dean Scarff <=