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