Шейкерная сортировка

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

 

type
  TAI = array of integer;
...
procedure ShakerSort(var A: TAI);
var
    i,
    leftBorder, newLeftBorder, // Левые границы несортированной области, для проходов справа налево. 
    rightBorder, newRightBorder // Правые границы несортированной области, для проходов слева направо. 
           : Integer; 
    direction : boolean; // Текущее направление сортировки.
begin
  // Стартовое положение. Весь массив - несортированная область.
  rightBorder := High(A)-1;
  leftBorder  := Low(A);
  direction := true;

  while rightBorder > leftBorder do // Продолжаем сортировку, пока границы не сойдутся.
  begin
    if direction then // Проходим попеременно, то направо, то налево.
    begin // Проход сортировки слева направо.
      newRightBorder := Low(A);
      for i := Low(A) to RightBorder do
      begin
        if A[i] > A[i+1] then
        begin
          swap(A[i], A[i+1]);
          newRightBorder := i;
        end;
      end;
      rightBorder := newRightBorder;
    end
      else
    begin  // Проход сортировки справа налево.
      newLeftBorder := High(A);
      for i := High(A) downto LeftBorder +1 do
      begin
        if A[i] < A[i-1] then
        begin
          swap(A[i], A[i-1]);
          newLeftBorder := i;
        end;
      end;
      leftBorder := newLeftBorder;
    end;
    direction := not(direction); // меняем направление для следующего прохода.
  end;
end;

 

Сложность:

Максимальная O(N2)
Минимальная O(N)
Средняя O(N2)