alt Hacker NewsTerminating condition in Bubble sort is "did we swap any values during this loop"? Yes -> continue, No -> list is already sorted, exit the loop.
I don't believe that insertion/selection sort is easier to grasp. Can you type it from memory, without looking it up? Here's bubble sort:
var swapped = true
while swapped:
swapped = false
for i in 0 .. list.len-2:
if list[i] > list[i+1]:
swap(list[i], list[i+1])
swapped = trueReplies
> Can you type it from memory, without looking it up?
Well, yeah, but that’s not a very useful heuristic for people who are already aware of the algorithms in question. If you ask people to come up with a way from scratch – probably without explicitly asking, in order to get better success, like by watching how they sort cards – I bet they won’t tend to come up with bubble sort. Maybe that says something about the relative intuitiveness of the approaches? Or not.
Let's see.
for i in 1 .. list.len - 1:
j = i - 1
while j >= 0 and list[j] > list[j + 1]:
swap(list[j], list[j + 1])
j = j - 1
Different strokes for different folks I guess.
Selection sort was the first sorting algorithm that I ever created: Find the smallest element for slot #1. Find the next smallest for slot #2. And so on. I've recreated it from scratch many times. The double for-loop means that it is guaranteed to finish, and it is obviously O(N^2).
I did not learn about Bubble sort until my university class, where I thought, this is a terrible algorithm: It's not completely obvious that it will finish, and it's not obvious what the runtime complexity is. For example, if the inner loop used ">=" instead of ">", it would work for test data sets with unique elements, then hang forever with a real data set that contained duplicates.