Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi

Полагаем, вы согласитесь с тем, что сортировка была довольно-таки утомительной. При реализации алгоритма на языке Pascal "утомительность" выражается медленной скоростью работы. Тем не менее, существует один простой метод оптимизации пузырьковой сортировки: если при выполнении очередного прохода не было выполнено ни одной перестановки, значит, карты уже отсортированы в требуемом порядке.

Листинг 5.4. Пузырьковая сортировка

procedure TDBubbleSort(aList : TList;

aFirst : integer;

aLast : integer;

aCompare : TtdCompareFunc);

var

i, j : integer;

Temp : pointer;

Done : boolean;

begin

TDValidateListRange(aList, aFirst, aLast, 'TDBubbleSort');

for i := aFirst to pred(aLast) do

begin

Done := true;

for j := aLast downto succ ( i ) do

if (aCompare(aList.List^[j], aList.List^ ) < 0) then begin

{переставить j-ый и (j - 1)-ый элементы}

Temp := aList.List^ [ j ];

aList.List^[j] := aList.List^[j-1];

aList.List^[j-1] :=Temp;

Done := false;

end;

if Done then

Exit;

end;

end;

Пузырьковая сортировка принадлежит к алгоритмам класса O(n(^2^)). Как видите, в реализации присутствуют два цикла: внешний и внутренний, при этом количество выполнений каждого цикла зависит от количества элементов в массиве. При первом выполнении внутреннего алгоритма будет произведено n - 1 сравнений, при втором — n - 2, при третьем — n - 3 и т.д. Всего будет n - 1 таких циклов, таким образом, общее количество сравнений составит:

(n-1) + (n-2)+... + 1

Приведенную сумму можно упростить до n (n - 1)/2 или (n(^2^) - n)/2. Другими словами, получаем O(n(^2^)). Количество перестановок вычислить несколько сложнее, но в худшем случае (когда элементы в исходном наборе были отсортированы в обратном порядке) количество перестановок будет равно количеству сравнений, т.е. снова получаем O(n(^2^)).

Небольшая оптимизация метода пузырьковой сортировки, о которой мы говорили чуть выше, означает, что если элементы в наборе уже отсортированы в нужном порядке, пузырьковая сортировка будет выполняться очень быстро: будет выполнен всего один проход по списку, не будет сделано ни одной перестановки и выполнение алгоритма завершится, (n -1) сравнений и ни одной перестановки говорят о том, что в лучшем случае быстродействие пузырьковой сортировки равно O(n).

Одна большая проблема, связанная с пузырьковой сортировкой, да и честно говоря, со многими другими алгоритмами, состоит в том, что переставляются только соседние элементы. Если элемент с наименьшим значением оказывается в самом конце списка, он будет меняться местами с соседними элементами до тех пор, пока он не достигнет первой позиции.

Пузырьковая сортировка относится к нестабильным алгоритмам, поскольку из двух элементов с равными значениями первым в отсортированном списке будет тот, который находился в исходном списке дальше от начала. Если изменить тип сравнения на "меньше чем" или "равен", а не просто "меньше", тогда пузырьковая сортировка станет устойчивой, но количество перестановок увеличится, и введенная нами оптимизация не даст запланированного выигрыша в скорости.

Пузырьковая сортировка имеет одну малоизвестную вариацию, которая на практике дает незначительное увеличение скорости, - это так называемая шейкер-сортировка (shaker sort).

Рисунок 5.2. Два прохода с помощью шейкер-сортировки

Вернемся к картам. Выполните первый проход согласно алгоритму сортировки. Туз попадет на первую позицию. Теперь, вместо прохода колоды карт справа налево, пройдите слева направо: сравните вторую и третью карты и старшую карту поместите на третью позицию. Сравните третью и четвертую карты, и при необходимости поменяйте их местами. Продолжайте сравнения вплоть до достижения пары (12, 13). По пути к правому краю колоды вы "захватили" короля и переместили его на последнюю позицию.

А теперь снова пройдите колоду справа налево до второй карты. Во вторую позицию попадет двойка. Продолжайте чередовать направления проходов до тех пор, пока не будет отсортирована вся колода.

Листинг 5.5. Шейкер-сортировка

procedure TDShakerSort(aList :TList;

aFirst : integer; aLast : integer;

aCompare : TtdCompareFunc);

var

i : integer;

Temp : pointer;

begin

TDValidateListRange(aList, aFirst, aLast, 'TDShakerSort');

while (aFirst < aLast) do

begin

for i := aLast downto succ(aFirst) do

if (aCompare(aList.List^[i], aList.List^[i-1]) < 0) then begin

Temp := aList.List^[i];

aList.List^[i] := aList.List^[i-1];

aList.List^[i-1] := Temp;

end;

inc(aFirst);

for i := succ(aFirst) to aLast do

if (aCompare(aList.List^[i], aList.List^[i-1]) < 0) then begin

Temp := aList.List^[i];

aList.List^[i] := aList.List^[i-1];

aList.List^[i-1] := Teilend;

dec(aLast);

end;

end;

Несмотря на то что шейкер-сортировка принадлежит к алгоритмам класса O(n(^2^)), время ее выполнения немного меньше, чем для пузырьковой сортировки. Причина, по которой алгоритм назван именно шейкер-сортировкой, состоит в том, что элементы в списке колеблются относительно своих позиций до тех пор, пока список не будет отсортирован.