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: 109fba,baaf5f793d03d420
X-Google-Attributes: gid109fba,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
From: miker3@ix.netcom.com (Mike Rubenstein)
Subject: Re: Should I learn C or Pascal?
Date: 1996/08/17
Message-ID: <3215cc56.142847293@nntp.ix.netcom.com>#1/1
X-Deja-AN: 174853311
references: <4u7hi6$s2b@nntp.seflin.lib.fl.us> <4uo74j$95p@ns.broadvision.com>
 <qqk9v3ji06.fsf@tartarus.ucsd.edu> <4v1r2a$gh6@falcon.le.ac.uk>
 <840224235snz@genesis.demon.co.uk> <32159698.39D9@xenon.chromatic.com>
organization: Netcom
x-netcom-date: Sat Aug 17  8:45:21 AM CDT 1996
newsgroups: 
 comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada,comp.os.msdos.programmer
Date: 1996-08-17T08:45:21-05:00
List-Id: <comp.lang.ada>


Paul Hsieh <qed@xenon.chromatic.com> wrote:

> Lawrence Kirby wrote:
> > 
> > In article <4v1r2a$gh6@falcon.le.ac.uk> EB15@le.ac.uk "Dr E. Buxbaum" writes:
> > 
> > >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.
> > 
> > Quicksort is faster for sorted data than unsorted data: any passable
> > implementation will use at the very least median-of-three pivot > selection.
> 
> Geez ... pay attention in class next time folks:
> 
> On a reversed list, quicksort==bubble sort.
> On a shifted list, quicksort==bubble sort.
> On most other arrangements quicksort = O(nlnn)
> 
> Merge sort is O(nln) in all situations and hence is better when reliable
> running time is required.

You should not have cut class the day they covered the techniques for
making O(N^2) performance very unlikely.  In fact, properly
implemented, quicksort will give O( N log N) performance on both a
reversed list and a shifted list.

Michael M Rubenstein