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

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

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

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

Таблица 12.1

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

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

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

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

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