Selection Sort

Selection sort is an in-place comparison sorting algorithm with a time complexity of n².

1. Iterate over the whole list.
   | for i in range(len(a))
2. Keep track of the smallest value, which is i initially.
   | min = i
3. Iterate over the remaining values to the right.
   | for j in range(i + 1, len(a))
4. If this value is smaller than the smallest, replace it.
   | if (util.less(a[j], a[min])): m = j
5. After checking all values to the right, replace i with the smallest value (min).
   | util.exchange(a, i, min)

for i in range(len(a)):
    min = i;
    for j in range(i + 1, len(a)):
        if (util.less(a[j], a[min])):
            min = j;
    util.exchange(a, i, min);

The algorithm divides the list in two parts. A list of already sorted values (left) and a list of values to be sorted (right). With other words, left of i the values are sorted, right of it they are not. i is the index of the list it is currently sorting.