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.6 required=5.0 tests=BAYES_40,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: dewar@cs.nyu.edu (Robert Dewar) Subject: Re: Teaching sorts [was Re: What's the best language to start with?] Date: 1996/08/14 Message-ID: #1/1 X-Deja-AN: 174148868 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-14T00:00:00+00:00 List-Id: Stephen says 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 d atasets 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. For quick sorts, I prefer heapsort to quicksort, because of its bounded worst case behavior. Note that there is a little-known modification to heap sort that reduces the number of compares to about NlogN compared with the normal 2NlogN (the 2 is where Eachus got the O(2N), though of course constants don't belong in big-O formulas). As far as I know this is not really properly reported in the literature -- I treat it in detail in my 1968 thesis, and it is an excercise in Knuth volume 3 (although his original answer was wrong, I think I kept that $1 Wells Fargo colorful check somewhere as a souvenir :-) P.S. I really prefer to call heapsort treesort3, its original name bestowed by Floyd, the discoverer of this algorithm. Too many people think Knuth invented the algorithm, when all he invented (I think?) was the name -- though of course, as always Knuth is VERY careful, almost fanatically careful, to give full credit to original authors, but someone people sometimes miss these careful credits in the books!