I haven't investigated selection sort. You have me curious though. Is that a step down from bubble sort? If so, maybe it's just as well I figured out bubble.
Selection sort is arguably the easiest sort, and arguably the easiest to see that it is correct. Given an array a with n elements A[0], A[1], ..., A[n-1], let the notation A[x:y] mean the set {A[x], A[x+1], ..., A[y]}.
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]
I think that selection sort is easy to understand and easier to see that it is correct because it can be separated into a two array version. Given input array A and an empty array B, do this:
while A is not empty
find a smallest element of A
append that to B
The in place version earlier is essentially that, just storing B and A together in one array.
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
In bookshelf form
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:
