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