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

Сортировка выбором улучшает пузырьковую сортировку, совершая всего один обмен за каждый проход по списку. Чтобы сделать это, она ищет наибольший элемент и помещает его на соответствующую позицию. Как и для пузырьковой сортировки, после первого прохода самый большой элемент находится на правильном месте. После второго - на своё место становится следующий наибольший элемент. Процесс продолжается, требуя \(n-1\) проход для сортировки \(n\) элементов, поскольку последний из них автоматически оказывается на своём месте.

Рисунок 3 демонстрирует сортировочный процесс целиком. На каждом проходе выбирается наибольший из несортированных элементов и помещается на соответствующюю позицию. Первый проход разместит 93, второй - 77, третий - 55 и так далее. Функция показана в ActiveCode 3.

Рисунок 3: selectionSort

def selectionSort(alist):
   for fillslot in range(len(alist)-1,0,-1):
       positionOfMax=0
       for location in range(1,fillslot+1):
           if alist[location]>alist[positionOfMax]:
               positionOfMax = location

       temp = alist[fillslot]
       alist[fillslot] = alist[positionOfMax]
       alist[positionOfMax] = temp

alist = [54,26,93,17,77,31,44,55,20]
selectionSort(alist)
print(alist)

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

Для большей детализации CodeLens 3 позволит вам пройти весь алгоритм пошагово.

Трассировка сортировки выбором (selectionsortcodetrace)

Вы можете видеть, что сортировка выбором совершает то же число сравнений, что и пузырьковая сортировка, поэтому является \(O(n^{2})\). Однако, из-за уменьшения количества перестановок, на тестовых заданиях она обычно выполняется быстрее. Фактически, для нашего списка пузырьковая сортировка сделает 20 перестановок, в то время как сортировка выбором - всего 8.

Самопроверка

Q-61: Предположим, у вас есть следующий список для сортировки: [11, 7, 12, 14, 19, 1, 6, 18, 8, 20]. Который из представленных вариантов является частично отсортированным списком после трёх проходов сортировки выбором?

Next Section - Сортировка вставками