What 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.
But 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.
> 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.
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.