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
_______________________________________________
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"
