Selection Sort

This is the continuation of the last article on bubble sort. If you didn’t read it you can read it clicking here.

Another algorithm that is usually better than bubble sort is called selection sort.

The idea is also very simple. You conceptually separate the list in two parts, the sorted one and the unsorted one. You find the minimum element of the unsorted part and put it in the sorted part and you do that until everything is sorted.

Example: [5, 4, 3, 2, 1]
We have a sorted empty list [] and unsorted [5, 4, 3, 2, 1].
The minimum element is 1, so we put it in the sorted part
[1] + [5, 4, 3, 2]
We do the same again and we get [1, 2] + [5, 4, 3].
And we repeat until the unsorted part is empty.

In code this is also very simple and since it’s in general faster than bubble sort, you should not use bubble sort anymore.

fun <T : Comparable<T>> DynamicArray<out T>.selectionSort() {
    val n = size()
    for (i in 0 until n) {
        var min = i
        var j = i
        while (j < n) {
            if (this[j] < this[min]) {
                min = j
            }
            j++
        }
        swap(this, i, min)
    }
}

On my machine this took around 25min, which is a bit slower than the previous bubble sort but that’s not usually the case. You can still forbid yourself from using it almost anywhere.

Why so slow?

The reason why both bubble sort and selection sort are so slow will be the topic for a future article. They would not be that slow if the number of elements would not be so big. They would both behave quite acceptably for arrays with around 50 elements but since we’re dealing with more than 300,000, the performance drops quite fast.

From these algorithms where the performance drops quite fast under the average scenario, there is another one that you should know about and it should be always your choice for small arrays.

This algorithm is called insertion sort and it outperforms the previous two in the average scenario. Click here if you want to read about it in the next article.