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/summary?doi=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

sean_84 wrote: »

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).

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

Deleted User wrote: »

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.

Deleted User wrote: »

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

Herbal Deity

fergalr wrote: »

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

Herbal Deity wrote: »

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

Herbal Deity wrote: »

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?

Herbal Deity wrote: »

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.

Herbal Deity wrote: »

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.

Herbal Deity wrote: »

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.

Herbal Deity wrote: »

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

fergalr wrote: »

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

Herbal Deity wrote: »

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

sean_84 wrote: »

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

PhantomBeaker wrote: »

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.

PhantomBeaker wrote: »

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?

PhantomBeaker wrote: »

(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

PhantomBeaker wrote: »

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

sean_84

bonkey wrote: »

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.

The problem is that some people remember how bubble-sort works, but don't remember that it's rubbish. Maybe when you first learn about it, the simplicity is appealing, and it's not an algorithm that most people would think of by themselves. If you gave someone a shuffled deck of cards and asked them to sort them, I can't imagine anyone would use bubble-sort (unless they were a CS student )

But I agree that the main lesson in learning sorting algorithms is how to analyse and compare algorithms.

I think that the vast majority of programmers shouldn't be implementing sorting algorithms (not because they can't, but because there's no reason to). Unless you know something else about the data, such as only 1 item is out of place (use insertion-sort), or you've tested a radix-sort implementation and it's better than a generic quick sort.

dloob

When I was doing sorts in college we were using Modula-2
No libaries for us.
Bubble sort was among them, I think it was the first.
It helps get people in the mindset of sorting, we didn't spend long on it and moved on the selection and rest.

I'd like to see someone sort a deck of cards with quicksort

Bill-e

LoL I've been programming for a year or 2 now and I remember this coming up in college. They made it sound really difficult so I skipped it. Having looked at it now I don't know what the big deal was.

fergalr

dloob wrote: »

When I was doing sorts in college we were using Modula-2
No libaries for us.
Bubble sort was among them, I think it was the first.
It helps get people in the mindset of sorting, we didn't spend long on it and moved on the selection and rest.

I'd like to see someone sort a deck of cards with quicksort

Isn't the internet wonderful?

http://www.youtube.com/watch?v=cNB5JCG3vts

sean_84

When sorting cards, i reckon it takes more time to move the cards then to make the comparison, so I don't think quick-sort is the best approach

Herbal Deity

So how many people have gone looking for a pack of cards?