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: 109fba,baaf5f793d03d420 X-Google-Attributes: gid109fba,public X-Google-Thread: 103376,97188312486d4578 X-Google-Attributes: gid103376,public X-Google-Thread: 1014db,6154de2e240de72a X-Google-Attributes: gid1014db,public From: Paul Hsieh Subject: Re: Should I learn C or Pascal? Date: 1996/08/17 Message-ID: <32159698.39D9@xenon.chromatic.com>#1/1 X-Deja-AN: 174705785 references: <4u7hi6$s2b@nntp.seflin.lib.fl.us> <4uo74j$95p@ns.broadvision.com> <4v1r2a$gh6@falcon.le.ac.uk> <840224235snz@genesis.demon.co.uk> content-type: text/plain; charset=us-ascii organization: Zocalo - Berkeley, California, USA mime-version: 1.0 newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada,comp.os.msdos.programmer x-mailer: Mozilla 3.0b5Gold (Win95; I) Date: 1996-08-17T00:00:00+00:00 List-Id: 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. -- Paul Hsieh qed@chromatic.com http://www.geocities.com/SiliconValley/9498 Graphics Programmer Chromatic Research What I say and what my company says are not always the same thing