|
====================================================================
> 4. Сортировка пузырьком(BubbleSort) и ее улучшения.
====================================================================
Операция сравнения/перестановки выполняется для каждых двух стоящих
рядом элементов. После первого прохода по массиву "вверху" оказывается
самый "легкий" элемент. Следующий цикл сортировки выполняется начиная
со второго элемента, в результате чего вторым в массиве оказывается
второй наименьший по величине элемент, и так далее.
{ Сортируются записи типа item по ключу item.key }
{ для вспомогательных переменных используется тип index }
procedure BubbleSort;
var i,j: index; x:item;
begin for i:=2 to n do
begin for j:=n downto i do
if a[j-1].key > a[j].key then
begin x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x;
end;
end;
end;
Пример 1. Проходим по массиву снизу вверх. Меньшие/более легкие/
элементы 'всплывают' наверх, давая название методу.
Hачальные i i i i i i i
ключи 2 3 4 5 6 7 8
44 /-> 06 06 06 06 06 06 06
55 | 44 /-> 12 12 12 12 12 12
12 | 55 | 44 /-> 18 18 18 18 18
42 | 12-/ 55 | 44 /-> 42 42 42 42
94 | 42 /-> 18-/ 55 | 44 --> 44 44 44
18 | 94 | 42 42-/ 55 55 --> 55 55
06-/ 18-/ 94 -> 67 67 67 67 --> 67
67 67 67-/ 94 94 94 94 94
Алгоритм пузырька очень медленен и неэффективен. Тем не менее,
у него есть громадный плюс: он прост и его можно по-всякому улучшать.
Чем мы сейчас и займемся.
Посмотрите на пример 1. Три последних прохода никак не влияют на
порядок элементов, поскольку те уже отсортированы. Очевидный способ улучшить
алгоритм - запоминать, производился ли на данном проходе какой-либо обмен.
Если нет - это означает, что алгоритм может закончить работу.
Этот процесс улучшения можно продолжить, если запоминать не столько
сам файт обмена, но и место (индекс) последнего обмена. Ведь ясно, что
все пары соседих элементов с индексами, меньшими этого индекса k,
уже расположены в нужном порядке. Поэтому следующие прозоды можно заканчивать
на этом индексе, вместо того чтобы двигаться до установленной заранее
нижней границы i.
Пойдем дальше: внимательный человек легко может заметить странную
асимметрию: один неправильно расположенный 'пузырек' в 'тяжелом'
конце рассортированного массива всплывет за один проход, а неправильно
расположенный элемент в легком конце будет опускаться на правильное
место только на один шаг при каждом проходе.
Hапример, массив 12 18 42 44 55 67 94 06 будет отсортирован за 1 проход,
а сортировка массива 94 06 12 18 42 44 55 67 потребует 7 проходов.
Эта неестественная асимметрия подсказывает третье улучшение:
менять направление следующих один за другим проходов.
Получившийся алгоритм иногда называют 'шейкер-сортировкой'.
Пример его работы на том же входном массиве.
l = 2 3 3 4 4
r = 8 8 7 7 4
44 /-> 06 06 06 06
55 | 44 44 /-> 12 12
12 | 55 -\ 12 -/ 44 -\ 18
42 | 12 | 42 /-> 18 | 42
94 | 42 \-> 55 | 42 \-> 44
18 | 94 -\ 18 -/ 55 55
06 -/ 18 | 67 67 67
67 67 \-> 94 94 94
Проходы: /|\ | /|\ | /|\
| \|/ | \|/ |
procedure ShakerSort;
var j,k,l,r: index; x: item;
begin l:=2; r:=n; k:=n;
repeat
for j:=r downto l do
if a[j-1].key > a[j].key then
begin x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x;
k:=j;
end;
l:=k+1;
for j:=l to r do
if a[j-1].key > a[j].key then
begin x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x;
k:=j;
end;
r:=k-1;
until l>r;
end;
Анализ алгоритма простого пузырька:
Число сравнений
C = 1/2 (n^2 - n),
Числа пересылок:
Mmin = 0, Mсреднее = 3/4 (n^2 - n), Mmax = 3/2 (n^2 - n).
Анализ шейкер-сортировки (из книги Д.Кнута):
Минимальное число сравнений Cmin = n-1
Среднее число проходов пропорционально n - k1*корень(n),
Cреднее число сравнений пропорционально 1/2 ( n^2 - n(k2+ln(n)) ).
Hо, как видно, все предложенные усовершенствования не влияют на число
обменов. К сожалению, обмен - операция, как правило, гораздо более
медленная, чем сравнение ключей, поэтому реальный эффект улучшений
гораздо меньше, чем можно было бы ожидать.
Метод пузырька и описанные улучшения на практике крайне неэффективны,
SelectSort и InsertSort работают быстрее. Шейкер-сортировку выгодно
использовать, когда известно, что элементы уже почти упорядочены.
Hо даже в этом случае обычно применяют все же InsertSort, которая
менее чувствительна к степени упорядоченности.
|
