5 ms·

The "point" is that it is one of the three intuitive sorting algorithms that someone unfamiliar with algorithmic complexity will write when asked to write a com

The "point" is that it is one of the three intuitive sorting algorithms that someone unfamiliar with algorithmic complexity will write when asked to write a computer sorting algorithm (and happened to be the first sort I wrote when tasked with just that in college long ago). This makes it a useful thing to discuss because it's so clearly inferior to the other two despite being just as intuitive.

bonoboTP 6y ago
Insertion sort seems more intuitive. Just take the next item and file it at its correct position. I think the whole "swap neighbors and scan many times" thing isn't something a novice would come up with.
- quietbritishjim 6y ago
  The refutation of that is in the comment you're replying to: > [Bubble sort] happened to be the first sort I wrote when tasked with just that in college long ago
- virgilp 6y ago
  If you need an additional datapoint, bubble sort is also the first sorting algorithm I came up with. I find it super intuitive - the only slightly-less intuitive part maybe is that you need to do the outer loop at most N times (in my implementation, the outer loop was `while(changed)` where `changed` would be set to `true` if any swap was performed in the inner loop ).
  - bonoboTP 6y ago
    Even though I know the algorithm, I still find that I need to think a nontrivial amount to see why it will not miss anything. I mean, sure, you are strictly improving the "sortedness" by a discrete amount in each pass and crucually, you don't destroy any progress you made before (not totally trivial), and there's only a finite amount of "sortedness" to attain, so it will converge to the sorted state. But how exactly and, as you say, after how many iterations, is not so clear. In more complex algorithms, you may get stuck in a local optimum with such a greedy approach though. But contrast that with insertion sort. I have a sorted pile that grows after each insertion. I find it trivially clear that it works and when I will be done. It's also something that people will intuitively do in the physical world to sort paper documents I think: just grow a pile of sorted documents by adding the next one in the right place.
- ernesth 6y ago
  My anecdotal experience as a teacher is that when tasked with implementing sort, students go for selection sort. However when asked to do it in real life on a bundle of graded exam sheets, if I ask them to sort alphabetically, they will do insertion sort, if I demand to sort by grade, they will bubble sort. The number of sheets may also change their method.
iainmerrick 6y ago
I think this is a bit dangerous because people take away the “I understand and can implement bubble sort” part, but forget the “it’s very inefficient, don’t use it” part. So people end up using bubble sort in production! It doesn’t help that it has such a cute and catchy name.
- coldpie 6y ago
  I don't think I have ever implemented a sort. What modern tooling doesn't provide a sort? Even C has qsort.
  - lebuffon 6y ago
    RISC V Assembler :)
  - iainmerrick 6y ago
    Why even bother teaching it, then? (Semi-serious question, as you're quite right that hardly anyone ever needs to write a sort routine by hand these days.)
    - ogogmad 6y ago
      Maybe it's the things you learn along the way, such as: - Recursion and induction (mergesort, quicksort) - Lower bounds on running time (O(n log n)) - Data structures (heaps in the context of heapsort, binary search trees in the context of treesort, tries in the context of radix sort, etc.) - Difference between worst case and average case (quicksort) - The role of the hidden coefficient in O notation (insertion sort is fast for small n even though its running time is O(n^2)) Etc.
- kadoban 6y ago
  Probably no real fix for that. In algorithms if you only taught the best algo for a particular problem, you'd lose everyone on the first day, and miss out on a lot of analysis/teaching opportunities. Remember that algorithms study isn't just about speed, it's actually about _correctness_ first. Besides, it's pretty rare for someone to need to write their own sorting algorithm anyway, in production. And if they do but they're so addled they do it from memory and randomly pick bubblesort, hey at least it's fairly easy to be correct.

bonoboTP 6y ago

Insertion sort seems more intuitive. Just take the next item and file it at its correct position. I think the whole "swap neighbors and scan many times" thing isn't something a novice would come up with.

quietbritishjim 6y ago
The refutation of that is in the comment you're replying to: > [Bubble sort] happened to be the first sort I wrote when tasked with just that in college long ago
virgilp 6y ago
If you need an additional datapoint, bubble sort is also the first sorting algorithm I came up with. I find it super intuitive - the only slightly-less intuitive part maybe is that you need to do the outer loop at most N times (in my implementation, the outer loop was `while(changed)` where `changed` would be set to `true` if any swap was performed in the inner loop ).
- bonoboTP 6y ago
  Even though I know the algorithm, I still find that I need to think a nontrivial amount to see why it will not miss anything. I mean, sure, you are strictly improving the "sortedness" by a discrete amount in each pass and crucually, you don't destroy any progress you made before (not totally trivial), and there's only a finite amount of "sortedness" to attain, so it will converge to the sorted state. But how exactly and, as you say, after how many iterations, is not so clear. In more complex algorithms, you may get stuck in a local optimum with such a greedy approach though. But contrast that with insertion sort. I have a sorted pile that grows after each insertion. I find it trivially clear that it works and when I will be done. It's also something that people will intuitively do in the physical world to sort paper documents I think: just grow a pile of sorted documents by adding the next one in the right place.
ernesth 6y ago
My anecdotal experience as a teacher is that when tasked with implementing sort, students go for selection sort. However when asked to do it in real life on a bundle of graded exam sheets, if I ask them to sort alphabetically, they will do insertion sort, if I demand to sort by grade, they will bubble sort. The number of sheets may also change their method.

iainmerrick 6y ago

I think this is a bit dangerous because people take away the “I understand and can implement bubble sort” part, but forget the “it’s very inefficient, don’t use it” part. So people end up using bubble sort in production! It doesn’t help that it has such a cute and catchy name.

coldpie 6y ago
I don't think I have ever implemented a sort. What modern tooling doesn't provide a sort? Even C has qsort.
- lebuffon 6y ago
  RISC V Assembler :)
- iainmerrick 6y ago
  Why even bother teaching it, then? (Semi-serious question, as you're quite right that hardly anyone ever needs to write a sort routine by hand these days.)
  - ogogmad 6y ago
    Maybe it's the things you learn along the way, such as: - Recursion and induction (mergesort, quicksort) - Lower bounds on running time (O(n log n)) - Data structures (heaps in the context of heapsort, binary search trees in the context of treesort, tries in the context of radix sort, etc.) - Difference between worst case and average case (quicksort) - The role of the hidden coefficient in O notation (insertion sort is fast for small n even though its running time is O(n^2)) Etc.
kadoban 6y ago
Probably no real fix for that. In algorithms if you only taught the best algo for a particular problem, you'd lose everyone on the first day, and miss out on a lot of analysis/teaching opportunities. Remember that algorithms study isn't just about speed, it's actually about _correctness_ first. Besides, it's pretty rare for someone to need to write their own sorting algorithm anyway, in production. And if they do but they're so addled they do it from memory and randomly pick bubblesort, hey at least it's fairly easy to be correct.