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



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

  • Июль
    2020
  • Пн
  • Вт
  • Ср
  • Чт
  • Пт
  • Сб
  • Вс
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31