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
(randomization?).
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:
https://en.wikipedia.org/wiki/Dutch_national_flag_problem
Hi,
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:
<cite>
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.
</cite>
Did anyone try to generate such a fiendish set of data, and see how
quadratic the FreeBSD's qsort() becomes?
Another thread, possibly related:
http://postgresql.nabble.com/Why-do-we-still-perform-a-check-for-pre-sorted-input-within-qsort-variants-td5746526.html
--HPS
_______________________________________________
freebsd-current@freebsd.org mailing list
https://lists.freebsd.org/mailman/listinfo/freebsd-current
To unsubscribe, send any mail to "freebsd-current-unsubscr...@freebsd.org"
