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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Сортування змішуванням
Клас Алгоритм сортування
Структура даних Масив
Найгірша швидкодія O(n^2)
Найкраща швидкодія O(n)
Середня швидкодія O(n^2)
Оптимальний Ні

Сортування змішуванням (англ. Cocktail sort) — один із різновидів алгоритму сортування бульбашкою. Відрізняється від сортування бульбашкою тим, що сортування відбувається в обох напрямках, міняючи напрямок при кожному проході. Цей алгоритм лише трішки складніший за сортування бульбашкою, однак, вирішує так звану проблему "черепах".

Швидкодія[ред.ред. код]

Ефективність алгоритму рівна O(n^2) водночас для середнє статистичного та найгіршого випадку, однак, вона прямує до O(n) якщо список вже не погано відсортований, наприклад, якщо кожен елемент знаходиться у позиції, яка відрізняється від кінцевої більше, ніж на k (k ≥ 1), то його швидкодіє рівна O(k*n).

Відмінності від сортування бульбашкою[ред.ред. код]

Сортування змішуванням мало чим відрізняється від сортування бульбашкою. Єдина його відмінність у тому, що замість багаторазового проходження через список знизу вгору, він проходить по черзі знизу вгору і згори вниз. Він може досягати трохи вищої ефективності, ніж алгоритм сортування бульбашкою. Причиною цьому є те, що алгоритм сортування бульбашкою проходить по списку лише в одному напрямі, а тому за одну ітерацію елементи списку можна перемістити лише на один крок.

Наприклад, для того, щоб відсортувати список (2,3,4,5,1), алгоритму сортування змішуванням достатньо лише одного проходу, у той час, як алгоритму сортування бульбашкою знадобиться чотири проходи. Однак, один прохід сортування змішуванням слід рахувати за два проходи сортування бульбашкою. Зазвичай, сортування змішуванням удвічі швидше за сортування бульбашкою.

Іншою можливою оптимізацією є запам'ятовування попередніх перестановок. У наступній ітерації, перестановки не повторюватимуться, а тому алгоритм матиме коротші проходи по списку.

Приклади реалізації на різних мовах програмування[ред.ред. код]

C++[ред.ред. код]

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

Java[ред.ред. код]

public static void cocktailSort(int[] a) {
    for (int k = a.length-1; k > 0; k--) {
        boolean swapped = false;
        for (int i = k; i > 0; i--)
            if (a[i] < a[i-1]) {
                // swap
                int temp = a[i];
                a[i] = a[i-1];
                a[i-1] = temp;
                swapped = true;
            }
 
        for (int i = 0; i < k; i++)
            if (a[i] > a[i+1]) {
                // swap
                int temp = a[i];
                a[i] = a[i+1];
                a[i+1] = temp;
                swapped = true;
            }
 
        if (!swapped)
            break;
    }
}

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;
      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;

Python[ред.ред. код]

def cocktail_sort(A):
    for k in range(len(A)-1, 0, -1):
        swapped = False
        for i in range(k, 0, -1):
            if A[i]<A[i-1]:
                a = A[i]
                b = A[i-1]
                A[i] = b
                A[i-1] = a
                swapped = True
 
        for i in range(k):
            if A[i] > A[i+1]:
                a = A[i]
                b = A[i+1]
                A[i] = b
                A[i+1] = a
                swapped = True
 
        if not swapped:
            return A

Посилання[ред.ред. код]