Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.programming > #5867
| From | Kaz Kylheku <kaz@kylheku.com> |
|---|---|
| Newsgroups | comp.programming |
| Subject | Re: What do they teach in school today? |
| Date | 2015-09-16 18:54 +0000 |
| Organization | Aioe.org NNTP Server |
| Message-ID | <20150916113743.747@kylheku.com> (permalink) |
| References | (8 earlier) <87fv2lgcv9.fsf@bsb.me.uk> <msvm9f$3gm$1@news.albasani.net> <mt0t8m$au0$1@dont-email.me> <mt18h7$411$1@news.albasani.net> <irbjvalqumg3kbl7tdoen4btl0kj3e9u75@4ax.com> |
On 2015-09-16, Robert Wessel <robertwessel2@yahoo.com> wrote: > On Sat, 12 Sep 2015 08:10:09 -0500, BGB <cr88192@hotmail.com> wrote: > >>On 9/12/2015 5:04 AM, James Harris wrote: >>> "BGB" <cr88192@hotmail.com> wrote in message >>> news:msvm9f$3gm$1@news.albasani.net... >>> >>> ... >>> >>>> there was an class for algorithms, but it was fairly rudimentary, like >>>> implementing linked lists and bubble sort. >>> >>> Anything that teaches bubble sort has to be rudimentary! I remember one >>> person saying that it should never be taught to anyone. The course below >>> teaches eight (yes, eight) sorting methods and not one of them is bubble >>> sort. >>> >> >>it is sometimes useful, either if one doesn't care (because N is always >>small), or (along with selection or insertion sort) as a fallback case >>for quicksort. > > > The complaint about bubble sort is that not only is insertion sort > faster (typically by a factor of two), insertion sort is a *simpler* > algorithm as well, usually requiring fewer lines of code to implement. Yes; for instance insertion sort doesn't have to calculate the silly "are we done?" flag on every pass, unlike bubble sort. The condition of being done proceeds from the way insertion sort partitions the array between unprocessed and processed elements. > So what does bubble sort have going for it, except (as Knuth said), a > catchy name? Bubble sort has perhaps this "virtue". Suppose that it is not required that some items be sorted immediately, only that they eventually settle into a sorted order, little by little. Once in a while, when we have spare cycles, we perform a single bubble sort pass, and the items are all closer to where they should be after that pass. That could be a desirable property, in some imaginable situation. Also, it seems as if bubble sort can be nicely parallelized. Combinatorial circuits can compare adjacent elements and produce the values for the next array. All that is left to do is supply a clock signal to latch the output back into the array. The implementation is easy because the elementary operations of bubble sort are localized. By contrast, insertion sort requires the treatment of a single element in one step of the algorithm to have a global effect on the entire array. > FWIW, bubble sort appears to be reasonably applicable to the one tape > sorting problem, but that's not really of much relevance, and even in > the past trying to sort with one tape was more desperation than > anything else. Bubble sort is useful in the education of newbie computer scientists. It's a nice example of an algorithm where some narrowly confined local effect, when repeated over the data, brings about a global property. It's not obvious from the structure of bubble sort that it's getting all the items in order. For people who have no concept of an algorithm or computer programming, bubble sort is eye opening. Because bubble sort is "bad", that also has educational value; it can be used as a springboard to into other algorithms, introducing the topic of how there exist multiple algorithms to solve the same problem, which have different trade offs, and that sometimes algorithms have so few virtues that they get abandoned. If you don't teach bubble sort, then you can't explain why insertion sort is better than bubble sort. All you can do is tell the students is that there exists something called bubble sort (which you will not teach) and that it's to be taken upon your word that insertion sort is superior.
Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
What do they teach in school today? "J. Clarke" <j.clarke.873638@gmail.com> - 2015-08-20 18:17 -0400
Re: What do they teach in school today? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-08-20 23:56 +0100
Re: What do they teach in school today? fir <profesor.fir@gmail.com> - 2015-08-20 16:10 -0700
Re: What do they teach in school today? Kaz Kylheku <kaz@kylheku.com> - 2015-08-20 23:55 +0000
Re: What do they teach in school today? Julio Di Egidio <julio@diegidio.name> - 2015-08-24 04:28 -0700
Re: What do they teach in school today? Leo <chris.w.l.macleod@sympatico.ca> - 2015-08-20 21:21 -0400
Re: What do they teach in school today? BGB <cr88192@hotmail.com> - 2015-08-23 09:33 -0500
Re: What do they teach in school today? fir <profesor.fir@gmail.com> - 2015-08-23 09:47 -0700
Re: What do they teach in school today? BGB <cr88192@hotmail.com> - 2015-08-23 14:45 -0500
Re: What do they teach in school today? "J. Clarke" <j.clarke.873638@gmail.com> - 2015-08-23 23:27 -0400
Re: What do they teach in school today? BGB <cr88192@hotmail.com> - 2015-08-24 09:48 -0500
Re: What do they teach in school today? "J. Clarke" <j.clarke.873638@gmail.com> - 2015-08-25 00:49 -0400
Re: What do they teach in school today? BGB <cr88192@hotmail.com> - 2015-08-25 09:58 -0500
Re: What do they teach in school today? "J. Clarke" <j.clarke.873638@gmail.com> - 2015-08-28 19:30 -0400
Re: What do they teach in school today? "James Harris" <james.harris.1@gmail.com> - 2015-09-05 20:49 +0100
Re: What do they teach in school today? BGB <cr88192@hotmail.com> - 2015-09-11 00:26 -0500
Re: What do they teach in school today? "James Harris" <james.harris.1@gmail.com> - 2015-09-12 10:58 +0100
Re: What do they teach in school today? BGB <cr88192@hotmail.com> - 2015-09-12 08:06 -0500
Re: What do they teach in school today? "James Harris" <james.harris.1@gmail.com> - 2015-09-12 15:20 +0100
Re: What do they teach in school today? BGB <cr88192@hotmail.com> - 2015-09-13 00:53 -0500
Re: What do they teach in school today? "J. Clarke" <j.clarke.873638@gmail.com> - 2015-09-13 12:19 -0400
Re: What do they teach in school today? BGB <cr88192@hotmail.com> - 2015-09-14 00:32 -0500
Re: What do they teach in school today? "J. Clarke" <j.clarke.873638@gmail.com> - 2015-09-14 07:17 -0400
Re: What do they teach in school today? BGB <cr88192@hotmail.com> - 2015-09-14 09:29 -0500
Re: What do they teach in school today? "J. Clarke" <j.clarke.873638@gmail.com> - 2015-09-12 13:11 -0400
Re: What do they teach in school today? "James Harris" <james.harris.1@gmail.com> - 2015-09-05 20:55 +0100
Re: What do they teach in school today? "J. Clarke" <j.clarke.873638@gmail.com> - 2015-09-07 20:20 -0400
Re: What do they teach in school today? BGB <cr88192@hotmail.com> - 2015-09-11 00:44 -0500
Re: What do they teach in school today? BGB <cr88192@hotmail.com> - 2015-09-11 08:29 -0500
Re: What do they teach in school today? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-09-11 17:05 +0100
Re: What do they teach in school today? Mark Carroll <mtbc@bcs.org> - 2015-09-11 17:07 +0100
Re: What do they teach in school today? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-09-11 17:27 +0100
Re: What do they teach in school today? "J. Clarke" <j.clarke.873638@gmail.com> - 2015-09-12 12:51 -0400
Re: What do they teach in school today? "Charles Richmond" <numerist@aquaporin4.com> - 2015-09-11 14:55 -0500
Re: What do they teach in school today? "J. Clarke" <j.clarke.873638@gmail.com> - 2015-09-12 12:54 -0400
Re: What do they teach in school today? BGB <cr88192@hotmail.com> - 2015-09-11 17:52 -0500
Re: What do they teach in school today? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-09-12 00:23 +0100
Re: What do they teach in school today? BGB <cr88192@hotmail.com> - 2015-09-11 22:45 -0500
Re: What do they teach in school today? "J. Clarke" <j.clarke.873638@gmail.com> - 2015-09-12 12:56 -0400
Re: What do they teach in school today? "James Harris" <james.harris.1@gmail.com> - 2015-09-12 11:04 +0100
Re: What do they teach in school today? BGB <cr88192@hotmail.com> - 2015-09-12 08:10 -0500
Re: What do they teach in school today? "James Harris" <james.harris.1@gmail.com> - 2015-09-12 15:24 +0100
Re: What do they teach in school today? Richard Heathfield <rjh@cpax.org.uk> - 2015-09-12 15:36 +0100
Re: What do they teach in school today? BGB <cr88192@hotmail.com> - 2015-09-12 23:24 -0500
Re: What do they teach in school today? Robert Wessel <robertwessel2@yahoo.com> - 2015-09-16 13:08 -0500
Re: What do they teach in school today? Kaz Kylheku <kaz@kylheku.com> - 2015-09-16 18:54 +0000
Re: What do they teach in school today? Robert Wessel <robertwessel2@yahoo.com> - 2015-09-17 00:15 -0500
Re: What do they teach in school today? Chad <cdalten@gmail.com> - 2015-09-25 21:08 -0700
Re: What do they teach in school today? "J. Clarke" <j.clarke.873638@gmail.com> - 2015-09-12 12:49 -0400
Re: What do they teach in school today? BGB <cr88192@hotmail.com> - 2015-09-12 19:56 -0500
Re: What do they teach in school today? "James Harris" <james.harris.1@gmail.com> - 2015-09-05 21:21 +0100
Re: What do they teach in school today? Mark Carroll <mtbc@bcs.org> - 2015-09-05 22:54 +0100
Re: What do they teach in school today? "James Harris" <james.harris.1@gmail.com> - 2015-09-05 23:17 +0100
Re: What do they teach in school today? Mark Carroll <mtbc@bcs.org> - 2015-09-06 09:59 +0100
Re: What do they teach in school today? "James Harris" <james.harris.1@gmail.com> - 2015-09-06 11:11 +0100
Re: What do they teach in school today? "J. Clarke" <j.clarke.873638@gmail.com> - 2015-09-07 19:59 -0400
Re: What do they teach in school today? "Charles Richmond" <numerist@aquaporin4.com> - 2015-09-11 14:59 -0500
csiph-web