Сортировка выбором :: Selection sort
Базовый алгоритм для сортировок выбором. Работает медленно, но некоторые её модификации (например, пирамидальная сортировка) могут показывать очень высокую эффективность.
Алгоритм
Проходим массив и находим в нём максимальный элемент. Найденый максимум меняем местами с последним элементом. Затем проходим по неотсортированной части массива (от первого элемента до предпоследнего) и находим в ней максимум, который затем меняем местами с предпоследним элементом масива. Продолжаем действия, пока не отсортируем полностью.
Если кроме максимумов конец массива таке перемещать минимальные элементы его начао, то мы пучаем двухстороннюю сортировку выбором.
Характеристики алгоритма
| Название | Сортировка выбором (Selection sort) | |
|---|---|---|
| Другие названия | Сортировка выделением | |
| Класс | Сортировки выбором | |
| Устойчивость | Нет | |
| Сравнения | Да | |
| Сложность по времени | Худшая | O(n2 / 2) |
| Средняя | O(n2 / 2) | |
| Лучшая | O(n2 / 2) | |
| Сложность по памяти | Общая | O(n) |
| Дополнительная | O(1) | |
Сортировка выбором
Реализация на различных ЯП