Should Bubble Sort Be Taught?

[Herbal Deity]

Inspiration in this thread.

I think it tends to be the first sorting algorithm taught in many courses, but I struggle to understand why. It's not necessarily any simpler or easier to understand than insertion or selection sort. I really don't think it should be taught at all (except for maybe an aside as an example of a bad algorithm you should never ever use).

I still see people in my course, 3 years in, using bubble sort for some small programming tasks because it was the first one taught to them, and thus they find it the easiest. Of course that's really their fault for not bothering to study complexity and performance of algorithms, but still, I think bubble sort should never have been taught as being in any way acceptable in the first place.

Thoughts?

[sean_84]

Unless the programming task is to explicitly implement a sorting algorithm, it would be best just to use whatever sort function is provided by the language you are using. This function should be highly optimised (for example read the paper here: http://citeseerx.ist.psu.edu/viewdoc...10.1.1.14.8162), and for general data sorting, you're unlikely to write anything better yourself.

So when sorting algorithms are being taught in college, I think what should be focused on is that multiple algorithms can solve a problem, but with different complexity, and different best/worst/average performances, and how to analyse algorithms to determine these. So when you are solving other problems you can use these techniques to avoid very inefficient approaches.

Still, there's no good reason to even mention bubble sort when insertion-sort is always as good, but usually better and very easy to implement and understand. I guess it was the first algorithm that lecturers learnt so they continue with the tradition

[fergalr]

I don't see any particular harm in teaching it.

If people are using it 3 years into a programming course, the problem isn't that they were taught how to do bubble sort - there's something else that's going very wrong.

Why are they still implementing their own sorting algorithms on an ad-hoc basis? Have they not learned to use libraries by now?
Lets pretend they hate using other peoples libraries. You seem to imply they are reimplementing it each time.
If they are using their own sorting algorithm again and again, why haven't they at least written their own version of quicksort by now, or something else they are reusing?

Really, I don't think that problem has anything to do with them being taught bubblesort. I don't think its an algorithm particularly worth teaching - I think insertion sort is easier conceptually, but thats just me personally. But I don't see any harm, if it fits usefully into a first course on algorithms.

Obviously programmers should be told when and when not to use it.
But really, after 3 years, they should no longer need to be told this sort of thing - it should be obvious to them. If they aren't familiar with the absolute basics of complexity analysis, to the extent that they can reason themselves that its not a great algorithm to use on an ongoing basis, then they have bigger problems than that their data won't sort quickly.

[Sparks]

Originally Posted by sean_84

Unless the programming task is to explicitly implement a sorting algorithm, it would be best just to use whatever sort function is provided by the language you are using.

Inevitably thought, teaching sorting is the main reason you do any sorting, at least at the level where bubble sort would be taught.

As to why you'd teach bubble sort, well, you need some sort of baseline. And bubble sort does have one advantage - it might be slow and inefficient, but it is a good baseline for teaching purposes (as in, pointing out that it doesn't work well with caches and pipelines and then showing approaches which do; pointing out that it's slow and then showing faster approaches; and so on).

[SBS]

Teach them all. The bubble sort is a "classic" - it makes sense in a real world environment, even if it isnt the most efficient algorithm. It helps to learn the basic search algorithms before trying to conquer some of the more obtuse academic (and alright - effficient) solutions.

[fergalr]

Originally Posted by SBS

Teach them all. The bubble sort is a "classic" - it makes sense in a real world environment, even if it isnt the most efficient algorithm.

By that, do you mean it makes good intuitive sense to someone who is learning this sort of thing for the first time?
I agree its easier to get your head around than, say, quicksort, but dont see much advantage over insert sort.

Originally Posted by SBS

It helps to learn the basic search algorithms before trying to conquer some of the more obtuse academic (and alright - effficient) solutions.

[Herbal Deity]

Originally Posted by fergalr

I agree its easier to get your head around than, say, quicksort

I suppose an advantage would be that understanding bubble sort is a stepping stone to understanding quicksort.

Re: why people wouldn't just use libraries on my course - I mean college assignments involving low level C stuff, not in a project for a software engineering course.

[fergalr]

Originally Posted by Herbal Deity

I suppose an advantage would be that understanding bubble sort is a stepping stone to understanding quicksort.

Re: why people wouldn't just use libraries on my course - I mean college assignments involving low level C stuff, not in a project for a software engineering course.

Where you don't even have access to the C standard library? Is it some sort of very low level embedded hardware stuff?
Even then, I'm at a loss as to why they'd right their own sorting algorithm each time, and not just reuse an implementation for earlier?

[Herbal Deity]

No, it's not embedded hardware stuff and yes we do have access to C libraries. You're reading a bit too much into this, however. It's about the tendancy of students in my year to use bubble sort over insertion or selection sort when asked to implement a basic sorting algorithm (which, for example, we had to do for an assignment involving analysing the workings of a compiler this year).

Will they ever have to do this in a real life job? Probably not, but to think bubble sort is acceptable is a pretty poor programming mindset IMO.

I suppose that perhaps the real question is why complexity analysis hasn't been taught well enough in my course...

[fergalr]

Originally Posted by Herbal Deity

No, it's not embedded hardware stuff and yes we do have access to C libraries.

Well, then, surely they should just be using the qsort function?

Originally Posted by Herbal Deity

You're reading a bit too much into this, however.

If they are rewriting their own implementations every time rather than using the library, then its bad.

Originally Posted by Herbal Deity

It's about the tendancy of students in my year to use bubble sort over insertion or selection sort when asked to implement a basic sorting algorithm (which, for example, we had to do for an assignment involving analysing the workings of a compiler this year).

If the only reason to use it is so you have something to analyse in the compiler assignment, then it doesn't matter whether they implement bubble sort or insertion sort. That wasn't the impression I got from your earlier post; fair enough.

Originally Posted by Herbal Deity

Will they ever have to do this in a real life job? Probably not, but to think bubble sort is acceptable is a pretty poor programming mindset IMO.

Again, for a compiler assignment where you just have to analyse a compiler, it doesn't matter whether you use bubble sort or insertion sort.

For normal development, it doesn't matter whether they write bubble sort or insertion sort, either of those show 'a pretty poor programming mindset', if they do so in place of just using the provided library functions.

Originally Posted by Herbal Deity

I suppose that perhaps the real question is why complexity analysis hasn't been taught well enough in my course...

Just to be clear, you come across as lamenting the tendency to use
"bubble sort over insertion or selection sort" in your post. Are you aware of the relative complexities of these 3 algorithms? (also, vs, say quicksort etc)

[Herbal Deity]

Originally Posted by fergalr

Just to be clear, you come across as lamenting the tendency to use
"bubble sort over insertion or selection sort" in your post.

I'm lamenting the tendancy to teach bubble sort as the quintessential "simple sorting algorithm". (yes, I do understand that the bubblesort and insertion sort are both O(n^2), and that quicksort etc. are far better)

Forget about what I said about my year. We have some courses where we're expected to use libraries, we have others where we're not really encouraged to. The relative merits and demerits of this is a discussion for another thread.

[fergalr]

Originally Posted by Herbal Deity

I'm lamenting the tendancy to teach bubble sort as the quintessential "simple sorting algorithm".

Forget about what I said about my year. We have some courses where we're expected to use libraries, we have others where we're not really encouraged to. The relative merits and demerits of this is a discussion for another thread.

Fair enough, forgotten.

In a situation where people just have a few things to sort in a toy program, and aren't allowed use a library or reuse code from elsewhere (in 3rd year??), then I don't see much difference as to whether they use bubble or insertion sort.

Personally, I don't have an issue if people want to teach it as the first example of a sorting algorithm.

I'd prefer to teach selection sort as being more basic, insertion sort as being an improvement on that, and then bubble sort as an interesting variation that doesn't improve much. But thats just personal preference, because I notice that bubble sort takes some people a while to 'get', whereas noone has a problem with selection sort :-)
I'd probably also teach people to generate all permutations, and check which one was sorted.

[PhantomBeaker]

I reckon it should, if only because it's one of the easiest for a student to generalise into an algorithm with an independant comparator. ("I want you to sort these objects. Don't know how to order 2 of those objects? Here, I'll give you a function that decides for you.")

I work with scripting languages a lot (perl and some python mostly), and one of the things I occasionally have to do is sort something arbitrary. That means developing a function that will compare 2 of those arbitrary objects and give a result that will order the two. If I happen to confuse myself while working on it, I think about it in the context of a bubble sort. Sure, a comparator is the core to any of those sorting algorithms but bubble is a nice way to think about it.

Also, correct me if I'm wrong, but I remember hearing that bubble isn't so bad when you think of it in multi-processor situations; sure it's still O(n^2), but it can be easily adapted so it scales relatively evenly across the processors, as opposed to some that can't divide the work out into independant units of work. (That said, I still really like merge sorts - can be made to scale well across processors, and is a beautiful algorithm) (Also to be noted, I don't do multi-threaded programming myself, so I'm not speaking from experience)

As others have said, most of the time, the students should be using libraries anyway, so the algorithm itself doesn't matter, but if they need to think about it in a concrete way, the bubble sort isn't that headwrecking.

Just my 2c,
Aoife

[bonkey]

Originally Posted by sean_84

Still, there's no good reason to even mention bubble sort when insertion-sort is always as good, but usually better and very easy to implement and understand.

Funnily, I think that in itself is an excellent reason to teach bubble-sort.

Learn and understand an algorithm. Then learn another which is never worse in performance. Then find some which can be better, depending on certain factors.

Learn how to abstract those lessons and you've learned far more valuable stuff then how to sort.

[fergalr]

Originally Posted by PhantomBeaker

I reckon it should, if only because it's one of the easiest for a student to generalise into an algorithm with an independant comparator. ("I want you to sort these objects. Don't know how to order 2 of those objects? Here, I'll give you a function that decides for you.")

Obviously, all of the algorithms mentioned are comparison sorts, but I do see that there is something natural and intuitive about the 'compare and swap if' primitive as used in bubble, so I think thats a good point.

Originally Posted by PhantomBeaker

I work with scripting languages a lot (perl and some python mostly), and one of the things I occasionally have to do is sort something arbitrary. That means developing a function that will compare 2 of those arbitrary objects and give a result that will order the two. If I happen to confuse myself while working on it, I think about it in the context of a bubble sort. Sure, a comparator is the core to any of those sorting algorithms but bubble is a nice way to think about it.

Also, correct me if I'm wrong, but I remember hearing that bubble isn't so bad when you think of it in multi-processor situations; sure it's still O(n^2), but it can be easily adapted so it scales relatively evenly across the processors, as opposed to some that can't divide the work out into independant units of work.

That hadn't occurred to me as a teaching benefit. Its an interesting point, and maybe one that will be increasingly relevant as parallel programming becomes more an more important to the discipline of programming - maybe we'll see it introduced earlier into teaching courses?

Originally Posted by PhantomBeaker

(That said, I still really like merge sorts - can be made to scale well across processors, and is a beautiful algorithm) (Also to be noted, I don't do multi-threaded programming myself, so I'm not speaking from experience)

Nerd

Originally Posted by PhantomBeaker

As others have said, most of the time, the students should be using libraries anyway, so the algorithm itself doesn't matter, but if they need to think about it in a concrete way, the bubble sort isn't that headwrecking.

Just my 2c,
Aoife