← Все примеры

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

На каждом шаге находим минимальный элемент среди неотсортированных и ставим его на своё место.

Идея алгоритма

1. Ищем минимальный элемент во всём массиве, ставим на первое место
2. Ищем минимальный среди оставшихся, ставим на второе место
3. Повторяем, пока массив не отсортирован

Разбор

Внешний цикл

нц для 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], " "
    кц
    вывод нс
кон

▶ Запустить пример