I can't stand Bubble Sort

[Duthomhas]

I can't think of a less-intuitive, more wasteful method of sorting.

And it seems like every intro CS course want's people to write one.If you're going to force your students to learn some random sorting method, why not pick something useful, like mergesort or a counting sort, or even a radix sort? You can actually do interesting, cool stuff with those.

Instead I find myself trying to decide whether I even want to open a thread about someone's bubble sort. The last three I opened turned out to have perfectly fine bubble sorts in them -- the OP had some other problem.

[MiiNiPaa]

"write sorting algorithm implementation" assigment usually given when students have learned only basics of language and still at very beginning level. It is often first "useful" code they write. So anything required additional storage or complex algorithms are out of question. Usually bubblesort, selection sort or insertion sort is chosen.
As I noticed selction sort usually given when students wrote "search largest value in array" function lately, insertion sort when they wrote "insert at arbitrary position" one and bubble sort in other cases.

Naive bubblesort is very simple, easy to write and hard to make mistake in. That why it is probably chosen.

Probably trying to implement sorting at the beginner level isn't the best idea. At more advanced level they could chose interesting algorithm themself, implement it, and make aan essay about it, which would be more useful than writing slow and non-generic one early and instantly abandoning it.

Interesting visualisation (and audialisation) of different sorting methods: https://www.youtube.com/watch?v=kPRA0W1kECg

[Duthomhas]

Don't take this the wrong way, but I know more about pedagogy than you, and I'm not alone in my belief that bubble sort is a horrible sort to teach with.

Selection sort and insertion sort are the simplest choices to begin with. Then move on to a merge sort, which is exceedingly simple and easy to implement. The only trick to get over is it is not in-place, but it is the next step after selection sort.

Naive bubblesort is very simple, easy to write and hard to make mistake in.

You can disagree with me, but simply reblandishing the propaganda I'm complaining about doesn't really forward the conversation.

Bubble sort is only simple in terms of operations to perform. Conceptually, it is not simple, and that is why forums are flooded twice a year with newbies who are finding it hard to write because they keep making mistakes.

The sheer volume of noise about getting it right (and the nearly absolute absence of information about it in any other useful context) make my point for me. If it were so easy and hard to mistake, why the traffic about bubble sorts that aren't working?

I also dislike the visualization. Even people who are not in their first year will look at that and have no idea what is going on. There is no intuitive way to see how the sort is actually accomplishing its task. It's just a cool noise trick for people who already understand what's going on.

In comparison, a simple animation like this is, after maybe a couple of viewings, so much more comprehendable.
http://www.cplusplus.com/faq/sequences/sequencing/sort-algorithms/quicksort/#algorithm

Knowing how to sort things is not the same as knowing how to make the computer's lights blink the right way.
https://xkcd.com/722/

You have to understand what you are doing in order to make it work. And I think that is the primal problem with bubble sort. It isn't readily comprehensible without some 'trust me things eventually get to the right spot' winking from the professor -- if the professor actually bothers to try to explain it (few do, AFAIK -- prove me wrong and you prove the situation is worse than I assert).

[oSGzwA7f]

duoas wrote:

Don't take this the wrong way, but I know more about pedagogy than you,

Wow, great way to start a constructive conversation.

[booradley60]

Duoas wrote:

In comparison, a simple animation like this is, after maybe a couple of viewings, so much more comprehendable.
http://www.cplusplus.com/faq/sequences/sequencing/sort-algorithms/quicksort/#algorithm

Simpler than this?: https://upload.wikimedia.org/wikipedia/commons/c/c8/Bubble-sort-example-300px.gif
I disagree. Especially when it comes time to reify the sort in C++ code.

[Lowest0ne]

That isn't the bubble sort I learned, it's like a mutated selection sort.

We learned bubble and selection sort in the same lecture. The teacher wrapped it up by saying "don't write your own sort methods, use std::sort".

Also,
http://www.youtube.com/watch?v=lyZQPjUT5B4

[Lachlan Easton]

I think bubble sort is far easier to learn and reason about than other sorting methods. The reason so many new programmers come to forums for help with it is because it's normally learned early on, and most of these aren't having trouble with the sort itself. The gif booradley posted is way easier to explain and understand than the one Duoas posted.

[abhishekm71]

I don't know about how difficult/easy it is to teach, but according to me bubble sort is the easiest and one of the most intuitive sorting algorithms to implement. In fact I use it many times "where time complexity is not a constraint"

For other "good" sorting algorithms like mergesort or quicksort, you usually need to have a separate function to carry these out, not-to-mention spend time in debugging your code for boundary conditions etc.

I have to use bubble sort at times when C++ std::sort by itself can't be used. For example if I want to sort two vectors simultaneously depending on the values of one of the vectors.

[MiiNiPaa]

I want to sort two vectors simultaneously depending on the values of one of the vectors.

Can you post an example of that. I have hard time thinking about cases when bublesort would be best choice.

In fact I used single pass of shaker sort once because of nature of the data, but complete bublesort...

[giblit]

most intuitive

I would have to say it is anything but intuitive. That is like saying using 2 loops to find primes with modulus each time is intuitive instead of using a sieve.

[abhishekm71]

@MiNiPaa

Just an example from my code:

for ( int i = 0; i < location.size(); i++ )
        for ( int j = 0; j < location.size() - 1 - i; j++ )
            if ( location[j].first > location[j+1].first ) {
                QPair<int,int> temp = location[j];
                location[j] = location[j+1];
                location[j+1] = temp;
                int tempF = feederNos[j];
                feederNos[j] = feederNos[j+1];
                feederNos[j+1] = tempF;
            }

Here I want to sort the vector location, but I also want the indices of feederNos to remain pointing to the same location. I know there are better choices but this is the simplest I could think of. And it works for my use.

@giblit
Why do you say it is not intuitive. The largest (or the smallest) value just bubbles to the end.

As I said, I don't have any experience in teaching anyone else about bubble sort, but it suits my needs many times.

[MiiNiPaa]

@abhishekm71 You are storing coupled data in differett containers, maintaining relation manually. Smells extremely fishy to me. Even there I would use insertion sort if you need to sort this manually.

[abhishekm71]

@MiNiPaa
You are right. But this (presently) coupled data will need to be decoupled at a later time. They don't have any relation with each other. Only temporary association.

Ofcourse, to be fair, I should state that I am a beginner and not well-versed in designs.

Also, is there any specific reason to use insertion sort, apart from personal preference?

[MiiNiPaa]

Also, is there any specific reason to use insertion sort, apart from personal preference?

Using binary search and memory block moving instead of copying elements one by one for array of POD types will bring complexitivity to O(n·logn). Also insertion sort is simple and you are less likely to made a mistake when reinventing the wheel.

They don't have any relation with each other. Only temporary association.

But they do have relation right now. Why wouldn't you wrap them in pair/tuple to store them in container?

[abhishekm71]

Actually location is already a vector of pairs. I wasn't aware of tuples in C++ (Qt). I thought a vector of vector (or array) would have been an overkill.

Thanks for future reference.

[James Parsons]

Be prepared...(don't ask)

[Computergeek01]

Don't take this the wrong way, but I know more about pedagogy than you

With all due respect Duoas, you're making this statement in a thread that shows you completely missing the point of why bubble sort is taught to beginners. It's not about the sorting method at all, it's used to illustrate embedded loops. It shows the students how to compare every element in an array to every other element; the other sorting methods you mentioned are better then bubble sort precisely because they don't do that. A better, or at least more engaging, illustration for students might be something like Conway's game of Life. But how do you write something like that for a console platform without the code looking absolutely disgusting?

[Duthomhas]

Computergeek01 wrote:

With all due respect Duoas, you're making this statement in a thread that shows you completely missing the point of why bubble sort is taught to beginners. It's not about the sorting method at all, it's used to illustrate embedded loops.

With all due respect yourself, LOL.

Frankly, your statement pegs you as a complete neophyte. You do know that I work in education, right?

Nested loops and sorting algorithms are two distinct concepts, taught at different levels.

Nested loops are typically taught with variations of star pyramid and 2D arrays / matrices, which are much better-suited to the targeted learner objective for understanding nested loops.

And, frankly, anyone teaching nested loops with bubble sort ought to be fired, if for no other reason than he/she is oblivious to the confusion it causes in his/her students. Every educator worth his/her salt knows that confusion indicates a need to reevaluate and prune the current strategy. Failure to do so is, shall we say, cause for concern. (Remediation is indicated.)

Conway's Game of Life is likewise unsuited for the job. Managing the 2D array is the simplest part of such an exercise. And the console problem is a red herring. (Not that it makes a difference. The code can be just as clear on the console as with a GUI: http://www.cplusplus.com/forum/lounge/75168/)


There is a clear preponderance of evidence that bubble sort is not intuitive and causes confusion (even among experts).

Wikipedians confused about bubble sort
http://en.wikipedia.org/wiki/Talk%3ABubble_sort
(Apparently someone had placed mal-formed insertion sort pseudocode on the Wiki -- see the stuff under Wikicode and compare/swap indices being i and j instead of j and j+1. Notice also all the other stuff about it that knowledgeable people are having trouble getting right. It's a fairly large page for such a simple algorithm.)

Here's some other people who agree with me, not the least of which is Donald Knuth, who disparages it:

The Art of Computer Programming: Sorting and Searching, 2 ed., vol. 3. Addison-Wesley, 1998 wrote:

In short, the bubble sort seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems.

Here's from the CS Department at Duke University, replete with references
http://www.cs.duke.edu/~ola/bubble/bubble.html

Eric S. Raymond, et. al claim that using the bubble sort at all is naïve, an error foisted on the ignorant.
http://catb.org/jargon/html/B/bubble-sort.html

This fellow in Finland makes the most direct damning observations
http://warp.povusers.org/grrr/bubblesort_eng.html
http://warp.povusers.org/grrr/bubblesort_misconceptions.html

Even Barack Obama (studied constitutional law) knows better than to Bubble Sort
http://www.youtube.com/watch?v=k4RRi_ntQc8

But hey, who cares anyway? I should have known better than to make a statement like "bubblesort is evil". It's just flame bait for the hoi polloi armchair experts.

Cause I really don't care to hear all the useless arguments defending poor, little bubble sort.

[MiiNiPaa]

Duoas wrote:

But hey, who cares anyway? I should have known better than to make a statement like "bubblesort is evil". It's just flame bait for the hoi polloi armchair experts.

Cause I really don't care to hear all the useless arguments defending poor, little bubble sort.

I was under impression that you are trying to understand why bublesort is so widespread in CS courses.

[Lachlan Easton]

Man, I think we touched a nerve.