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.9 required=5.0 tests=BAYES_00 autolearn=ham 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: fc89c,97188312486d4578 X-Google-Attributes: gidfc89c,public X-Google-Thread: 103376,97188312486d4578 X-Google-Attributes: gid103376,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/17 Message-ID: <3214e90b.84660004@nntp.ix.netcom.com> X-Deja-AN: 175007075 references: <4u7hi6$s2b@nntp.seflin.lib.fl.us> <4uo74j$95p@ns.broadvision.com> <4uu9v3$hrp@goanna.cs.rmit.edu.au> organization: Netcom x-netcom-date: Fri Aug 16 8:29:02 PM CDT 1996 newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada,comp.os.msdos.programmer Date: 1996-08-16T20:29:02-05:00 List-Id: ok@goanna.cs.rmit.edu.au (Richard A. O'Keefe) wrote: > 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. Where did you get this idea? Certainly not from the Hoare's paper. In the paper he reports testing on such a machine, but he does not say that quicksort was designed for such a machine. In fact, he concludes that Quicksort is a sorting method ideally adapted for sorting in the random access store of a computer. ... Quicksort is likely to recommend itself as the standard sorting method on most computers with a large enough random access store to make internal sorting worthwhile. He includes the case where the random access store is disk or drum. Not unreasonable on the computers of the early 60s, but not realistic today. In general, today quicksort is not suitable unless the data to be sorted can pretty much be held in real memory. > > 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. It's not that new -- Knuth discusses heapsort with guaranteed O(N log N) performancein his 1973 book. I was unaware that there was ever a version that does not guarantee O(N log N) behavior. But it's very hard to get the constant as low as that for quicksort and quite easy to make O(N log N) behavior almost certain in quicksort. Sometimes heapsort is better for soft real time work, but not always. In fact, if the maximum number of items to be sorted is fixed in advance, insertion sort is often very good if the number is very small and Shell sort for several hundred items. > > 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. Of course, but how often do you sort machine integers? In 35 years of programming, I can count on my fingers how often that problem came up and in most of those cases the amount of data was so small that it would be hard to choose a sort that isn't adequate. > > 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. Sometimes. It pays to think. A number of years ago I did a billing program for a large retailer. Transactions were stored in the order in which they were received and had to be sorted in order of transaction date. For the most part, the data was already sorted correctly. The main exception was that billing transactions for items shipped were batched and processed overnight. In some cases they were not processed for a day or two. If a person placed an order the day after an item was shipped, the data could be out of order. Aside from the fact that the data was almost in order, the number of items to be sorted was quite small (for a variety of reasons it was not desirable to presort all the transactions, so the transactions for each customer were sorted separately). That alone made any sort package undesirable. Here C and C++ are much better than most languages I know. qsort() is generally decent for small sorts (though I'd not use it in the case I jsut mentioned). I've not done much work in them recently, but when I programmed in PL/I and COBOL their sort routines were completely unsuitable if one was doing a large number of small sorts (unlike C's, they were extremely good for very large sorts). Michael M Rubenstein