5 ms·

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

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.
smcl 6y ago
I wonder how many people actually write a sort algorithm in production code anymore. I haven't personally seen this, but I guess that doesn't really mean it doesn't exist. What I have seen is pretty horrific abuse of Linq (i.e. repeated lookup of `things.Where(t => t.Id == query.Id).First()` as if it was a dictionary) which might stem from the same root cause - not thinking about what your code is actually doing and why it might be inefficient. It doesn't help that there's that there's those oft-quoted Bentley's Rules of Optimization which gives people an excuse to not care :-/
dragonwriter 6y ago
Huh, like when I learned this (back when I was in elementary school and the class was taught using unstructured BASIC, so the more natural lesson with most things more modern of “rely on your standard library for sorting, unless you have a really good cause to roll your own and then do some research” wasn't an option) the takeaway was “look up the implementation of a better algorithm if you are sorting nontrivial data”. (Plus, “its worth thinking about how much work your code is going to take to do what it needs to do”, as it was also my first introduction to algorithmic complexity.) I'm trying to grasp the pedagogical failure that would result in people taking the lesson “implementing bubble sort is a reasonable thing to ever do for non-toy problems”.

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.

smcl 6y ago

I wonder how many people actually write a sort algorithm in production code anymore. I haven't personally seen this, but I guess that doesn't really mean it doesn't exist. What I have seen is pretty horrific abuse of Linq (i.e. repeated lookup of `things.Where(t => t.Id == query.Id).First()` as if it was a dictionary) which might stem from the same root cause - not thinking about what your code is actually doing and why it might be inefficient. It doesn't help that there's that there's those oft-quoted Bentley's Rules of Optimization which gives people an excuse to not care :-/

dragonwriter 6y ago

Huh, like when I learned this (back when I was in elementary school and the class was taught using unstructured BASIC, so the more natural lesson with most things more modern of “rely on your standard library for sorting, unless you have a really good cause to roll your own and then do some research” wasn't an option) the takeaway was “look up the implementation of a better algorithm if you are sorting nontrivial data”. (Plus, “its worth thinking about how much work your code is going to take to do what it needs to do”, as it was also my first introduction to algorithmic complexity.) I'm trying to grasp the pedagogical failure that would result in people taking the lesson “implementing bubble sort is a reasonable thing to ever do for non-toy problems”.