The appeal of bubble sort for me is that is it the only one I understand well enough to implement myself without having to think much about it.
Bubble sort doesn't click for me easily. I think it's because the terminating condition seems uglier than Selection sort or Insertion sort. I always have a little voice in the back of my mind, "Is this outer loop guaranteed to terminate?"
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 = trueWell, 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.
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 - 1Selection 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.
For the curious, the ZX Spectrum microdrive listed files on the cartridges by order found on tape. I wanted to display it in alphabetical order like the "big" computers did.
It is your choice which career to pursue, but in my experience, absolute majority of programmers don't know algorithms and data structures outside of very shallow understanding required to pass some popular interview questions. May be you've put too high artificial barriers, which weren't necessary.
To be a professional software developer, you need to write code to solve real life tasks. These tasks mostly super-primitive in terms of algorithms. You just glue together libraries and write so-called "business-logic" in terms of incomprehensible tree of if-s which nobody truly understands. People love it and pay money for it.
Should I be familiar with every step of Dijkstra’s search algorithm and remember the pseudocode at all times? Why don’t the textbooks explain why the algorithm is correct?
The good ones do!
> Should I be familiar with every step of Dijkstra’s search algorithm and remember the pseudocode at all times?
If it’s the kind of thing you care to be familiar with, then being able to rederive every step of the usual-suspect algorithms is well within reach, yes. You don’t need to remember things in terms of pseudocode as such, more just broad concepts.
Somehow, I think you already know the answer to that is "no".
I've been working as a software engineer for over 8 years, with no computer science education. I don't know what Dijkstra's search algorithm is, let alone have memorised the pseudocode. I flicked through a book of data structures and algorithms once, but that was after I got my first software job. Unless you're only aiming for Google etc, you don't really need any of this.
I used to think alike (I'm +30 year programing) until I decide to do https://tablam.org, and making a "database" is the kind of project where all this stuff suddenly is practical and worthwhile.
for i = 0 to n-1
find an index j in A of the smallest member of A[i:n-1]
swap A[i] with A[j]
while A is not empty
find a smallest element of A
append that to B
That is something most non-programmers could easily come up with for physical sorting. For instance you have a row of books on a shelf that are in random order, and you want to move them to another shelf and have them sorted by author's last name.
1. Scan the first row to find the book that should come before all the rest on that row.
2. Move it to the end of the books on the second row.
3. Repeat until all the books have been moved.
Selection sort is in a sense just a computer implementation of a procedure that ordinary people have a good chance of coming up with when they need to sort physical items.
Selection sort performs better than bubble sort on random data. They are both O(n^2) but selection sort will perform fewer writes.
If you deal with data that is mostly already sorted though then bubble sort with early stopping is O(n) and wins.
With bubble sort I can't think of a two array version that makes it easier to understand. I also don't think many ordinary people would come up with bubble sort when sorting say their bookshelf.
There's also insertion sort. The two array version would be
while A is not empty
take the first element of A
insert that into B keeping B sorted
1. Pick a book from the first row.
2. Find where that belongs in alphabetical order in the second row and put it there.
3. Repeat until you run out of books on the first row.
I think this is what most ordinary people who don't come up with selection sort would come up with.
The two array form can be converted to in place the same as selection sort.
Insertion sort is, like the others O(n^2). Like selection sort it is faster than bubble sort on random data. Unlike selection sort whose runtime is about the same no matter how the data is ordered, it is fast on almost sorted data.
Here's all three (bubble, selection, insertion) illustrated by folk dancers:
https://www.youtube.com/watch?v=Iv3vgjM8Pv4