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: alexad3@iceonline.com (Alexander J Russell) Subject: Re: Should I learn C or Pascal? Date: 1996/08/17 Message-ID: #1/1 X-Deja-AN: 174783758 sender: Newsposter@iceonline.com (Newsposter) references: <4u7hi6$s2b@nntp.seflin.lib.fl.us> <4uo74j$95p@ns.broadvision.com> <4uu9v3$hrp@goanna.cs.rmit.edu.au> content-type: Text/Plain; charset=US-ASCII organization: ICE Online Internet news mime-version: 1.0 newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada,comp.os.msdos.programmer Date: 1996-08-17T00:00:00+00:00 List-Id: In article <4uu9v3$hrp@goanna.cs.rmit.edu.au>, ok@goanna.cs.rmit.edu.au says... > >djohnson@tartarus.ucsd.edu (Darin Johnson) writes: >>Actually, I learned it freshman year, but didn't understand it. >... >>I think many of my classmates kept the >>"quicksort is the fastest sort" categorization without really >>understanding it. Too many people fall asleep in algorithms class >>(then bitch about the waste of time later). > >The *really* sad thing here is that quicksort is *not* the fastest sort. >Quicksort was specifically designed (see Hoare's paper in Computer >Journal, 1960 or 61, can't remember the issue) for a machine with 256 >words of memory. Not 256M. Not 256k. Two hundred and fifty-six words >of main memory. Backing store was a drum with 16384 words, transferred >in 64 word pages. Hoare knew at the time that it did more comparisons >than merge sort, but merge sort need extra memory that simply wasn't there. > >Quicksort still has a niche in embedded processors, >although there is a new version of heapsort (also published in the >Computer Journal, but I can't find the reference) which can challenge it: >the modern heapsort has the virtue that its worst case is O(nlgn) which >makes it a better bet for soft-real-time work. > >For general use, a well engineered merge sort is as good as a well engineered >quicksort; sometimes better. > >For sorting machine integers, a well engineered radix sort (or even count >sort if the range is small enough) is so much faster that it isn't funny. > >For most programmers, the main issue is that it is cheaper to re-use >an existing expertly implemented and thoroughly tested sort procedure >than to write their own buggy code. >-- >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. heap sort: average N log N, worst case N log N quick sort: average N log N, worst case N^2 But heap sort is more complicated, requires more code and generally runs slower than quick-sort for random data. Quick-Sort is more fragile, and is realy bad for sorting sorted data. So, heap sort CAN be faster than quick-sort, but it is false to clain that it is ALWAYS faster. In general it is good to know a number of sorting algoriths and use the one best suited to the data being sorted. -- The AnArChIsT! Anarchy! Not Chaos! aka Alex Russell alexad3@iceonline.com