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

Вернемся к картам. Выполните первый проход согласно алгоритму сортировки. Туз попадет на первую позицию. Теперь, вместо прохода колоды карт справа налево, пройдите слева направо: сравните вторую и третью карты и старшую карту поместите на третью позицию. Сравните третью и четвертую карты, и при необходимости поменяйте их местами. Продолжайте сравнения вплоть до достижения пары (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'4 [i], aList.ListA[i-l]) < 0) then begin Temp := aList.ListA[i]; aList.ListA[i] : = aList.ListA[i-l]; aList.ListA[i-l] := Temp;
end; inc(aFirst);

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

for i := succ(aFirst) to aLast do if (aCompare(aList.ListA[i], aList.ListA[i-1]) < 0) thenbegin Temp := aList.ListA[i]; aList.ListA[i] := aList.ListA[i-1]; aList.ListA[i-1] := Teilend;
dec(aLast);
end;
end;

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

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

Пузырьковая сортировка || Оглавление || Сортировка методом выбора


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



Новости за месяц

  • Май
    2019
  • Пн
  • Вт
  • Ср
  • Чт
  • Пт
  • Сб
  • Вс