Сортировка с помощью прямого обмена
Классификация методов сортировки редко бывает осмысленной. Оба разбиравшихся до этого метода можно тоже рассматривать как “обменные” сортировки. Однако в данном разделе описан метод, где обмен местами двух элементов представляет собой характернейшую особенность процесса. Изложенный ниже алгоритм прямого обмена основывается на сравнении и смене мест для пары соседних элементов и продолжении этого процесса до тех пор, пока не будут упорядочены все элементы. Как и в упоминавшемся методе, повторяются проходы по массиву, сдвигая каждый раз наибольший (или наименьший) элемент оставшейся последовательности к левому концу массива. Если мы будем рассматривать массивы как вертикальные, а не горизонтальные построения, то элементы можно интерпретировать как пузырьки в чане с водой, причем вес каждого соответствует его ключу. В этом случае при каждом проходе один пузырёк как бы поднимается до уровня, соответствующего его весу. Такой метод широко известен под именем пузырьковая сортировка. Ниже он представлен в своем простейшем виде
PROCEDURE BubbleSort;
VAR i, j: index; x: item;
BEGIN
FOR i := 2 ТО n DO
FOR j := n ТО i ВУ -1 DO
IF a[j-1] > a[j] THEN
х := a[j-1]; a[j-1] := a[j]; a[j] := х
END
END
END
END BubbleSort;
Пример пузырьковой сортировки:
Улучшения этого алгоритма напрашиваются сами собой. На примере видно, что три последних прохода не влияют на порядок элементов из-за того, что они уже отсортированы. Очевидный приём улучшения этого алгоритма - запоминать, были или не были перестановки в процессе некоторого прохода. Если в последнем проходе перестановок не было, то алгоритм можно заканчивать. Это улучшение, однако, можно опять же улучшить, если запоминать не только сам факт, что обмен имел место, но и положение (индекс) последнего обмена. Ясно, что все пары соседних элементов выше этого индекса k уже находятся в желаемом порядке. Поэтому просмотры можно заканчивать на этом индексе, а не идти до заранее определенного нижнего предела для i. Внимательный программист заметит здесь некоторую своеобразную асимметрию. Один плохо расположенный пузырек на “тяжелом конце" в массиве с обратным порядком будет перемещаться на нужное место в один проход, но плохо расположенный элемент на "легком конце" будет просачиваться на свое нужное место на один шаг при каждом проходе. Проще было бы сказать так: всплывает пузырек сразу, за один проход, а тонет очень медленно, за один проход на одну позицию.
Например, массив
12 18 42 44 55 67 94 06
c помощью усовершенствованной пузырьковой сортировки можно упорядочить за один просмотр, а для сортировки массива
94 06 12 18 42 44 55 67
требуется семь просмотров. Такая неестественная симметрия наводит на мысль о третьем улучшении: чередовать направление последовательных просмотров. Получающийся при этом алгоритм, мы соответственно назовем Шейкерной сортировкой (ShakerSort). Напомним, что шейкером называется нечто вроде двух, накрывающих друг друга стаканов, в которых встряхиванием вверх-вниз готовят коктейль. Иллюстрация сортировки новым способом тех же восьми ключей:
Алгоритм шейкерной сортировки:
PROCEDURE ShakerSort;
VAR j. k, L, R: index; x: item;
BEGIN L := 2; R := n; k := n;
RЕРЕАТ
FOR j := R ТО L ВУ -1 DO
IF a[j-1] > a[j] THEN
x := a[j-1]; a[j-1] := a[j]; a[j] := x; k := j
END
END;
L := k+1;
FOR j := L ТО R ВУ +1 DO
IF a[j-1] > a[j] THEN
x:= a[j-1]; a[j-1]:= a[j]; a[j]:= х; k:=j
END
END;
R : = k-1
UNТIL L > R
END ShakerSort;
Анализ пузырьковой и шейкерной сортировок.
Число сравнений в строго обменном алгоритме:
C = (n2-n)/2,
а минимальное, среднее и максимальное число перемещений элементов (присваиваний) будет соответственно Mmin=0, Mаvg =3*(n2-n)/2, Мmax=З*(n2-n)/4. Анализ же улучшенных методов, особенно шейкерной сортировки, довольно сложен. Минимальное число сравнений Сmin = n-1. Кнут считает, что для улучшенной пузырьковой сортировки среднее число проходов пропорционально n-k1*n1/2 , а среднее число сравнений пропорционально 1/2 (n2 - n(k2 +In n)).
Обратите, однако, внимание на то, что все перечисленные выше усовершенствования не влияют на число перемещений, они лишь сокращают число излишних двойных проверок. К несчастью, обмен местами двух элементов - чаще всего более дорогостоящая операция, чем сравнение ключей, поэтому наши, вроде очевидные улучшения дают не такой уж большой выигрыш, как мы интуитивно ожидали. Такой анализ показывает, что обменная сортировка и ее небольшие усовершенствования представляют собой нечто средиее между сортировками с помощью включений и с помощью выбора. Фактически в пузырьковой сортировке нет ничего ценного, кроме её привлекательного названия (BubbleSort). Шейкерная же сортировка с успехом используется в тех случаях, когда известно, что элементы почти упорядочены - на практике это бывает весьма редко.
Можно показать, что среднее расстояние, на которое должен продвигаться каждый из n элементов во время сортировки, равно n/3 "мест". Эта цифра является целью в поиске улучшений, т. е. в поиске более эффективных методов сортировки. Все строгие приемы сортировки фактически передвигают каждый элемент на всяком элементарном шаге на одну позицию. Поэтому они требуют порядка n2 таких шагов. Следовательно, в основу любых улучшений должен быть положен принцип перемещения на каждом такте элементов на большие расстояния.
Другие методы сортировки:
1. Сортировки с помощью включения (by insertion).
2. Сортировки с помощью прямого выбора (by selection).
3. Сортировки с помощью обмена (by exchange).
