From owner-freebsd-current@freebsd.org Mon Apr 18 16:10:03 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 B631FB131B2 for ; Mon, 18 Apr 2016 16:10:03 +0000 (UTC) (envelope-from hps@selasky.org) Received: from mail.turbocat.net (mail.turbocat.net [IPv6:2a01:4f8:d16:4514::2]) (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 8242810C5 for ; Mon, 18 Apr 2016 16:10:03 +0000 (UTC) (envelope-from hps@selasky.org) Received: from laptop015.home.selasky.org (unknown [62.141.129.119]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by mail.turbocat.net (Postfix) with ESMTPSA id 3687E1FE023; Mon, 18 Apr 2016 18:09:59 +0200 (CEST) Subject: Re: qsort() documentation To: Ed Schouten References: <5714C86A.8050204@selasky.org> <20160418151639.634d571d@fujitsu> <5714DC98.7090208@selasky.org> Cc: Aleksander Alekseev , FreeBSD Current From: Hans Petter Selasky Message-ID: <5715079B.9010408@selasky.org> Date: Mon, 18 Apr 2016 18:13:15 +0200 User-Agent: Mozilla/5.0 (X11; FreeBSD amd64; rv:38.0) Gecko/20100101 Thunderbird/38.5.0 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset=windows-1252; format=flowed Content-Transfer-Encoding: 7bit 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: Mon, 18 Apr 2016 16:10:03 -0000 On 04/18/16 16:49, Ed Schouten wrote: > 2016-04-18 15:09 GMT+02:00 Hans Petter Selasky : >> On 04/18/16 14:16, Aleksander Alekseev wrote: >>> I suggest also add a short description of how it was achieved >>> (randomization?). >> >> I think the algorithm is switching to mergesort. I'll look up the paper and >> add that correctly before commit. > > As a Dutch person, I know the answer to this. > > Instead of picking a fixed pivot or choosing one at random, it uses an > approach called linear time median finding to find a pivot that is > 'approximately median'. There are a couple of algorithms for this, but > I think Bentley's qsort() uses this: > > https://en.wikipedia.org/wiki/Dutch_national_flag_problem > Hi, Ryan: Yes, there is quadratic behaviour still, but I believe the order is limited. For the matter of the topic I added a counter for the swap() code in the insertion fallback algorithm, and for a set of 2048 integers I never saw the swap() count exceed this number. For a pre-sorted array, values around ~2047 and reverse sorted ~2043. For random input far less. Citing the document "bentley93engineering.pdf", a footnote says: Of course, quadratic behavior is still possible. One can generate fiendish inputs by bugging Quicksort: Con- sider key values to be unknown initially. In the code for selecting a partition element, assign values in increas- ing order as unknown keys are encountered. In the partitioning code, make unknown keys compare high. Did anyone try to generate such a fiendish set of data, and see how quadratic the FreeBSD's qsort() becomes? Another thread, possibly related: http://postgresql.nabble.com/Why-do-we-still-perform-a-check-for-pre-sorted-input-within-qsort-variants-td5746526.html --HPS