From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham
	autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 103376,385be4c68a9e4de6
X-Google-Attributes: gid103376,public
X-Google-ArrivalTime: 2002-07-02 15:58:58 PST
Path: 
 archiver1.google.com!news1.google.com!sn-xit-02!sn-xit-06!sn-post-01!supernews.com!corp.supernews.com!not-for-mail
From: achrist@easystreet.com
Newsgroups: comp.lang.ada
Subject: Re: Smart sorting algorithm ?
Date: Tue, 02 Jul 2002 15:57:12 -0700
Organization: Posted via Supernews, http://www.supernews.com
Message-ID: <3D222FC8.D4F10CF4@easystreet.com>
X-Mailer: Mozilla 4.79 [en] (WinNT; U)
X-Accept-Language: en
MIME-Version: 1.0
References: <3D21D581.6EF6CB06@despammed.com>
 <3D21DC25.AD402F70@easystreet.com> <3D220648.6F3BE45D@despammed.com>
 <3D2221CD.3F619935@easystreet.com> <3D22278D.D3D34B7D@despammed.com>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
X-Complaints-To: newsabuse@supernews.com
Xref: archiver1.google.com comp.lang.ada:26827
Date: 2002-07-02T15:57:12-07:00
List-Id: <comp.lang.ada>

Wes Groleau wrote:
> 
> > I guess that quicksort will repeat comparisons if there are duplicate
> > items in the set of items being sorted.  Or if the pivots are selected
> 
> As a matter of fact, this particular implementation
> _several_ times compared an item with itself!
> 

I think that's an optimization of the tight inner loop that is based on
the assumption that one extra item compare is less expensive than
comparing indexes on every iteration of the loop plus keeping track of
where your pivot element is.  That comparison of an element with itself
will end the inner loop.  In your case, the assumption is maybe not
true, but you get at most one extra compare on the last time through the 
loop.  I think you can change the loop to save the comparison, but it 
makes the algorithm more complicated and it's easy to get it wrong.  I 
believe I've done that.

Al