Алгоритм сортировки перемешиванием (Шейкерная сортировка, двунаправленная пузырьковая сортировка)

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

Механизм алгоритма сортировки по возрастанию следующий:

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

Цикл завершается, когда диапазон сойдется в середине массива.

const
    N = 10; // размер массива
var
    i, low, high, h : Integer;
    mas : array[1..N] of Integer;
begin
    low := 1; // начало и конец массива
    high := N - 1;

    while low < high do begin
      for i := low to high do // проход массива от начала к концу, перемещение большего значения
         if mas[i] > mas[i+1] then begin // замена элементов местами
             h := mas[i];
             mas[i] := mas[i+1];
             mas[i+1] := h;
         end;

    high := high - 1; // сокращение сортируемого диапазона от конца

    for i := high downto high do // проход массива от конца к началу, перемещение меньшего значения
        if mas[i] > mas[i+1] then begin // замена элементов местами
            h := mas[i];
            mas[i] := mas[i+1];
            mas[i+1] := h;
         end;

   low := low + 1; // сокращение сортируемого диапазона от начала
  end;
end;