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

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

Клас	Алгоритм сортування
Структура даних	Масив
Найгірша швидкодія	$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 )
{
    while (last != first)
    {
        Iterator max = first;
        for ( Iterator i = first; i != last; ++i )
        {
            if ( *(i + 1) < *i )
            {
                std::iter_swap( i, i + 1 );
                max = i;
            }
        }
        last = max;
        Iterator 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) {
    int size = a.length;
    boolean swapped = false;
    for (int k = size - 1; k > 0; k--) {
        swapped = false;
        for (int i = k; i > size - 1 - k; 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 = size - k; 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

JavaScript

const swap = (arr, i, j) => {
    const akum = arr[i]
    arr[i] = arr[j]
    arr[j] = akum
}

function shakerSort(array) {
    let leftIndex = 0
    let rightIndex = array.length - 1

    while (leftIndex < rightIndex) {
        for (let idx = leftIndex; idx < rightIndex; idx++) {
            if ( array[idx] > array[idx + 1]) {
                swap(array, idx, idx + 1)
            }
        }
        rightIndex--;

        for (let idx = rightIndex; idx > leftIndex; idx--) {
            if ( array[idx] < array[idx - 1]) {
                swap(array, idx, idx - 1)
            }
        }
        leftIndex++;
    }

    return array
}

PHP

// $array - масив з числами

for ($k = count($array) - 1; $k > 0; $k--) {
    $swapped = false;
    
    for ($i = 0; $i < $k; $i++) {
        if ($array[$i] > $array[$i + 1]) {
            $elem_a = $array[$i];
            $elem_b = $array[$i + 1];
            $array[$i] = $elem_b;
            $array[$i + 1] = $elem_a;

            $swapped = true;
        }
    }

    for ($i = $k; $i > 0; $i--) {
        if ($array[$i] < $array[$i - 1]) {
            $elem_a = $array[$i];
            $elem_b = $array[$i - 1];
            $array[$i] = $elem_b;
            $array[$i - 1] = $elem_a;

            $swapped = true;
        }
    }

    if (!$swapped)
        break;
}

Посилання

• Java source code and an animated demo of cocktail sort (called bi-directional bubble sort) and several other algorithms
• .NET Implementation of cocktail sort and several other algorithms