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: ok@goanna.cs.rmit.edu.au (Richard A. O'Keefe) Subject: Re: Should I learn C or Pascal? Date: 1996/08/19 Message-ID: <4v9a47$gm3@goanna.cs.rmit.edu.au>#1/1 X-Deja-AN: 175067460 references: <4u7hi6$s2b@nntp.seflin.lib.fl.us> <4uo74j$95p@ns.broadvision.com> <4v1r2a$gh6@falcon.le.ac.uk> <840224235snz@genesis.demon.co.uk> <32159698.39D9@xenon.chromatic.com> <3215cc56.142847293@nntp.ix.netcom.com> organization: Comp Sci, RMIT, Melbourne, Australia newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada,comp.os.msdos.programmer nntp-posting-user: ok Date: 1996-08-19T00:00:00+00:00 List-Id: miker3@ix.netcom.com (Mike Rubenstein) writes: >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. Yes, well I suppose all of us missed _something_ in our CS educations, such as the fact that the "proof" that O(N**2) is unlikely assumes that every possible permutation of the input is equally likely, which is not true in the real world. Check the paper by Bentley and someone (McIlroy?) in Software Practice and Experience on "Engineering a Sort": the UNIX qsort() routine *did* yield O(N**2) behaviour in actual use by people who were trying to solve a real problem, not break the sorting routine. The likelihood of quicksort doing badly on *your* data depends on the actual probability distribution of *your* data. This leads to the odd observation that if you don't know what the distribution of your data is, and you would like to be confident that bad things are genuinely unlikely, a good first step is to *scramble* your array before sorting it, so that the assumption of this proof is known to be true! (Permuting an array randomly is only O(N).) -- Australian citizen since 14 August 1996. *Now* I can vote the xxxs out! Richard A. O'Keefe; http://www.cs.rmit.edu.au/~ok; RMIT Comp.Sci.