Date: Thu, 20 Apr 2023 13:23:18 +0200 From: Hans Petter Selasky <hps@selasky.org> To: Joerg Sonnenberger <joerg@bec.de>, dev-commits-src-all@freebsd.org Subject: Re: git: 8dcf3a82c54c - main - libc: Implement bsort(3) a bitonic type of sorting algorithm.] Message-ID: <d626c4b7-e771-df57-ad2f-a136b50b4a0c@selasky.org> In-Reply-To: <ZEEDxY7EnaEKycMF@bec.de> References: <202304191206.33JC6Qcp062380@gitrepo.freebsd.org> <ZEAM3rO9r5e97BHE@spindle.one-eyed-alien.net> <a073fd36-9aa9-e988-0cc5-86af305fb654@freebsd.org> <3B5734C4-8630-4CD5-BA8D-DE33899161F1@freebsd.org> <e2ea5c89-aa48-e257-b9d5-7fe783bf216e@freebsd.org> <ZEBagv961lutuBJV@bec.de> <b9395dbc-bddf-6250-0185-14ae4318bcb2@selasky.org> <ZEEDxY7EnaEKycMF@bec.de>
next in thread | previous in thread | raw e-mail | index | archive | help
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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?d626c4b7-e771-df57-ad2f-a136b50b4a0c>