4 ms·

Terminating 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 believ

Terminating 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 = true

minitech 10mo ago
> 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.
- 3eb7988a1663 10mo ago
  I recall "inventing" bubble sort during one of my first CS classes when the question was posed of how to sort a list. So, not that outlandish.
  - avmich 10mo ago
    Agree. I remember the names of many of these algorithms, but not the logic.
jeltz 10mo ago
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
bxparks 10mo ago
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.

minitech 10mo ago

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

3eb7988a1663 10mo ago
I recall "inventing" bubble sort during one of my first CS classes when the question was posed of how to sort a list. So, not that outlandish.
- avmich 10mo ago
  Agree. I remember the names of many of these algorithms, but not the logic.

jeltz 10mo ago

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

bxparks 10mo ago

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.