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: 103376,97188312486d4578 X-Google-Attributes: gid103376,public X-Google-Thread: fc89c,97188312486d4578 X-Google-Attributes: gidfc89c,public X-Google-Thread: 1014db,6154de2e240de72a X-Google-Attributes: gid1014db,public From: miker3@ix.netcom.com (Mike Rubenstein) Subject: Re: Should I learn C or Pascal? Date: 1996/08/16 Message-ID: <3214e6a0.84041124@nntp.ix.netcom.com>#1/1 X-Deja-AN: 174613732 references: <4u7hi6$s2b@nntp.seflin.lib.fl.us> <4uo74j$95p@ns.broadvision.com> <4v1r2a$gh6@falcon.le.ac.uk> organization: Netcom x-netcom-date: Fri Aug 16 2:35:01 PM PDT 1996 newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada,comp.os.msdos.programmer Date: 1996-08-16T14:35:01-07:00 List-Id: "Dr E. Buxbaum" 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. Only if it is implemented by an idiot. Techniques that make O(n^2) operation extremely unlikely are well known and are covered in any decent book of algorithms. Hoare's 1962 paper points out one of them. If the data is known to be very close to being sorted, quicksort (properly implemented) isn't the sort of choice, but it's not terrible. Michael M Rubenstein