Усовершенствованная "пузырьковая" сортировка
Нетрудно заметить, что в приведенных процедурах сравнения элементов будут продолжаться даже после того, как массив станет упорядоченным после некоторого, не последнего, прохода. В зависимости от начальных данных массив может быть уже отсортирован уже на K-ом прохождении.
Но сравнения элементов (бесполезные) продолжаются. Ясно, что если на очередном проходе не было сделано ни одного обмена, то массив стал упорядоченным и сортировку можно прекратить.
Если мы будем фиксировать этот факт, то несущественное усложнение приведенной процедуры может дать существенный выигрыш во времени выполнения программы. Для этого можно использовать некоторую величину логического типа was_swap, определяющую, был ли обмен при последнем проходе, и очередной проход проводить только в случае, если обмен был. Приведем процедуры, учитывающие это обстоятельство.
procedure Bubble_Sort( var a : arrtype );
var r, i : integer;
was_swap : Boolean; {был обмен: was_swap = true,
не было: was_swap = false }
begin
was_swap := true;
r := n;
while ( r >= 2 ) and was_swap do
begin
was_swap := false;
for i := 1 to r - 1 do
if a[ i ] > a[ i + 1 ] then
begin
Swap( a[ i ], a[ i + 1 ] );
was_swap := true;
end;
r := r - 1
end
end;
Процесс совершенствования метода «пузырька» можно продолжить, если фиксировать не только сам факт обмена, но и место (индекс) последнего обмена, а затем учитывать его для уточнения правой границы r обрабатываемого участка массива.
Соответствующая процедура имеет вид:
procedure Bubble_Sort( var a : arrtype );
var r, i : integer;
was_swap : Boolean; {был обмен: was_swap = true,
не было: was_swap = false }
begin
was_swap := true;
r := n;
while ( r >= 2 ) and was_swap do
begin
was_swap := false;
for i := 1 to r - 1 do
if a[ i ] > a[ i + 1 ] then
begin
Swap( a[ i ], a[ i + 1 ] );
was_swap := true;
{«Свое» место занял элемент с индексом i+1}
end;
r := i {Новая правая граница
обрабатываемого участка массива}
end
end;
"Шейкер" - сортировка
Несмотря на все сделанные выше усовершенствования, «пузырьковая» сортировка следующего (почти упорядоченного!) массива 5, 7, 12, 28, 36, 85, 2 будет проведена за семь проходов.
Это связано с тем, что при сортировке рассматриваемым методом за один проход элемент не может переместиться влево больше чем на одну позицию. Так что если минимальный элемент массива находится в его правом конце (как в рассматриваемом примере), то придется выполнить максимальное число проходов.
Поэтому естественно напрашивается еще одно улучшение метода «пузырьковой» сортировки — запоминать не только факт обмена, но и место последнего обмена, так как ясно, что после него все пары расположены уже в правильном порядке. В этом случае время сортировки может несколько сократиться.
Еще одно улучшение мы добавим, периодически меняя направление сортировки, которое борется с некоторой асимметрией пузырькового метода. Асимметрия заключается в том, «тяжелый» элемент в «легком» конце массива более быстро всплывает на свое место, чем «легкий» элемент в «тяжелом» конце.
Действительно, массив 5 1 2 3 4 можно отсортировать за одни проход, а массив 2 3 4 5 1 будет отсортирован только на последнем 5 проходе. Поэтому массив 5 1 2 3 4 разумно сортировать слева направо, а массив 2 3 4 5 1 – справа налево.
Такой метод сортировки называется "шейкер"-сортировкой (от английского слова shake- трясти, встряхивать).
Его работа показана на рис. 3 на примере сортировки массива из 8 элементов:
67, 6, 18, 94, 42, 12, 55, 4
4 94 94 94 94
55 4 55 67 67
12 55 12 55 55
42 12 42 12 42
94 42 67 42 18
18 67 18 18 12
6 18 6 6 6
67 6 4 4
4
Направление прохода
Рис. 3
В процедуре, использующей «шейкер»-сортировку, будем использовать две новые величины:
l - левую границу ( индекс ) участка массива, обрабатываемого на каждом проходе;
r - то же, правую, а процесс упорядочения массива будем проводить, пока соблюдается условие l < r.
На школьном алгоритмическом языке такая процедура может быть представлена следующим образом:
алг Shaker_Sort( арг рез цел таб a[ 1 : n ] )
нач цел l, r, i, лог was_swap
was_swap := да
l := 1; r : = n
нц пока l < r и was_swap
was_swap := нет
нц для i от l до r -1 | Проход «слева направо»
если a[ i ] > a[ i + 1 ]
то Swap( a[ i ], a[ i + 1 ] )
was_swap := да
все
кц
r := r - 1
нц для i от r до l + 1 шаг -1 | Проход «справа налево»
если a[ i ] < a[ i - 1 ]
то Swap( a[ i ], a[ i - 1 ] )
was_swap := да
все
кц
l := l + 1
кц
кон
Как и в случае метода «пузырька», шейкер-сортировку можно ускорить, если фиксировать места (индексы) последнего обмена при проходах слева направо и справа налево, а затем использовать их для уточнения границ обрабатываемого участка массива. Ниже приведены соответствующие процедуры.
procedure Shaker_Sort( var a : arrtype );
var l, r, i : integer; was_swap : boolean;
begin
was_swap := true;
l := 1; r := n;
while ( l < r ) and was_swap do
begin
was_swap := false;
for i := 1 to r - 1 do { Проход «слева направо» }
if a[ i ] > a[ i + 1 ] then
begin
Swap( a[ i ], a[ i + 1 ] );
was_swap := true;
{ «Свое» место занял элемент с индексом i + 1 }
r := i { Новая правая граница обрабатываемого участка массива }
end;
for i := 1 to r - 1 do { Проход «справа налево» } проверить for i:=r downto l+1
if a[ i ] < a[ i - 1 ] then
begin
Swap( a[ i ], a[ i - 1 ] );
was_swap := true;
{ «Свое» место занял элемент с индексом i - 1 }
l := i { Новая левая граница обрабатываемого участка массива }
end;
end
end;
Procedure Shakesort(var x: vector);
var i,j,r,l, buf:integer;
begin
l:=2; r:=n; i:=n;
repeat
for j:=r downto l do
if x[j-1]>x[j] then
begin
buf:=x[j-1]; x[j-1]:=x[j]; x[j]:=buf;
i:=j
end;
l:=i+1;
for j:=l to r do
if x[j-1]>x[j] then
begin
buf:=x[j-1]; x[j-1]:=x[j]; x[j]:=buf; i:=j
end;
r:=i-1;
until l>r
end; {shakesort}
Заметим, что предложенное усовершенствование никак не влияет на количество обменов, оно лишь уменьшает число сравнений ключей. К сожалению, обмен двух элементов – намного более дорогостоящая операция, чем сравнения ключей, поэтому усовершенствования дают на практике значительно меньший эффект, чем следовало ожидать.
Алгоритм шейкер-сортировки выгодно использовать в том случае, когда известно, что элементы уже почти упорядочены, то есть ожидается малое число перестановок.