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

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

Сортировка прямого обмена. Её эффективность

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

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

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

Таблица 12.1

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

Реализовать данный алгоритм можно простым способом (рис. 12.1), где присутствует большое число проходов «вхолостую».

Так же можно реализовать с использованием флага (рис. 12.2), который позволяет сэкономить на числе пустых проходов по массиву и числе сравнения соседних элементов. Чтобы лишний раз не переставлять элементы, можно ввести флажок b, который остается в значении false , если при очередном проходе не будет произведено ни одного обмена. Добавления можно проанализировать, сравнив блок-схемы (рис. 12.1 и 12.2).

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