Date: Wed, 20 Apr 2016 08:45:00 +0200 From: Hans Petter Selasky <hps@selasky.org> To: Warren Block <wblock@wonkity.com>, Aleksander Alekseev <afiskon@devzen.ru>, FreeBSD Current <freebsd-current@freebsd.org> Subject: Re: qsort() documentation Message-ID: <5717256C.5080805@selasky.org> In-Reply-To: <alpine.BSF.2.20.1604192002111.59174@wonkity.com> References: <5714C86A.8050204@selasky.org> <alpine.BSF.2.20.1604181250450.68720@wonkity.com> <20160419113430.69e41a0b@fujitsu> <alpine.BSF.2.20.1604192002111.59174@wonkity.com>
next in thread | previous in thread | raw e-mail | index | archive | help
On 04/20/16 06:01, Warren Block wrote: > On Tue, 19 Apr 2016, Aleksander Alekseev wrote: > >>> Why Wikipedia, specifically? There are a lot of places that describe >>> quicksort. How about just >>> >>> Note: This implementation of qsort() is designed to avoid the >>> worst-case complexity of N**2 that is often seen with standard >>> versions. >> >> I would say that this statement is just false. Worst-case complexity is >> still N**2. How about something like: >> >> """ >> This implementation of qsort() has worst case complexity of N**2. >> However measures were taken that make it very unlikely that for some >> random input N**2 swaps will be made. It's still possible to generate >> such an input on purpose though. See code below for more details. >> """ > > Okay: > > The quicksort algorithm worst-case is O(N**2), but this implementation > has been designed to avoid that for most real data. Hi, There is something which I don't understand. Why is quicksort falling back to insertion sort which is an O(N**2) algorithm, when there exist a O(log(N)*log(N)*N) algorithms, which I propose as a solution to the "bad" characteristics of qsort. The replacement algorithm I propose does not allocate working memory and it does not recurse and it does not use a significant amount of stack space. Maybe some number theorists want to have a look? I cannot seem to find it anywhere public. See here: https://reviews.freebsd.org/D5241 Local test results w/D5241 running statically in userspace: > Data set size log2(N) qsort w/insert sort qsort w/hpsort mergesort data set > 10 1.28 1.12 1.34 random0 > 11 2.42 2.43 2.83 random0 > 12 5.21 5.2 6.1 random0 > > 10 1.26 1.14 1.44 random1 > 11 2.46 2.46 3.05 random1 > 12 5.28 5.29 6.56 random1 > > 10 10.01 5.1 0.2 bad0 > 11 39.12 12.11 0.33 bad0 > 12 156.54 28.42 0.58 bad0 New algorithm is in the middle column. Times are in seconds. Bad0 data set: > http://calmerthanyouare.org/2014/06/11/algorithmic-complexity-attacks-and-libc-qsort.html --HPS
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?5717256C.5080805>