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: 103376,97188312486d4578 X-Google-Attributes: gid103376,public X-Google-Thread: 1014db,6154de2e240de72a X-Google-Attributes: gid1014db,public X-Google-Thread: fc89c,97188312486d4578 X-Google-Attributes: gidfc89c,public X-Google-Thread: 109fba,baaf5f793d03d420 X-Google-Attributes: gid109fba,public From: ok@goanna.cs.rmit.edu.au (Richard A. O'Keefe) Subject: Re: Should I learn C or Pascal? Date: 1996/08/15 Message-ID: <4uu9v3$hrp@goanna.cs.rmit.edu.au>#1/1 X-Deja-AN: 174604454 references: <4u7hi6$s2b@nntp.seflin.lib.fl.us> <4uo74j$95p@ns.broadvision.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-15T00:00:00+00:00 List-Id: 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.