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: 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: dewar@cs.nyu.edu (Robert Dewar) Subject: Re: Teaching sorts [was Re: What's the best language to start with?] Date: 1996/08/19 Message-ID: #1/1 X-Deja-AN: 175936387 references: <31FBC584.4188@ivic.qc.ca> <01bb83f5$923391e0$87ee6fce@timpent.airshields.com> organization: Courant Institute of Mathematical Sciences newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada Date: 1996-08-19T00:00:00+00:00 List-Id: Stephen says "Having just done some testing, I don't think I can agree with your statement about bubble sort being optimial on nearly sorted arrays. On the cases I tested insertion sort seems to be much quicker, unless the two arrays are so nearly sorted that I can't easily measure the time to sort them. I have not used any special cases of the sort you suggest in the insertion sort. The bubble sort function is also over 50% more code than the insertion sort so I can't call it simpler." But! the cases in your "unless" case are exactly the ones where the difference is appreciable, so you are not measuring the interesting cases. What do you mean, you "can't easily measure the time to sort them" Of course you can, use a completely sorted vector and just do the sort enough times so you can measure it. Of course it may well be that you get an anomolous result due to compiler optimnizations applying in one case and not the other, so it is best to test this using carefully optimized hand written assembler, to minimize difficulties of this type, but that of course is much harder work!