Сортування змішуванням

Сортування змішуванням (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.

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