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

Оба разбиравшихся выше метода можно тоже рассматривать как "обменные" сортировки.

Для рассматриваемого ниже метода обмен местами двух элементов представляет собой характерную особенность процесса.

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

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

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

Текстовый алгоритм:

1. Начало.

2. Выполнить цикл, пока i имеет значения от 2 до N, шаг = +1:

а) выполнить цикл, пока j имеет значения от N до i, шаг = -1:

тело цикла: если А(j-1) > А(j), то меняем местами эти два элемента.

3. Конец.

На рисунке 5 представлена блок-схема сортировки методом прямого обмена.

Рис. 5. Блок-схема сортировки методом прямого обмена

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

Сортировка методом прямого обмена имеет меньшую эффективность. Число шагов просмотра с обменом ≤ (n – 2), и из-за того, что "легкие" элементы "всплывают" по несколько сразу, то кажется, что сортировка происходит быстро. Но с другой стороны, "тяжелые" элементы, если они находятся наверху, перемещаются вниз на одну позицию при каждом шаге, что увеличивает время сортировки. Число обменов элементов оказывается довольно большим.

На рисунке 6 приведен пример сортировки методом прямого обмена.

Исходная последовательность	I = 1	I = 2	I = 3	I = 4	I = 5	I = 6	I = 7	I = 8
4 4	06	06	06	06	06	06	06	06
55	44	12	12	12	12	12	12	12
12	55	44	18	18	18	18	18	18
42	12	55	44	42	42	42	42	42
94	4 2	18	55	44	44	44	44	44
18	94	42	42	55	55	55	55	55
06	18	94	67	67	67	67	67	67
67	67	67	94	94	94	94	94	94

Рис. 6. Пример сортировки методом прямого обмена