Сортировка выбором
На каждом шаге находим минимальный элемент среди неотсортированных и ставим его на своё место.
Идея алгоритма
- Ищем минимальный элемент во всём массиве, ставим на первое место
- Ищем минимальный среди оставшихся, ставим на второе место
- Повторяем, пока массив не отсортирован
Разбор
Внешний цикл
нц для i от 0 до n - 2
min_i := i
...
кц
Переменная i — позиция, куда мы поставим очередной минимум. Начинаем с предположения, что минимум находится в позиции i.
Поиск минимума
нц для j от i + 1 до n - 1
если A[j] < A[min_i] то
min_i := j
все
кц
Проходим все элементы правее i. Если нашли элемент меньше текущего минимума — запоминаем его индекс в min_i.
Обмен
если min_i <> i то
tmp := A[i]
A[i] := A[min_i]
A[min_i] := tmp
все
Если минимум не на позиции i — меняем их местами.
Сложность: $O(n^2)$. Делает минимум обменов (не более $n - 1$), но всегда выполняет $O(n^2)$ сравнений.
Полная программа
алг main(цел n)
нач
если n <= 0 то
вывод "Размер массива должен быть положительным", нс
выход
все
цел таб A[0:n-1]
заполнить_случайными(n, A)
вывод "Исходный массив:", нс
печать_массива(n, A)
selectionsort(n, A)
вывод "Отсортированный массив:", нс
печать_массива(n, A)
кон
алг selectionsort(цел n, цел таб A[0:n-1])
нач
цел i, j, min_i, tmp
нц для i от 0 до n - 2
min_i := i
нц для j от i + 1 до n - 1
если A[j] < A[min_i] то
min_i := j
все
кц
если min_i <> i то
tmp := A[i]
A[i] := A[min_i]
A[min_i] := tmp
все
кц
кон
алг заполнить_случайными(цел n, цел таб A[0:n-1])
нач
цел i
нц для i от 0 до n - 1
A[i] := irnd(100)
кц
кон
алг печать_массива(цел n, цел таб A[0:n-1])
нач
цел i
нц для i от 0 до n - 1
вывод A[i], " "
кц
вывод нс
кон