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.3 required=5.0 tests=BAYES_00,INVALID_MSGID
	autolearn=no autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 10f6aa,e1e578817780dac2
X-Google-Attributes: gid10f6aa,public
X-Google-Thread: fc89c,97188312486d4578
X-Google-Attributes: gidfc89c,public
X-Google-Thread: 1014db,6154de2e240de72a
X-Google-Attributes: gid1014db,public
X-Google-Thread: 103376,97188312486d4578
X-Google-Attributes: gid103376,public
X-Google-Thread: 109fba,baaf5f793d03d420
X-Google-Attributes: gid109fba,public
From: miker3@ix.netcom.com (Mike Rubenstein)
Subject: Re: Should I learn C or Pascal?
Date: 1996/08/20
Message-ID: <32199f2d.20856009@nntp.ix.netcom.com>#1/1
X-Deja-AN: 175298138
references: <4u7hi6$s2b@nntp.seflin.lib.fl.us> <4uo74j$95p@ns.broadvision.com>
 <qqk9v3ji06.fsf@tartarus.ucsd.edu> <4v1r2a$gh6@falcon.le.ac.uk>
 <4vblm8$df9@electra.saaf.se>
organization: Netcom
x-netcom-date: Tue Aug 20  4:21:12 AM PDT 1996
newsgroups: 
 comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada,comp.os.msdos.programmer
Date: 1996-08-20T04:21:12-07:00
List-Id: <comp.lang.ada>


pausch@electra.saaf.se (Paul Schlyter) wrote:

> In article <4v1r2a$gh6@falcon.le.ac.uk>, Dr E. Buxbaum <EB15@le.ac.uk> wrote:
>  
> > djohnson@tartarus.ucsd.edu (Darin Johnson) wrote:
> >>> A binary sort, also known as quicksort, or Hoare's sort is
> >>> covered extensively
> > 
> >>"quicksort is the fastest sort" categorization without really
> >>understanding it.  
> > 
> > A common misconception. Quicksort is fast for UNSORTED data. For data 
> > which are largely presorted (a common occurance if a bunch of additional 
> > data has to be added to a list), Quicksort becomes Slowsort. 
> > 
> > Resume: Spend some time on checking your data first, then decide on the 
> > proper sorting algorithm!
>  
> The performane of Quicksort on already sorted, or almost-sorted, data
> can be dramatically improved by first scrambling the data(!) somewhat.
>  
> For instance the first element can be exchanged with some element
> near the middle, and then that new first element can be used as a
> pivot.  This matters little on unsorted data, but ensures that on
> almost-sorted data the pivot will each time split the data set into
> two approximately equally large parts, which will yield near-optimum
> performance of Quicksort.
>  
> Of course, this trick still does not ensure that Quicksort never will
> perform miserably -- it still may do if the input data is ordered in
> some particular way.  But at least it's much less likely to encounter
> this "wost performance" initial order, and it's is quite different
> from almost-sorted order.

Why not just pick the pivot randomly?  This was suggested by Hoare in
1962.

Michael M Rubenstein