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

Шейкерная сортировка (cocktail sort, shaker sort), или сортировка перемешиванием - усовершенствованная разновидность сортировки пузырьком, при которой сортировка производиться в двух направлениях, меняя направление при каждом проходе.

Проанализировав алгоритм пузырьковой сортировки, можно заметить:

• если при обходе части массива не происходит обмен элементов, то эту часть можно исключить, так как она уже отсортирована;
• при проходе от конца массива к началу минимальное значение сдвигается на первую позицию, при этом максимальный элемент перемещается только на один индекс вправо.

Исходя из приведенных идей, модифицируем сортировку пузырьком следующим образом:

• на каждой итерации, фиксируем границы части массива в которой происходит обмен;
• массив просматривается поочередно от начала массива к концу и от конца к началу;

Мы перемещаем минимальный элемент в начало массива, а максимальный - в конец, после этого выбрасываем индексы этих элементов из рабочей области. Таким образом, за каждую итерацию просматриваемая часть массива уменьшается на два элемента.

Визуализация алгоритма шейкерной сортировки

Реализация алгоритма

{$CODEPAGE UTF8}
program CocktailSort;
const
  arrayLength = 10;
var
  inputArray : array [1..arrayLength] of integer;
  i, tempValue: integer;
  firstIndex, lastIndex : integer;
begin
  randomize;
  writeln ('Исходный массив: ');
  {заполнение массива случайными числами}
  for i := 1 to arrayLength do
  begin
    inputArray[i] := random(100);
    write (inputArray[i]:4);
  end;
  writeln;

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

  firstIndex := 1;          {индекс первого элемента рабочей зоны массива}
  lastIndex := arrayLength; {индекс последнего элемента рабочей зоны массива}

  while firstIndex < lastIndex do
  begin
    {проход слева направо} 
    for i:= firstIndex to lastIndex-1 do
      if inputArray[i] > inputArray[i+1] then
      begin
        {обмен элементов}
        tempValue := inputArray[i];
        inputArray[i] := inputArray[i+1];
        inputArray[i+1] := tempValue;
      end;

    {проход справа налево}
    for i:= lastIndex downto firstIndex+1 do
      if inputArray[i] < inputArray[i-1] then
      begin
        {обмен элементов}
        tempValue := inputArray[i];
        inputArray[i] := inputArray[i-1];
        inputArray[i-1] := tempValue;
      end;

    {уменьшаем просматриваемую область}  
    firstIndex := firstIndex + 1;
    lastIndex := lastIndex - 1;
  end;

  writeln ('Отсортированный массив: ');
  for i := 1 to arrayLength do
    write (inputArray[i]:4);
  readln;
end.

Результат работы программы шейкерной сортировки массива: