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: fc89c,97188312486d4578 X-Google-Attributes: gidfc89c,public X-Google-Thread: 109fba,baaf5f793d03d420 X-Google-Attributes: gid109fba,public X-Google-Thread: 1014db,6154de2e240de72a X-Google-Attributes: gid1014db,public X-Google-Thread: 103376,97188312486d4578 X-Google-Attributes: gid103376,public From: rhoads@george.rutgers.edu (Glenn Rhoads) Subject: Re: Teaching sorts [was Re: What's the best language to start with?] Date: 1996/08/18 Message-ID: <4v75ru$igl@george.rutgers.edu>#1/1 X-Deja-AN: 174919242 references: <31FBC584.4188@ivic.qc.ca> <01bb83f5$923391e0$87ee6fce@timpent.airshields.com> organization: Rutgers University LCSR newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada Date: 1996-08-18T00:00:00+00:00 List-Id: dewar@cs.nyu.edu (Robert Dewar) writes: > Why do people try and teach students Bubblesort? It may be an interlectually > interesting exercise but it is of no use. An insertion sort is simpler and at > least as fast as a bubble sort. For many practical programing problems an > insertion sort is a sensible solution, it is very compact and for small > datasets as fast as anything (Many quicksort implementations switch to > insertion sort for less than about 7 items). The number of times I have > had to redirect graduates who have tried to write a small sort using > Bubblesort (because it was the simplest sort they were taught) or Quicksort > (because they have been taught it is faster in all cases). >The one advantage of bubble sort is that it is close to optimal on sorted >or nearly sorted arrays. You have to be very careful how you write insertion >sort not to require more compares in the fully sorted case, and you will >almost certainly find you require more overhead, because of the two nested >loops. Yes, you could add a special test in the outer loop for already >being in the right place, but then you complicate the inner loop if you >want to avoid repeating this comparison. A bubble sort is certainly a >much simpler solution to the problem of optimal sorting of a sorted >list, and simplicity of solutoins is interesting if performance is NOT >an issue after all. I believe you are confused as to which sort is insertion sort and which is bubble sort. If you replace every occurrence of bubble sort with insertion sort and vice-versa in the above paragraph, then you are correct (as is the poster you are responding to). -- Glenn Rhoads