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

к сведению

Основано на статьях "Сортировка выбором", "Сортировка выбором", "Selection Sort Algorithm", "Сортировка выбором минимумов (максимумов)" и "Общие сведения об алгоритмах сортировки".

Пожалуй, самый простой алгоритм сортировок – это сортировка выбором (англ. selection sort). Судя по названию сортировки, необходимо что-то выбирать (максимальный или минимальный элементы массива). Алгоритм сортировки выбором находит в исходном массиве максимальный или минимальный элементы, в зависимости от того как необходимо сортировать массив, по возрастанию или по убыванию. Если массив должен быть отсортирован по возрастанию, то из исходного массива необходимо выбирать минимальные элементы. Если же массив необходимо отсортировать по убыванию, то выбирать следует максимальные элементы.

На массиве из $n$ элементов имеет время выполнения в худшем, среднем и лучшем случае $O(n^2)$, предполагая что сравнения делаются за постоянное время.

Алгоритм

Шаги алгоритма:

• находим номер минимального значения в текущем списке;
• производим обмен этого значения со значением первой неотсортированной позиции (обмен не нужен, если минимальный элемент уже находится на данной позиции);
• теперь сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы.

Пример работы

Для того, чтобы отсортировать массив в порядке возрастания, следует на каждой итерации найти элемент с наибольшим значением. С ним нужно поменять местами последний элемент. Следующий элемент с наибольшим значением становится уже на предпоследнее место. Так должно происходить, пока элементы, находящиеся на первых местах в массиве, не окажутся в надлежащем порядке.