3 ms·

I wonder since 25 years or so why bubblesort is considered a viable sort at all. Putting aside its terrible complexity and thus performance, it is not even intu

by kunley 3y ago

I wonder since 25 years or so why bubblesort is considered a viable sort at all. Putting aside its terrible complexity and thus performance, it is not even intuitive. For example, if you look at it, it is not how we humans sort things manually. It is IMO an example of a "following the herd" confusion: some scientist wrote a paper (they must do it to survive, don't they), others mentioned it in a textbook (doesn't hurt to have more pages, huh), others put it in their other textbooks because, well, it was mentioned in the past, and this is how this abomination survives decades..

bradley13 3y ago
FWIW: As an instructor, I used to include bubblesort when talking about sorting algorithms.. I stopped, because too many students saw it presented as an algorithm, and thought it was therefore a valid choice. It is not. As others have pointed out, insertion sort and selection sort are just as simple, but significantly faster. As long as the quantity of data is small, there is nothing wrong with using an n^2 algorithms for sorting. They are simple, robust, stable, and easy to implement correctly. Sure, things may change. In 25 years, you may have 1000 elements instead of 10. If that happens, your successors can change the algorithm to meet the new requirements. That's what software maintenance is all about.
- kunley 3y ago
  Yeah, great points about insertion and selection sort. Thank you for the story and for keeping up the quality of education.
Delk 3y ago
To me, bubble sort is intuitive, as far as sorting algorithms or their detailed implementations go. I absolutely wouldn't sort that way if I were to sort something as a human, but in that case I wouldn't be even trying to figure out an exact systematic logic with its minute details that always gets it right. I'd be thinking in terms of ad hoc problem solving, and possibly some heuristics for speeding it up. When thinking of algorithms in a programming (or CS) sense, getting the exact logic right down to the detail is exactly what you'll need to do. So, to me, those aren't the same kind of intuitive. As is probably common, a bunch of simple sorting algorithms were given as some kinds of introductory examples of algorithms during my first university programming courses. I think those included selection sort, bubble sort and insertion sort. I don't think I initially considered bubble sort the more intuitive one (I think selection sort was it for me). But for some reason, over the years the basic logic of bubble sort became more obvious to me than those other options. So, at least personally, maybe there's something else to it than following the herd. Of course I've never actually written bubble sort in any kind of real code, but it's still perhaps the most intuitive one to me, in terms of detailed algorithms rather than in terms of heuristics for human problem solving. (Merge sort is also about as intuitive to me at least as a general idea.)

by kunley 3y ago

bradley13 3y ago

FWIW: As an instructor, I used to include bubblesort when talking about sorting algorithms.. I stopped, because too many students saw it presented as an algorithm, and thought it was therefore a valid choice. It is not. As others have pointed out, insertion sort and selection sort are just as simple, but significantly faster. As long as the quantity of data is small, there is nothing wrong with using an n^2 algorithms for sorting. They are simple, robust, stable, and easy to implement correctly. Sure, things may change. In 25 years, you may have 1000 elements instead of 10. If that happens, your successors can change the algorithm to meet the new requirements. That's what software maintenance is all about.

kunley 3y ago
Yeah, great points about insertion and selection sort. Thank you for the story and for keeping up the quality of education.

Delk 3y ago

To me, bubble sort is intuitive, as far as sorting algorithms or their detailed implementations go. I absolutely wouldn't sort that way if I were to sort something as a human, but in that case I wouldn't be even trying to figure out an exact systematic logic with its minute details that always gets it right. I'd be thinking in terms of ad hoc problem solving, and possibly some heuristics for speeding it up. When thinking of algorithms in a programming (or CS) sense, getting the exact logic right down to the detail is exactly what you'll need to do. So, to me, those aren't the same kind of intuitive. As is probably common, a bunch of simple sorting algorithms were given as some kinds of introductory examples of algorithms during my first university programming courses. I think those included selection sort, bubble sort and insertion sort. I don't think I initially considered bubble sort the more intuitive one (I think selection sort was it for me). But for some reason, over the years the basic logic of bubble sort became more obvious to me than those other options. So, at least personally, maybe there's something else to it than following the herd. Of course I've never actually written bubble sort in any kind of real code, but it's still perhaps the most intuitive one to me, in terms of detailed algorithms rather than in terms of heuristics for human problem solving. (Merge sort is also about as intuitive to me at least as a general idea.)