Date: Wed, 20 Apr 2016 09:52:29 +0200 From: Erik Trulsson <Erik.Trulsson.1013@student.uu.se> To: Warren Block <wblock@wonkity.com> Cc: Aleksander Alekseev <afiskon@devzen.ru>, Hans Petter Selasky <hps@selasky.org>, FreeBSD Current <freebsd-current@freebsd.org> Subject: Re: qsort() documentation Message-ID: <20160420095229.184641ns20dxu799@webmail.uu.se> 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
Quoting Warren Block <wblock@wonkity.com>: > 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. Keep in mind that there is no requirement whatsoever that the qsort() function uses the quicksort algorithm, even if that is a common way to implement qsort() Also, worst-case is worst-case, no matter how unlikely.
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20160420095229.184641ns20dxu799>