Selection Sort

Selection sort is quite simple, but because is simple is then easy to understand. It’s complexity is O(n²) so it’s not very suitable for production quality code and there are (obviously) other faster sorting algorithms, but it’s good to get a grip of it and treat it as an introduction to sorting algorithms.

Basically this algorithm is performing what is says on the tin, it selects items and sorts them. That’s all!

So what you want is, to pick up whether you want to start with the smallest or the largest value in the array and carry on from this point.

Let’s say we want to start with the smallest item in an array and sort it in ascending order.

Pseudo code for selection sort algorithm starting with the smallest value:

sorted_array = []
for each_item in array
    min = select_minimal_value(array)
    add min to sorted_array
return sorted_array

And possible implementation in python:

def find_min_index(arr):
    min_index = 0
    for index in range(len(arr)):
        if arr[index] < arr[min_index]:
            min_index = index

    return min_index

def selection_sort(arr):
    sorted_array = []
    while arr:
        min_index = find_min_index(arr)
        sorted_array.append(arr[min_index])
        arr.pop(min_index)

    return sorted_array

Try it out, check how it works with different inputs. Try reimplement it from memory, apply into your own applications and check its performance. Later when we go over other algorithms you will be able to compare their performances.