Шаги алгоритма:
1.
находим номер минимального значения в текущем списке
2.
производим обмен этого значения со значением первой
неотсортированной позиции (обмен не нужен, если минимальный элемент уже
находится на данной позиции)
3.
теперь сортируем хвост списка, исключив из рассмотрения уже
отсортированные элементы
Для
реализации устойчивости алгоритма необходимо в пункте 2 минимальный элемент
непосредственно вставлять в первую неотсортированную позицию, не меняя порядок
остальных элементов.
Сказанное можно
записать следующим образом в псевдокоде:
Нц для j от 1 до N-1
выбрать среди M[j],. . ., M[N] наименьший элемент и
поменять его местами с M[j]
кц
выбрать среди M[j],. . ., M[N] наименьший элемент и
поменять его местами с M[j]
кц
Так
как после каждого прохода по внутреннему циклу делается только один обмен, то
общее число обменов равно N-1, что в N/2 раз меньше, чем в сортировке
пузырьком.
Число проходов по внутреннему циклу равно N-1 даже в случае сортировки частично или полностью отсортированного массива.
Наихудший случай:
Число сравнений в теле цикла равно (N-1)*N/2.
Число сравнений в заголовках циклов (N-1)*N/2.
Число сравнений перед операцией обмена N-1.
Суммарное число сравнений N2−1.
Число обменов N-1.
Анализ сложности – Королев-Миков
страницы 122!!!Число проходов по внутреннему циклу равно N-1 даже в случае сортировки частично или полностью отсортированного массива.
Наихудший случай:
Число сравнений в теле цикла равно (N-1)*N/2.
Число сравнений в заголовках циклов (N-1)*N/2.
Число сравнений перед операцией обмена N-1.
Суммарное число сравнений N2−1.
Число обменов N-1.
