Сортировка выбором
Сортировка выбором — алгоритм сортировки, относящийся к неустойчивым алгоритмам сортировки. На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае Θ(n2), предполагая что сравнения делаются за постоянное время.
Алгоритм
Шаги алгоритма:
- находим минимальное значение в текущем списке
- производим обмен этого значения со значением на первой неотсортированной позиции
- теперь сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы
Пример сортировки выбором
Реализация сортировки с помощью двоичного дерева на С++
05 | void selection_sort( Iterator first, Iterator last ) |
07 | while( first < --last ) |
08 | std::iter_swap( last, std::max_element( first, last + 1 ) ); |
Вывод по сортировке выбором
Пирамидальная сортировка сильно улучшает базовый алгоритм, используя структуру данных «куча» для ускорения нахождения и удаления минимального элемента.
Существует также двунаправленный вариант сортировки методом выбора, в котором на каждом проходе отыскиваются и устанавливаются на свои места и минимальное, и максимальное значения.