Добавить комментарий

Алгоритм обрёл своё название, потому что может быть использован для сортировки стопки блинов... 

Находим максимальный элемент. Переворачиваем стопку от верхнего до максимального. Самый большой блин оказывется наверху. Теперь переворачиваем всю стопку. Самый большой оказался внизу. Неотсортированная часть стопки уменьшилась на один элемент. Повторяем действие с неотсортированной частью.

Т.е. единственной используемой операцией над сортируемыми данными является реверс части последовательности, и переворачиваемая часть всегда с одного края.

type
  TAI = array of integer;
...
procedure PancakeSort(var A: TAI);
var
    i : integer;
    maxI : integer;

    // Поиск максимума в левой части массива.
    // right - правая граница области поиска.
    function GetMaxIndex(right: integer): integer;
    var
        i   : integer;
        max : integer;
    begin
      result := Low(A);
      max := A[result];
      for i := Low(A)+1 to right do
      begin
        if A[i] >= max then
        begin
          max := A[i];
          result := i;
        end;
      end;
    end;

    // Реверс левой части массива.
    // right - правая граница переворачиваемой части.
    procedure Reverse(right: integer);
    var
        i : integer;
    begin
      for i := 0 to (right -1) div 2 do
        swap(A[i], A[right - i]);
    end;

begin
  // Несортированная область уменьшается на 1
  //   на каждом шаге.
  for i := High(A) downto Low(A)+1 do
  begin
    // Найдём положение максимального из несортированных.
    maxI := GetMaxIndex(i);
    // Если он уже самый правый, ничего делать не нужно,
    //  просто перейдём к следующей итерации.
    if maxI < i then
    begin
      // Если максимальный элемент не самый левый из несортированных,
      //  перевернём часть массива.
      if maxI>0 then Reverse(maxI);
      // Теперь максимальный из несортированных точно самый левый.
      // Перевернём несортированную область.
      Reverse(i);
      // Максимальный из несортированных теперь самый правый,
      //  несортированная область уменьшилась на 1.
    end;
  end;
end;

Поскольку реверс массива - это ещё один цикл, сложность получается не очень красивой.

Сложность: