Сортировка выбором — это алгоритм, который позволяет упорядочить элементы в списке и который может быть или устойчивым, или неустойчивым.
Введение
Информационные объёмы, которые включают в себя действующие сегодня базы данных, могут достигать огромных размеров, вплоть до десятков миллионов единиц. При обработке таких баз самой главной характеристикой выступает скорость отклика, то есть интервал времени от момента постановки задачи поиска информации, до момента осуществления решения этой проблемы.
Работа с информационными данными будет осуществляться гораздо более оперативно, если массив данных отсортирован.
Сортировка представляет собой операцию последовательного расположения набора однотипных данных в определённом порядке согласно заданным правилам.
Одним из основных параметров алгоритмов сортировки считаются скорость работы и оптимальность использования ресурсов памяти. Скорость работы или быстродействие сортировки задаётся числом операций сравнения и числом операций перестановки компонентов (обменов), которые производятся при выполнении алгоритма сортировки.
Обычно, эффективность сортировочных алгоритмов определяется по уровню роста числа процедур сравнения. Сравнительно маленькие массивы данных возможно полностью разместить в оперативной памяти. Это также обеспечивает возможность произвольного доступа к компонентам сортировки. В таких случаях сортировка считается внутренней. Но если размер массива данных очень большой и оперативной памяти уже недостаточно, то приходится использовать внешние носители для запоминания данных. Тогда доступ к информационным компонентам выполняется последовательно и сортировка уже будет внешней. Эти типы сортировки используют тогда, когда исходная информация находится на этих носителях. Естественно, что при внутренней сортировке быстродействие будет выше, чем при внешней, для одного и того же массива, поскольку внешняя сортировка тратит львиную долю времени на последовательный доступ к информационным компонентам.
Виды сортировок
Сортировать возможно данные различных типов: числовые, текстовые (строковые), записи в файлах. Сортировка числовой информации заключается в следующем. Задан числовой массив A1, A2, …An. Возможные типы сортировки определяются условием наличия в массиве одинаковых по значению компонентов:
- Сортировка по не убыванию. В этом случае все последующие компоненты должны быть больше (не меньше) предыдущих: Ax > A2 >…> An.
- Сортировка по не возрастанию. В этом случае все последующие компоненты должны быть не больше предыдущих: Ax > A2 > … > An.
При сортировке текстовой информации, как правило требуется расположить фрагменты текста в алфавитном порядке. Идея текстовой сортировки следующая. Изначально делается операция сортировки по начальному символу текста. Далее все полученные подмножества компонентов, которые имеют одинаковые начальные символы, проходят сортировку по следующему символу и так далее. При сортировке в алфавитном порядке возможны различные методы выбора порядка символов:
- Задание порядка вручную.
- Порядок символов соответствует порядку их кодов. При этом для информационных строк, которые начинаются с цифр, есть вероятность получения неожиданных итогов сортировки, типа «4» > «20». Для ликвидации таких возможностей используют специальные алгоритмы.
Выполнение сортировки записей в файлах осуществляется по ключам записей. Ключи могут быть разных типов, то есть числовые, текстовые или включать в себя поля с разными видами информации. Записи могут сортироваться по величине ключа, то есть возрастание или убывание.
Итак, сортировкой данных является один из шагов по работе с данными, упорядочивание информационных данных в порядке, который определяется ключами сортировки. Чаще всего, это выстраивание компонентов массива в порядке возрастания или убывания величин компонентов, которые входят в состав массива.
Сортировка выбором
Алгоритм сортировки выбором можно представить следующим образом:
- В части массива, которая не отсортирована, необходимо найти локальный минимум или максимум (зависит от поставленной задачи).
- Выполняется обмен месторасположением обнаруженного компонента с минимальным (максимальным) значением, с первым(последним) компонентом этой части массива.
- Если после выполнения второго пункта ещё есть не отсортированные подмассивы, то снова выполняется первый шаг.
Рассмотрим конкретный пример. Есть числовой массив:
Рисунок 1. Числовой массив. Автор24 — интернет-биржа студенческих работ
Согласно приведённому выше алгоритму, выполняется проход по компонентам массива с целью найти максимум. Обнаруженный максимальный компонент меняется местами с последним. Часть массива, которая ещё не отсортирована, соответственно стала меньше на единицу. Далее действие повторяется с неотсортированным участком массива, то есть определяется максимум и устанавливается на последнее место в той части массива, которая ещё не отсортирована. Процедура повторяется до тех пор, пока неотсортированным останется только один компонент. Программная реализация выглядит так:
Рисунок 2. Программная реализация. Автор24 — интернет-биржа студенческих работ
По сути сортировка выбором является обычным двойным перебором. Но этот алгоритм возможно улучшить. Например, использовать двухстороннюю сортировку выбором. Подобная мысль применяется в шейкерной сортировке, являющейся одной из версий пузырьковой сортировки. При обходе участка массива, не прошедшего сортировку, определяется не только максимальный элемент, но и минимальный. Элемент с минимальным значением перемещается в начало массива, а, имеющий максимальное значение, переходит в конец массива. То есть, часть массива, не прошедшая сортировку, при каждом шаге итерации становиться меньше на два элемента. Создаётся впечатление, что такое улучшение повышает быстродействие алгоритма в два раза, поскольку на каждом шаге не отсортированная часть массива обрезается сразу с обеих сторон. Но следует помнить, что и число операций сравнения возрастает в два раза. То есть быстродействие улучшенного алгоритма увеличивается незначительно.
