Пузырьковая сортировка.

Входное множество просматривается, при этом попарно сравниваются соседние элементы множества. Если порядок их следования не соответствует заданному критерию упорядоченности, то элементы меняются местами. В результате одного та- кого просмотра при сортировке по возрастанию элемент с самым большим значением ключа переместится ("всплывет") на последнее место в множестве. При следующем проходе на свое место "всплывет" второй по величине ключа элемент и т.д. Для постановки на свои места N элементов следует сделать N-1 проходов. Выходное множество, таким образом, формируется в конце сортируемой последовательности, при каждом следующем проходе его объем увеличивается на 1, а объем входного множества уменьшается на 1.

Порядок пузырьковой сортировки - O(N^2). Среднее число сравнений - N*(N-1)/2 и таково же среднее число перестановок, что значительно хуже, чем для обменной сортировки простым выбором. Однако, то обстоятельство, что здесь всегда сравниваются и перемещаются только соседние элементы, делает пузырьковую сортировку удобной для обработки связных списков. Перестановка в связных списках также получается более экономной.

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

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

Во-вторых, может быть учтено то обстоятельство, что за один просмотр входного множества на свое место могут "всплыть" не один, а два и более элементов. Это легко учесть, запоминая в каждом просмотре позицию последней перестановки и установки этой позиции в качестве границы между множествами для следующего просмотра. Именно эта модификация реализована в программной иллюстрации пузырьковой сортировке в примере 3.9. Переменная nn в каждом проходе устанавливает верхнюю границу входного множества. В переменной x запоминается позиция перестановок и в конце просмотра последнее запомненное значение вносится в nn. Сортировка будет закончена, когда верхняя граница входного множества станет равной 1.

{===== Программный пример 3.9 =====}

Procedure Sort( var a : seq);

Var nn, i, x : integer;

begin

nn:=N; { граница входного множества }

repeat x:=1; { признак перестановок }

for i:=2 to nn do { перебор входного множества }

if a[i-1] > a[i] then begin { сравнение соседних эл-в }

x:=a[i-1]; a[i-1]:=a[i]; a[i]:=x; { перестановка }

x:=i-1; { запоминание позиции }

end; nn:=x; { сдвиг границы }

until (nn=1); {цикл пока вых. множество не захватит весь мас.}

end;

Результаты трассировки программного примера 3.9 представлены в таблице 3.6.

Таблица 3.6

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

Сортировка Шелла.

Это еще одна модификация пузырьковой сортировки. Суть ее состоит в том, что здесь выполняется сравнение ключей, отстоящих один от другого на некотором расстоянии d. Исходный размер d обычно выбирается соизмеримым с половиной общего размера сортируемой последовательности. Выполняется пузырьковая сортировка с интервалом сравнения d. Затем величина d уменьшается вдвое и вновь выполняется пузырьковая сортировка, далее d уменьшается еще вдвое и т.д. Последняя пузырьковая сортировка выполняется при d=1. Качественный порядок сортировки Шелла остается O(N^2), среднее же число сравнений, определенное эмпирическим путем - log2(N)^2*N. Ускорение достигается за счет того, что выяв- ленные "не на месте" элементы при d>1, быстрее "всплывают" на свои места.

Пример 3.10 иллюстрирует сортировку Шелла.

{===== Программный пример 3.10 =====}

Procedure Sort( var a : seq);

Var d, i, t : integer; k : boolean; { признак перестановки }

begin d:=N div 2; { начальное значение интервала }

while d > 0 do { цикл с уменьшением интервала до 1 }

begin k:=true; {пузырьковая сортировка с интервалом d}

while k do { цикл, пока есть перестановки }

begin k:=false; i:=1;

for i:=1 to N-d do { сравнение эл-тов на интервале d }

begin if a[i] > a[i+d] then begin

t:=a[i]; a[i]:=a[i+d]; a[i+d]:=t; { перестановка }

k:=true; { признак перестановки }

end; { if ... } end; { for ... } end; { while k }

d:=d div 2; { уменьшение интервала }

end; { while d>0 } end;

Результаты трассировки программного примера 3.10 представлены в таблице 3.7.

Таблица 3.7