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

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

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

Швидкодія

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

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

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

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

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

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

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

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

[ред. | ред. код]
#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;
    }
}
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;
    }
}
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;
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
}
// $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;
}

Посилання

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