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

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

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

Примеры реализации

Pascal

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;
   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;
   end;
    s:= s+1;
    e:= e-1;
end;

C++

  #include <algorithm>
 
  template< typename Iterator >
  void cocktail_sort( Iterator first, Iterator last )
  {
      for( --last; first < last; --last, ++first )
      {
          for( Iterator i = first; i < last; ++i )
              if ( *(i + 1) < *i )
                  std::iter_swap( i, i + 1 );
 
          for( Iterator i = last - 1; i > first; --i )
              if ( *i < *(i - 1) )
                  std::iter_swap( i, i - 1 );
      }
  }