Сортировка выбором

Сортировка выбором на каждом проходе ищет минимальный элемент в неотсортированной части и меняет его местами с первым неотсортированным. Число обменов мало — не более n−1.

Сложность: время O(n^2) всегда, независимо от исходного порядка. Память: O(1). В классическом виде неустойчива.

def selection_sort(a):
    n = len(a)
    for i in range(n):
        m = i
        for j in range(i + 1, n):
            if a[j] < a[m]:
                m = j
        a[i], a[m] = a[m], a[i]
    return a