Date: Tue, 19 Apr 2016 22:01:20 -0600 (MDT) From: Warren Block <wblock@wonkity.com> To: Aleksander Alekseev <afiskon@devzen.ru> Cc: Hans Petter Selasky <hps@selasky.org>, FreeBSD Current <freebsd-current@freebsd.org> Subject: Re: qsort() documentation Message-ID: <alpine.BSF.2.20.1604192002111.59174@wonkity.com> In-Reply-To: <20160419113430.69e41a0b@fujitsu> References: <5714C86A.8050204@selasky.org> <alpine.BSF.2.20.1604181250450.68720@wonkity.com> <20160419113430.69e41a0b@fujitsu>
next in thread | previous in thread | raw e-mail | index | archive | help
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.
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?alpine.BSF.2.20.1604192002111.59174>