Path: csiph.com!eternal-september.org!feeder.eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail From: Tim Rentsch Newsgroups: comp.lang.c Subject: Re: Challenge for Feeb: dealing with large numbers in C Date: Mon, 04 Nov 2019 17:02:09 -0800 Organization: A noiseless patient Spider Lines: 92 Message-ID: <86d0e7f84u.fsf@linuxsc.com> References: <3pkrF.1790269$HWr.573547@fx36.am4> <87y2xbvuzb.fsf@bsb.me.uk> <877e4uvstq.fsf@bsb.me.uk> <90254a82-7571-4767-9d6e-90f0d51e6d4c@googlegroups.com> <87wocrtr2y.fsf@bsb.me.uk> <87lft6rqy6.fsf@bsb.me.uk> <5a9c3f4b-1204-4d40-8d5b-438b4cfe3bf3@googlegroups.com> <87a79lsmm7.fsf@bsb.me.uk> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Info: reader02.eternal-september.org; posting-host="59b683b75f73ead2c1b20aa011ddc5ef"; logging-data="29356"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+CRaxm0nGXiyu97Uz9qQafxkBSU8qKxOQ=" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:gN/Cv7l5AiYwkWLHUbloVnPxn+0= sha1:vIoRXaF79hSAkxLCbD1Kt3iknZA= Xref: csiph.com comp.lang.c:147590 Ben Bacarisse writes: > Malcolm McLean writes: > >> On Sunday, 27 October 2019 18:20:20 UTC, Ben Bacarisse wrote: >> >>> Eh? A learner see how insertion sort can be usefully replaced with >>> merge sort, heap sort, shell sort, quick sort, etc. Is bubble sort's >>> advantage that it is bad enough to replace with another quadratic >>> algorithm? That's an odd reason to teach it. >> >> Usually bubble sort will be the first algorithm taught (other than >> things like the pencil and paper method for long multiplication, >> which aren't understood at the time to be algorithms). > > Most such courses include data structures, so many algorithms may well > have been covered by the time in-place array sorting is discussed. > Anyway, the question is why bother with bubble sort when the time comes? > >> Next lesson is other sort methods the students can devise themselves, >> which will usually be O(N^2) algorithms, and a discussion of the advantages >> and disadvantages. So you are teaching that some algorithms are better >> than others in different circumstances. > > All good provided (a) bubble sort isn't taught unless it comes up as a > student-devised algorithm, and (b) the students understand that there > are no situations in which bubble sort would be the best choice. In > practice the problem is that, after taking some courses, the students > /can't/ choose because they can't remember any other algorithm than the > not-really-bubble-sort that's being discussed here. > > A key outcome should be that the students understand that insertion sort > is the best choice when a simple quadratic algorithm will do. They > should be able to come up with this: > > for (int i = 1; i < n; i++) > for (int j = i; j > 0 && A[j-1] > A[j]; j--) > swap(&A[j-1], &A[j]); > > as easily as the dreaded quasi bubble sort. It's not hard -- all the > bounds are logical. > >> Third lesson is quicksort, and the concept of big O notation for >> algorithms. > > I would have already covered big O. Sorting algorithms have actual, > average and worst-case complexities so its better, in my opinion, to > have big O already reasonably well understood by having used it for > simpler algorithms. Just a few personal reactions or observations. For many of the comments made about bubble sort versus insertion sort (or other sorting methods), whether one agrees or not depends on what qualifies as "bubble sort" and how one understands the different algorithms. For me the simple nested loop for( int m = n; m > 1; m-- ){ for( int i = 1; i < m; i++ ){ if( a[i-1] > a[i] ) swap( &a[i-1], &a[i] ); } } qualifies as a bubble sort (probably because this was the first way I learned it, although I don't remember if it was), with any sort of early exit as just an embellishment or optimization. I find bubble sort easier to understand than, eg, insertion sort not because the code is simpler but because it is conceptually simpler. Obviously that impression is a subjective one, but in essence that is what I'm trying to point out - which is simpler or more comprehensible depends on how one thinks of the various algorithms. Whether one considers teaching bubble sort a waste of time depends on what one thinks we are hoping to accomplish in teaching a course on Algorithms. In my view that is a lot more than just being able to program the various algorithms. Just learning how to code up a particular algorithm is usually better done by consulting a reference such as Numerical Recipes. Bubble sort has little to offer as a practical sorting algorithm. But learning about bubble sort, and how it relates to other sorting methods, carries a fair amount (as I see it, in case that needs repeating) of educational value beyond just learning how to code it. I don't know how common it is for students coming out of a course on Algorithms to reach reflexively for bubble sort before other, faster (even if still quadratic) sorting algorithms. If and when that happens clearly it indicates some sort of problem with how the course was taught. That doesn't mean bubble sort should just be left out necessarily -- it depends on what the alternatives are and what educational value we think those other possibilities may provide.