Сортировка методом пузырька – это трогательное название запоминают все. Но далеко не все знают, что этот метод в полной мере воплощает принцип обменной сортировки: сравниваются и обмениваются местами два соседних элемента. При чем здесь пузырек? Если представить массив высоким и узким сосудом с жидкостью, а элементы массива – пузырьками, вес которых пропорционален величине ключа элемента, то каждый проход по массиву заставляет пузырек подняться кверху и занять место, соответствующее его весу. Алгоритм приведен в листинге 7.5.
Листинг 7.5. Сортировка методом пузырька
procedure SortBubble (var a: TData);
i,j: integer;
tmp : integer;
for i:=2 to N do begin
for j:=N downto i do
if a[j-1]>a[j] then begin // сравнение элементов
tmp:=a[j]; a[j]:=a[j-1]; a[j-1]:=tmp // обмен местами
Оптимизация предыдущего алгоритма включает в себя следующее:
массив можно считать уже упорядоченным, если на последнем проходе не было ни одной перестановки элементов
сравнение пар элементов можно производить только до места последней перестановки: раз не было перестановок, значит – дальше элементы упорядочены
при прохождении массива слева направо (снизу вверх) поднимается легкий пузырек. Почему бы не двигаться по массиву в обратном направлении – сверху вниз, опуская тяжелый пузырек?
Эти моменты учтены в шейкер-сортировке(от англ. shake – трясти), приведенной в листинге 7.6.
Листинг 7.6. Шейкер-сортировка
procedure SortShaker (var a: TData);
j,left,right: integer;
tmp : integer;
last :integer; // место последней перестановки
left:=2; right:=N; last:=N;
for j:=right downto left do //поднимаются легкие пузырьки
if a[j-1]>a[j] then begin
tmp:=a[j]; a[j]:=a[j-1]; a[j-1]:=tmp;
last:=j
left:=last+1; // запомнили место последней перестановки
for j:=left to right do //опускаются тяжелые пузырьки
if a[j-1]>a[j] then begin
tmp:=a[j]; a[j]:=a[j-1]; a[j-1]:=tmp;
last:=j
right:=last-1; // запомнили место последней перестановки
until left>right;
end; //Shaker
Число сравнений в алгоритме простого обмена равно C=1/2(N2-N), а минимальное и максимальное количества пересылок равны: Mmin=0, Mmax~(N2-N). Наименьшее число сравнений в шейкер-сортировке Cmin=(N-1) – это соответствует единственному проходу по упорядоченному массиву.
Все усовершенствования сортировки обменом приводят только к уменьшению числа сравнений. Но поскольку именно перестановка элементов занимает, как правило, гораздо большее время, то эти усовершенствования не приводят к значительному эффекту. Анализ показывает, что сортировка методом пузырька (и даже ее улучшенный вариант – шейкер-сортировка) менее эффективна, чем сортировка вставками и обменом.
Рассмотрим одно из усовершенствований простой сортировки обменом – метод убывающих приращений. Оно заключается в том, что на каждом этапе сравниваются и обмениваются местами элементы, стоящие друг от друга на некотором расстоянии. Это расстояние (шаг) на первом этапе равно примерно половине длине массива, с каждым этапом уменьшается, и на последнем этапе шаг равен единице. Улучшение происходит оттого, что на начальных этапах в сортировке участвуют немного элементов, с каждым этапом повышается отсортированность массива, и на последнем этапе, который есть сортировка простыми вставками, массив уже почти отсортирован, и перемещений элементов немного.
В этой сортировке важен правильный выбор величины шагов. Анализ показывает, что величины шагов не должны быть кратны друг другу, чтобы достигнуть лучших результатов. Кнут рекомендует такие последовательности (записанные в обратном порядке):
1, 4, 13, 40, 121, … , где stepk-1=3*stepk+1,
1, 3, 7. 15, 31, …где stepk-1=2*stepk+1.
В листинге 7.7 шаги выбирались по формуле stepk= stepk-1*3/5, начиная с step1=N div 2 и заканчивая шагом, равным единице.
