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

Обновлено: 18.02.2019

Шейкерная сортировка (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.

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

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

В приведенной программе производиться сортировка по возрастанию, для сортировки по убыванию необходимо изменить операторы сравнения в строках:
if inputArray[i] > inputArray[i+1] then, с больше - “>” на меньше - “<”
if inputArray[i] < inputArray[i-1] then, с меньше - “<” на больше - “>”

Поделиться: Vk Ok