Сортировка выбором
Сортировка выбором (англ. selection sort) — простой алгоритм сортировки со сложностью O(n2), где n — количество элементов для сортировки.
Сортировка обменом – это еще один вид простого, но неэффективного алгоритма сортировки.
Идея алгоритма достаточна проста
Проходим по массиву в поисках минимального элемента. Найденный минимум меняем местами с первым элементом. Неотсортированная часть массива уменьшилась на один элемент (не включает первый элемент, куда мы переставили найденный минимум). К этой неотсортированной части применяем те же действия — находим минимум и ставим его на первое место в неотсортированной части массива. И так продолжаем до тех пор, пока неотсортированная часть массива не уменьшится до одного элемента.
Алгоритмическая реализация данного алгоритма
ЦИКЛ ДЛЯ I=0 ДО N-2 ШАГ 1
МИН = I
ЦИКЛ ДЛЯ J=I+1 ДО N-1 ШАГ 1
ЕСЛИ a[J] < a[МИН],
ТО МИН = J
СЛЕДУЮЩЕЕ J
ПОМЕНЯТЬ МЕСТАМИ (a[I], a[МИН])
СЛЕДУЮЩЕЕ I
Вычислительная сложность:
\(\displaystyle O(n^{2})\).