4 ms·
It sounds like you essentially invented the spreadsheet. Nice work! > Part of the calculation involved sorting. I didn't know anything about sorting, so I impl
by kqr 6y ago
It sounds like you essentially invented the spreadsheet. Nice work!
> Part of the calculation involved sorting. I didn't know anything about sorting, so I implemented what I later learned was bubble sort. Because that's obviously how you'd do that.
I would like to politely contest the authenticity of this specific detail. In my fairly strong collection of evidence, people just do not bubble sort without being told how to do that.
People's natural mental sorting algorithm is most often insertion sort. That's what you use when you hold a hand of playing cards, for example. Sometimes something else (radix sort with monopoly money, for example), but I've never seen anyone invent bubble sort without first being told about it one way or another.
(Which is a good thing because bubble sort is just such a stupid idea I don't know why we teach it. In my life, I've only ever been notified of one single good use case for it: you need to slowly converge on an order but the minimum amount of computation is necessary for each step of the convergence.)
- jacobolus 6y agohttps://blog.reverberate.org/2020/05/29/hoares-rebuttal-bubble-sorts-comeback.html https://blog.reverberate.org/2020/05/29/hoares-rebuttal-bubb...
- kqr 6y agoI did not expect that, but sure enough, makes sense when I look at it. Thanks!
- gsliepen 6y ago> I would like to politely contest the authenticity of this specific detail. In my fairly strong collection of evidence, people just do not bubble sort without being told how to do that. I taught a C programming class for first-year students for a few years at the end of the 90s, where one of the tasks was to sort an array of words, with no hints given as to what kind of algorithm they should implement. Most students came up with bubble sort. Insertion sort was much less prevalent, and the few students who did typically did a kind of out-of-place insertion sort. (I also saw a O(N^4) algorithm once.)
- BlueTemplar 6y agoI "trolled" the professor by doing a random sort...
- tragomaskhalos 6y agoA better troll would have been Sleep Sort :)
- eru 6y ago> People's natural mental sorting algorithm is most often insertion sort. That's what you use when you hold a hand of playing cards, [...] I agree about the playing cards. But bubble sort was the natural sorting algorithm for me to come up with, too, when I was dealing with qbasic back in the 1990s.
- louisvgchi 6y agoBubble sort was perfectly natural to me before I learned about algorithms. I think your “fairly strong collection of evidence” is weak. We teach it because it’s a study in how not to sort, most of the time.
- a3n 6y ago> I would like to politely contest the authenticity of this specific detail. > People's natural mental sorting algorithm is most often insertion sort. [embarrassed panic] [trip down wikipedia lane] No, it was bubble sort. Data and loop management for insertion sort wouldn't have been something I would have thought of back then.
- kqr 6y agoWhat confuses me is that isn't the data and loop management for bubble sort even more complicated? Insertion sort is literally just "keep track of the index beyond the last sorted element, then scan for the next smallest element and swap it in, repeat until you have gone through the entire array." This is about as simple as a comparison sort gets. (And it's what literally everyone I've watched does when they get dealt a few playing cards.) Bubble sort, on the other hand, requires you to reason about consecutive adjacent swaps, keep track of whether the current iteration dirtied the array, and so on. (Just the idea of bubble sorting playing cards gets me sweaty. It would take long, be cumbersome, and hard to keep track of.) Edit: who is embarrassed now? What I'm describing is apparently not insertion sort but selection sort.
- a3n 6y agoBut you're speaking from knowledge and analysis. I only had the perspective at the time of looking at the world through a paper towel roll. Anyway, it was the first idea that bubbled up for me.
- tzs 6y ago> Bubble sort, on the other hand, requires you to reason about consecutive adjacent swaps, keep track of whether the current iteration dirtied the array, and so on. You only need to keep track of whether or not the current iteration dirtied the array if you want to stop as soon as a pass leaves the array sorted. If you don't want to do that (or don't think of it) then it is just something like: for pass = 1 to n for index = 1 to n-1 if array[index-1] > array[index] tmp = array[index] array[index-1] = array[index] array[index] = tmp There is less extra to keep track of then in insertion or selection sort.
- someguyorother 6y ago> I would like to politely contest the authenticity of this specific detail. In my fairly strong collection of evidence, people just do not bubble sort without being told how to do that. FWIW, my first sort was selection sort. "Find the smallest element, place it at the start, repeat" seems like the obvious way to do it, without the fussing about with shuffling already sorted elements out of the way that insertion sort requires. Perhaps it's a thinking top-down vs bottom-up kind of thing? People who think bottom-up stumble on bubble sort, people who think top-down stumble on selection or insertion.
- kqr 6y agoI just now realised that when I talked about insertion sort I really meant selection sort. How embarrassing of me to lecture others and then go on to make such a basic mistake myself!
- DonHopkins 6y agoBubble sort is just fine if you're sure you'll only have a few items, or if it's likely that it might already be sorted, but it's still embarrassing admitting implementing it. Even Barack Obama knows that! https://en.wikipedia.org/wiki/Bubble_sort#Performance https://en.wikipedia.org/wiki/Bubble_sort#Performance >The only significant advantage that bubble sort has over most other algorithms, even quicksort, but not insertion sort, is that the ability to detect that the list is sorted efficiently is built into the algorithm. When the list is already sorted (best-case), the complexity of bubble sort is only O(n). By contrast, most other algorithms, even those with better average-case complexity, perform their entire sorting process on the set and thus are more complex. However, not only does insertion sort share this advantage, but it also performs better on a list that is substantially sorted (having a small number of inversions). Additionally, if this behavior is desired, it can be trivially added to any other algorithm by checking the list before the algorithm runs. >In popular culture: In 2007, former Google CEO Eric Schmidt asked then-presidential candidate Barack Obama during an interview about the best way to sort one million integers; Obama paused for a moment and replied "I think the bubble sort would be the wrong way to go." Here's an implementation of bubble sort written in PostScript by Sam Leffler, renowned BSD/Lucasfilm/Pixar/SGI/Alias/Softimage/VMWare hacker, which he sent me and gave me permission to distribute in 1988, but which he was too embarrassed to sign his own name to, so he used the pseudonym "Bobo Leffler". https://donhopkins.com/home/archive/psiber/cyber/bubblesort.ps https://donhopkins.com/home/archive/psiber/cyber/bubblesort.... https://en.wikipedia.org/wiki/Samuel_J._Leffler https://en.wikipedia.org/wiki/Samuel_J._Leffler Also here's a PostScript heap sort by Owen Densmore of Sun, and a PostScript insertion sort by John Warnock of Adobe, both of whom used their real names: https://donhopkins.com/home/archive/psiber/cyber/heapsort.ps https://donhopkins.com/home/archive/psiber/cyber/heapsort.ps https://donhopkins.com/home/archive/psiber/cyber/insertion-sort.ps https://donhopkins.com/home/archive/psiber/cyber/insertion-s...
- kqr 6y agoWhat is so revealing about that Obama quote, the way I see it, is how dangerous it can be to "teach what not to do". There's a significant risk the student ends up just remembering the wrong way and none of the right ways.