Эффективность алгоритма сортировки прямого включения

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

Так, например, если последовательность уже отсортирована в нужном порядке, то максимальное число сравнений, которое может возникнуть на одном i- м шаге, c_max=i-1, а минимальное – это c_min=1. Если равновероятны все перестановки, то среднее число сравнений c_ср=i/2. Число перестановок в данной сортировке m_i=c_i+3 (включая барьер).

Если же массив отсортирован в обратном порядке от заданного, то это худший случай. Число сравнений будет равно с_max=n(n-1)/2, т. Е. – о(n²). Количество перестановок m_max=c_max +3(n-1), т.е. – о(n²).

Сортировка методом прямого выбора

В этом методе так же присутствуют две последовательности готовая и исходная, первая из которых на каждом шаге увеличивается на один элемент, а вторая уменьшается на один элемент. Отличие состоит в том, что вставляемый элемент в готовую последовательность помещается в её конец, при этом он не сравнивается с другими элементами готовой последовательности. Это возможно за счёт того, что среди элементов исходной последовательности выбирают каждый раз наименьший элемент (если сортируют данные по возрастанию) из всех. Минимальный элемент на i-м шаге будет больше минимального элемента шага i-1, который был найден на предыдущем шаг, поэтому его можно смело располагать в конец готовой последовательности. Найденный минимальный элемент меняется местами с первым элементом исходной последовательности, после чего исходная последовательность уменьшается на один элемент.

Отсортируем методом прямого выбора (табл. 11.2) последовательность элементов: 10, 3, 11, 8, 2, 15, 44, 9 по возрастанию.

Таблица 11.2

Принцип работы сортировки прямым выбором

Шаг	Готовая последовательность	Исходная последовательность
1	2	10, 3, 11, 8, 15, 44, 9
2	2, 3	10, 11, 8, 15, 44, 9
3	2, 3, 8	10, 11, 15, 44, 9
4	2, 3, 8, 9	10, 11, 15, 44
5	2, 3, 8, 9, 10	11, 15, 44
6	2, 3, 8, 9, 10, 11	15, 44
7	2, 3, 8, 9, 10, 11, 15	44
8	2, 3, 8, 9, 10, 11, 15, 44

Блок схема для данного алгоритма приведена ниже (рис. 11.3).

Эффективность алгоритма сортировки прямого выбора

Число сравнений ключей c не зависит от начального порядка ключей, так что поведение этого метода менее естественно, чем поведение прямого включения. При любом расположении ключей c=n(n-1)/2, а порядок числа сравнений, таким образом, о(n²). Число перестановок минимально м_min=3(n-1) в случае изначально упорядоченных ключей и максимально, м_max=3(n-1)+с, если первоначально ключи располагались в обратном порядке, порядок о(n²). В худшем случае сортировка прямым выбором дает порядок n², как для числа сравнений, так и для числа перемещений.