Сортировка выбором (Selection sort)

Во время сортировки выбором массив делится на две части: отсортированную и неотсортированную. Отсортированная часть, во время первой итерации алгоритма, состоит из нуля элементов, а неотсортированная составляет весь массив. С каждой итераций отсортированная часть увеличивается на один элемент, а неотсортированная уменьшается.

Во время каждой итерации алгоритм ищет максимальный или минимальный элемент в неотсортированной части массива, а затем добавляет его к отсортированной части. Точнее говоря, ближайший к отсортированной части массива элемент, заменяется на подходящий из остальной части массива.

Псевдокод

алгоритм сортировка_выбором(массив)
начало
  для каждого индекса в массиве
    находим минимальным элемент с индексом большим или равным текущему
    меняем местами элемент с текущим индексом и найденный элемент
конец

Поиск минимального элемента по сути является алгоритмом линейного поиска.

Реализация на Python

Перемещение элементов из неотсортированной части в отсортированную производится с помощью цикла. Цикл должен пройти от первого до предпоследнего элемента. Последний элемент проверять не требуется, так как после сортировки остальных элементов он уже окажется на своем месте.

def selection_sort(lst):
    for i in range(0, len(lst) - 1):

Таким образом сразу решается проблема с граничными случаями: когда массив пустой или из одного элемента цикл выполнятся не будет.

На каждой итерации внешнего цикла нужно найти минимальный или максимальный элемент в остальной части массива — применить алгоритм линейного поиска, следовательно понадобится либо вызов функции либо просто второй цикл.

def selection_sort(lst):
    for i in range(0, len(lst) - 1):
        for j in range(i + 1, len(lst)):
            if lst[j] < lst[i]:
                lst[i], lst[j] = lst[j], lst[i]
    return lst

Требования

Для эффективного применения сортировки выбором требуется коллекция с произвольным доступом.

Анализ сложности

Сложность сортировки выбором равна $\mathcal{O}(n^2)$. Сортировка выбором содержит типичную конструкцию для такой сложности — вложенные циклы. Внешний цикл выполняется $n-1$ раз. Количество выполнений внутреннего цикла постепенно уменьшается от $n$ до $1$, что в среднем даёт $0.5n$. Таким образом количество операций равно

$$(n-1)\ast 0.5n=0.5n^2-0.5n$$

что сокращается до $\mathcal{O}(n^2)$.

Сортировка выбором не требует дополнительной памяти при увеличении входного массива, поэтому сложность по памяти равна $\mathcal{O}(1)$.

Ссылки

• Грокаем алгоритмы. Адитья Бхаргава. Питер. 2018. Глава 2. Сортировка выбором. Сортировка выбором

Ссылки на эту заметку

Эта заметка на GitHub

Обсудить на форуме