On 04/18/16 16:49, Ed Schouten wrote:
2016-04-18 15:09 GMT+02:00 Hans Petter Selasky <h...@selasky.org>:
On 04/18/16 14:16, Aleksander Alekseev wrote:
I suggest also add a short description of how it was achieved

I think the algorithm is switching to mergesort. I'll look up the paper and
add that correctly before commit.

As a Dutch person, I know the answer to this.

Instead of picking a fixed pivot or choosing one at random, it uses an
approach called linear time median finding to find a pivot that is
'approximately median'. There are a couple of algorithms for this, but
I think Bentley's qsort() uses this:



Ryan: Yes, there is quadratic behaviour still, but I believe the order is limited. For the matter of the topic I added a counter for the swap() code in the insertion fallback algorithm, and for a set of 2048 integers I never saw the swap() count exceed this number. For a pre-sorted array, values around ~2047 and reverse sorted ~2043. For random input far less.

Citing the document "bentley93engineering.pdf", a footnote says:

Of course, quadratic behavior is still possible. One can generate fiendish inputs by bugging Quicksort: Con- sider key values to be unknown initially. In the code for selecting a partition element, assign values in increas- ing order as unknown keys are encountered. In the partitioning code, make unknown keys compare high.

Did anyone try to generate such a fiendish set of data, and see how quadratic the FreeBSD's qsort() becomes?

Another thread, possibly related:


freebsd-current@freebsd.org mailing list
To unsubscribe, send any mail to "freebsd-current-unsubscr...@freebsd.org"

Reply via email to