Re:Bubblesort, rocksort, and cocktail-shaker sort
by ernesth on Wednesday December 16, 2020 @10:03AM
(#25443353)
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.
Re:Bubblesort, rocksort, and cocktail-shaker sort
by virgilp on Wednesday December 16, 2020 @07:49AM
(#25441900)
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 ).
Re:Bubblesort, rocksort, and cocktail-shaker sort
by bonoboTP on Wednesday December 16, 2020 @09:21AM
(#25442754)
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.
Re:Bubblesort, rocksort, and cocktail-shaker sort
by quietbritishjim on Wednesday December 16, 2020 @06:50AM
(#25441514)
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
I think the whole "swap neighbors and scan many times" thing isn't something a novice would come up with.