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: 103376,97188312486d4578 X-Google-Attributes: gid103376,public X-Google-Thread: 109fba,baaf5f793d03d420 X-Google-Attributes: gid109fba,public X-Google-Thread: 1014db,6154de2e240de72a X-Google-Attributes: gid1014db,public From: pausch@electra.saaf.se (Paul Schlyter) Subject: Re: Should I learn C or Pascal? Date: 1996/08/20 Message-ID: <4vblm8$df9@electra.saaf.se>#1/1 X-Deja-AN: 175273317 references: <4u7hi6$s2b@nntp.seflin.lib.fl.us> <4uo74j$95p@ns.broadvision.com> <4v1r2a$gh6@falcon.le.ac.uk> organization: Svensk Amat|rAstronomisk F|rening newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada,comp.os.msdos.programmer Date: 1996-08-20T00:00:00+00:00 List-Id: In article <4v1r2a$gh6@falcon.le.ac.uk>, 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. > > 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. -- ---------------------------------------------------------------- Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF) Grev Turegatan 40, S-114 38 Stockholm, SWEDEN e-mail: pausch@saaf.se psr@home.ausys.se