On 4/20/23 11:20, Joerg Sonnenberger wrote:
Am Wed, Apr 19, 2023 at 11:47:35PM +0200 schrieb Hans Petter Selasky:
On 4/19/23 23:17, Joerg Sonnenberger wrote:
That's false. The difficult part of QuickSort is the median selection.
This can be done in O(n) using the median of median algorithm and when
combined into the main algorithm, much of the work for the median
selection also helps the partition step.
Hi Joerg,
From what I know, they all fall back to other sorting algorithms using
malloc(), in the end.
Please, just go and read:
Blum, Floy, Pratt, Rivest, Tarjan: Time Bounds for Selection, 1973.
[https://people.csail.mit.edu/rivest/pubs/BFPRT73.pdf]
If you want a slightly more variant:
Alexandrescu: Fast Deterministic Selection, 2017.
[http://erdani.org/research/sea2017.pdf]
Short answer: QuickSort requires O(log N) extra space, which is
essentially a fixed cost given the natural address space limitations.
Unless operating in a seriously confined environment, that's a perfectly
fine use of the regular stack.
Hi Joerg,
Thanks for the references you've provided. After reading through the
paper from 1973, I have the impressions it is about solving the
so-called pivot selection problem.
The basic QuickSort idea was introduced in 1961, according to the paper
you referred to:
C. A. R. HOaRE, Find (Algorithm 65), Communications of the ACM, July
1961, pp. 321-32
The other paper you refer to:
http://erdani.org/research/sea2017.pdf
is about different ways to implement QuickSort and how to mitigate
problems about pivot selection and performance.
Looking around, qsort() in libc's around the globe is so-to-speak
equivalent to variants of QuickSort:
Example 1: Android
https://android.googlesource.com/platform/bionic/+/754c178ae551aedcbbfd3bfd1c1c3b710d9ad989/libc/stdlib/qsort.c
Example 2: Linux (GLibc)
https://github.com/lattera/glibc/blob/master/stdlib/qsort.c
Example 3: NetBSD
http://cvsweb.netbsd.org/bsdweb.cgi/src/lib/libc/stdlib/qsort.c?rev=1.23&content-type=text/x-cvsweb-markup
Example 4: Darwin
https://github.com/apple/darwin-xnu/blob/main/bsd/kern/qsort.c
And FreeBSD of course.
Why not allow for more sorting competition inside FreeBSD?
If libc is not the place, maybe an own library, like libsort is more
appropriate?
Would that be any better if bsort(3) was in its own library, and
developed from that?
--HPS
