Сортировка перемешиванием

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

Лучший случай для этой сортировки — отстортированный массив (О(n)), худший — отсортированный в обратном порядке (O(n²)).

s:= 1; {Первый элемент массива}
e:= 25; {Последний элемент массива}
while e > s do
begin
 for i:= s to e-1 do if Arr[i]>Arr[i+1] then
 begin
 tmp := Arr[i];
 Arr[i] := Arr[i+1];
 Arr[i+1] := tmp;
 c := c+1;
 end;
 for i:= e downto s+1 do if Arr[i] < Arr[i-1] then
 begin
 tmp := Arr[i];
 Arr[i] := Arr[i-1];
 Arr[i-1] := tmp;
 c := c+1;
 end;
 s:= s+1;
 e:= e-1;
end;

Литература

• Википедия
• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн