Книга: Фундаментальные алгоритмы и структуры данных в Delphi

Шейкер-сортировка

Шейкер-сортировка

Пузырьковая сортировка имеет одну малоизвестную вариацию, которая на практике дает незначительное увеличение скорости, - это так называемая шейкер-сортировка (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^)), время ее выполнения немного меньше, чем для пузырьковой сортировки. Причина, по которой алгоритм назван именно шейкер-сортировкой, состоит в том, что элементы в списке колеблются относительно своих позиций до тех пор, пока список не будет отсортирован.

Как и пузырьковая сортировка, шейкер-сортировка относится к неустойчивым алгоритмам.

Оглавление книги