Сортировка выбором (Selection Sort) — это один из базовых алгоритмов сортировки, который последовательно находит минимальный (или максимальный) элемент в неотсортированной части массива и перемещает его в начало. Этот метод не требует дополнительной памяти (работает in-place) и легко реализуется, но имеет квадратичную сложность O(n²), что делает его неэффективным для больших данных.

Ключевые особенности

Простота реализации — алгоритм легко понять и написать даже новичкам.
Минимум перестановок — всегда делает O(n) перестановок, что полезно, если перемещение элементов дорого (например, при работе с файлами).
Медленный на больших данных — из-за сложности O(n²).
Нестабильный — может менять порядок одинаковых элементов.

 

def choice_sort(list_):
    for i in range(len(list_)):
        min_ind = i
        for c in range(i+1,len(list_)):
            if list_[c]<list_[i]:
                min_ind = c
            list_[i], list_[min_ind] = list_[min_ind],list_[i]
    return  list_
list_ = [1,4,2,9,1]
print(choice_sort(list_))

Как работает сортировка выбором?

  1. Разделение массива:

    • Левая часть — отсортированная (изначально пустая).

    • Правая часть — неотсортированная (весь массив).

  2. Поиск минимума:

    • В неотсортированной части находится минимальный элемент.

  3. Обмен:

    • Минимальный элемент меняется местами с первым элементом неотсортированной части.

  4. Рекурсивное повторение:

    • Граница отсортированной части сдвигается вправо.

    • Процесс повторяется, пока весь массив не будет отсортирован.