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

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

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

Так, например, если последовательность уже отсортирована в нужном порядке, то максимальное число сравнений, которое может возникнуть на одном 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

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

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