Сортування змішуванням
Сортування змішуванням (англ. Cocktail sort) — один із різновидів алгоритму сортування бульбашкою. Відрізняється від сортування бульбашкою тим, що сортування відбувається в обох напрямках, міняючи напрямок при кожному проході. Цей алгоритм лише трішки складніший за сортування бульбашкою, однак, вирішує так звану проблему «черепах».
Клас | Алгоритм сортування |
---|---|
Структура даних | Масив |
Найгірша швидкодія | |
Найкраща швидкодія | |
Середня швидкодія | |
Оптимальний | Ні |
Швидкодія
Ефективність алгоритму рівна водночас для середнє статистичного та найгіршого випадку, однак, вона прямує до якщо список вже не погано відсортований, наприклад, якщо кожен елемент знаходиться у позиції, яка відрізняється від кінцевої більше, ніж на k (k ≥ 1), то його швидкодіє рівна .
Відмінності від сортування бульбашкою
Сортування змішуванням мало чим відрізняється від сортування бульбашкою. Єдина його відмінність у тому, що замість багаторазового проходження через список знизу вгору, він проходить по черзі знизу вгору і згори вниз. Він може досягати трохи вищої ефективності, ніж алгоритм сортування бульбашкою. Причиною цьому є те, що алгоритм сортування бульбашкою проходить по списку лише в одному напрямі, а тому за одну ітерацію елементи списку можна перемістити лише на один крок.
Наприклад, для того, щоб відсортувати список (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