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

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

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

Алгоритм

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

Двухсторонняя сортировка выбором

Скорость алгоритма можно увеличить в 2 раза если кроме максимального элемента в неотсортированном подмассиве также находить и минимальный. Максимум при этом перемещать в конец подмассива, а минимум — в начало.

Двусторонняя сортировка выбором

Аналогичное улучшение для сортировки пузырьком называется коктейльной сортировкой.

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

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

Ссылки

Сортировка выбором в Википедии
Selection sort on Wikipedia
Реализация на различных ЯП

Добавить комментарий