Сортировка выбором :: Selection sort

Базовый алгоритм для сортировок выбором. Работает медленно, но некоторые её модификации (например, пирамидальная сортировка) могут показывать очень высокую эффективность.

Алгоритм

Проходим массив и находим в нём максимальный элемент. Найденый максимум меняем местами с последним элементом. Затем проходим по неотсортированной части массива (от первого элемента до предпоследнего) и находим в ней максимум, который затем меняем местами с предпоследним элементом масива. Продолжаем действия, пока не отсортируем полностью.

Если кроме максимумов конец массива таке перемещать минимальные элементы его начао, то мы пучаем двухстороннюю сортировку выбором.

Характеристики алгоритма

НазваниеСортировка выбором (Selection sort)
Другие названияСортировка выделением
КлассСортировки выбором
УстойчивостьНет
СравненияДа
Сложность по времениХудшаяO(n2 / 2)
СредняяO(n2 / 2)
ЛучшаяO(n2 / 2)
Сложность по памятиОбщаяO(n)
ДополнительнаяO(1)

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

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

Ссылки

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

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

Selection sort

Реализация на различных ЯП