From owner-freebsd-current@freebsd.org Wed Apr 20 08:00:23 2016 Return-Path: Delivered-To: freebsd-current@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id 27C8AB15735 for ; Wed, 20 Apr 2016 08:00:23 +0000 (UTC) (envelope-from Erik.Trulsson.1013@student.uu.se) Received: from cursor.its.uu.se (smtp-out2.uu.se [130.238.7.173]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id AC90F1301 for ; Wed, 20 Apr 2016 08:00:22 +0000 (UTC) (envelope-from Erik.Trulsson.1013@student.uu.se) Received: from e-mailfilter01.sunet.se (e-mailfilter01.sunet.se [192.36.171.201]) by cursor.its.uu.se (Postfix) with ESMTP id A318920D; Wed, 20 Apr 2016 09:52:32 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=uu.se; s=centralsmtp; t=1461138752; bh=4Tf5MLauR45bgIc5copgBsb5AkEtIhmQ4J7PItfoJyQ=; h=Date:From:To:Cc:Subject:References:In-Reply-To; b=hQo68tx1Z4ZKL227FgIAT03NBPklnq3Ijs7YSyfRsLyR4kFl2WsV2iZhcjXm4cJbv q1cyZrX/WuBRh7N6reeLzISkU9S2aw+lGzCHjQgZZvyFpyG2JE/YWFPeFXUzSAR33W 0JVO0TG2qgnyMZ+7j2keOFrbWAT+vfgoSuZUu2NU= Received: from lyra.its.uu.se (lyra.its.uu.se [130.238.7.73]) by e-mailfilter01.sunet.se (8.14.4/8.14.4/Debian-4) with ESMTP id u3K7qWbN016878 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Wed, 20 Apr 2016 09:52:32 +0200 Received: from virgata.its.uu.se (virgata.its.uu.se [130.238.7.55]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by lyra.its.uu.se (Postfix) with ESMTPS id 8E8A9E8135; Wed, 20 Apr 2016 09:52:31 +0200 (CEST) Received: from jubula (localhost.localdomain [127.0.0.1]) by virgata.its.uu.se (8.13.8/8.13.8) with ESMTP id u3K7qTTd025191; Wed, 20 Apr 2016 09:52:29 +0200 Received: from h-197-74.a213.corp.bahnhof.se (h-197-74.a213.corp.bahnhof.se [85.24.197.74]) by webmail.uu.se (Horde Framework) with HTTP; Wed, 20 Apr 2016 09:52:29 +0200 Message-ID: <20160420095229.184641ns20dxu799@webmail.uu.se> Date: Wed, 20 Apr 2016 09:52:29 +0200 From: Erik Trulsson To: Warren Block Cc: Aleksander Alekseev , Hans Petter Selasky , FreeBSD Current Subject: Re: qsort() documentation References: <5714C86A.8050204@selasky.org> <20160419113430.69e41a0b@fujitsu> In-Reply-To: MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; DelSp="Yes"; format="flowed" Content-Disposition: inline Content-Transfer-Encoding: 7bit User-Agent: Internet Messaging Program (IMP) H3 (4.3.9) X-Bayes-Prob: 0.0001 (Score 0, tokens from: outbound, outbound-uu-se:default, uu-se:default, base:default, @@RPTN) X-Spam-Score: -0.10 () [Tag at 15.00] T_RP_MATCHES_RCVD:-0.1 X-p0f-Info: os=Linux 2.6.x, link=Ethernet or modem X-CanIt-Geo: ip=130.238.7.55; country=SE; region=Uppsala; city=Uppsala; latitude=59.8500; longitude=17.6333; http://maps.google.com/maps?q=59.8500,17.6333&z=6 X-CanItPRO-Stream: outbound-uu-se:outbound (inherits from outbound-uu-se:default, uu-se:default, base:default) X-Canit-Stats-ID: 09QIvQwht - dcf3924f64fd - 20160420 X-Antispam-Training-Forget: https://mailfilter.sunet.se/canit/b.php?i=09QIvQwht&m=dcf3924f64fd&t=20160420&c=f X-Antispam-Training-Nonspam: https://mailfilter.sunet.se/canit/b.php?i=09QIvQwht&m=dcf3924f64fd&t=20160420&c=n X-Antispam-Training-Phish: https://mailfilter.sunet.se/canit/b.php?i=09QIvQwht&m=dcf3924f64fd&t=20160420&c=p X-Antispam-Training-Spam: https://mailfilter.sunet.se/canit/b.php?i=09QIvQwht&m=dcf3924f64fd&t=20160420&c=s X-CanIt-Archive-Cluster: PfMRe/vJWMiXwM2YIH5BVExnUnw Received-SPF: neutral (e-mailfilter01.sunet.se: 130.238.7.55 is neither permitted nor denied by domain Erik.Trulsson.1013@student.uu.se) receiver=e-mailfilter01.sunet.se; client-ip=130.238.7.55; envelope-from=; helo=lyra.its.uu.se; identity=mailfrom X-Scanned-By: CanIt (www . roaringpenguin . com) on 192.36.171.201 X-Mailman-Approved-At: Wed, 20 Apr 2016 11:07:09 +0000 X-BeenThere: freebsd-current@freebsd.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: Discussions about the use of FreeBSD-current List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 20 Apr 2016 08:00:23 -0000 Quoting Warren Block : > 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.