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.)
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.
> 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.
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.
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
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.
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....
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/insertion-s...
Do NOT click on the red button.
> 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.)