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.Received on Wed Apr 20 2016 - 02:01:35 UTC
This archive was generated by hypermail 2.4.0 : Wed May 19 2021 - 11:41:04 UTC