Простейшие методы сортировки: метод выбора

Данный метод из группы простейших имеет лучшие характеристики по числу перестановок, хотя он, как и оба ранее рассмотренных метода, в целом имеет трудоемкость O(n²). Его чуть более лучшие показатели связаны с тем, что в некоторых ситуациях выполняется перестановка не соседних элементов, а отстоящих на некотором расстоянии друг от друга.

Пусть имеется n элементов а₁ а₂, а₃, . . ., а_n, расположенных в ячейках массива. Сортировка выполняется за (n–1) шаг, пронумерованных от 1 до n-1. На каждом i-ом шаге обрабатываемый набор разбивается на 2 части:

· левую часть образуют уже упорядоченные на предыдущих шагах элементы а₁, а₂, а₃, . . ., а_i-1

· правую часть образуют еще не обработанные элементы а_i, а_i+1, а_i+2, . . ., а_n

Суть метода состоит в том, что в необработанном наборе отыскивается наименьший элемент, который меняется местами с элементом а_i. На первом шаге (при i = 1), когда необработанным является весь исходный набор, это сводится к поиску наименьшего элемента в массиве и обмену его с первым элементом. Ясно, что поиск наименьшего элемента выполняется обычным попарным сравнением, но соседние элементы при этом не переставляются, что в целом уменьшает число пересылок.

Пример. Возьмем тот же исходный набор целых чисел: 15-33-42-07-12-19

В данном примере сделано 15 сравнений (как и в методе пузырька), но всего 4 перестановки. Эта особенность сохраняется и в целом: по числу сравнений метод выбора близок к методу пузырька, но по числу перестановок существенно превосходит оба рассмотренные выше методы (оценка числа перестановок n*log ₂ n)

Особенности программной реализации. Внешний цикл обрабатывает основные шаги и выполняет перестановку минимального элемента, а внутренний организует поиск наименьшего элемента в необработанной части массива

fori := 1 to n–1 do

Begin

k := i; temp := a [i]; {устанавливаем начальный минимальный элемент}

for j := i+1 to n do

if a [j] < temp then

begin{изменяем текущий минимальный элемент}

k := j; temp := a [j];

end;

a [k] := a [i]; a [i] := temp;

end;

Общее заключение по простейшим методам сортировки.

Метод обмена (пузырька) имеет единственное преимущество – нулевое число пересылок в случае, если исходный набор уже отсортирован в нужном порядке. В остальных случаях все его показатели пропорциональны n².

Метод вставок также дает хорошие результаты для упорядоченных входных данных (число сравнений и пересылок пропорционально n). Во всех остальных случаях его показатели пропорциональны n², хотя что касается оценки среднего числа сравнений, то она чуть лучше, чем у других методов. Многочисленные эксперименты показывают, что метод вставок дает наименьшее время сортировки среди всех простейших методов.

Метод выбора, как это и следовало ожидать, имеет лучшие показатели по числу пересылок, особенно – для общего случая, где оценка О(n*log ₂ n) заметно лучше оценки O(n²). Поэтому его можно рекомендовать к использованию из всех простейших методов в том случае, если именно число перестановок является наиболее важным.