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=0.2 required=5.0 tests=BAYES_00,INVALID_MSGID, REPLYTO_WITHOUT_TO_CC autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 109fba,baaf5f793d03d420 X-Google-Attributes: gid109fba,public X-Google-Thread: 1014db,6154de2e240de72a X-Google-Attributes: gid1014db,public X-Google-Thread: fc89c,97188312486d4578 X-Google-Attributes: gidfc89c,public X-Google-Thread: 103376,97188312486d4578 X-Google-Attributes: gid103376,public From: Lawrence Kirby Subject: Re: What's the best language to start with? [was: Re: Should I learn C or Pascal?] Date: 1996/09/04 Message-ID: <841797569snz@genesis.demon.co.uk>#1/1 X-Deja-AN: 178330672 x-nntp-posting-host: genesis.demon.co.uk references: <4uaqqg$203@mulga.cs.mu.OZ.AU> <01bb84b4$75304ce0$87ee6fce@timpent.airshields.com> <4ubnhr$714@news1.mnsinc.com> <01bb8536$892ee260$87ee6fce@timpent.airshields.com> <4ud8m5$ka5@news1.mnsinc.com> <320bf503.8426726@nntp.ix.netcom.com> x-mail2news-path: genesis.demon.co.uk organization: none reply-to: fred@genesis.demon.co.uk newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada Date: 1996-09-04T00:00:00+00:00 List-Id: In article rchiu@cs.iastate.edu "Richard Chiu" writes: >miker3@ix.netcom.com (Mike Rubenstein) writes: >>But that is not always true. > >>A number of years ago I developed a program that had to do a large >>number of sorts with the following characteristics: > >> 1. The mean number of items to be sorted was about 5. In a >> test sample of a million cases, the larges number of items >> to be sorted was 35. > >> 2. The items were usually in order. In the test sample, 90% >> were in order, and most of the rest were in order except >> for a single interchange of adjacent items. Only 8 were >> out of order by more than three interchanges or required >> interchanges of nonadjacent items. > >>Care to try this with quicksort? or heapsort? A good old O(n^2) >>insertion sort works quite nicely. > >By the same thread of reasoning, a program that does nothing but >reture the inputs will be the best algorithm for sorting if the >numbers are already sorted. (Which is true!) However it wasn't stated that the numbers were already in order, just *usually* in order. It may also mean that in cases where items aren't exactly in order they are still nearly ordered. -- ----------------------------------------- Lawrence Kirby | fred@genesis.demon.co.uk Wilts, England | 70734.126@compuserve.com -----------------------------------------