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

Сортування змішуванням (cocktail sort, shaker sort), або шейкерне сортування – це вдосконалений різновид сортування бульбашкою, при якому сортування проводиться у двох напрямках, змінюючи напрям при кожному проході.

Опис алгоритму шейкерного сортування

Аналізуючи алгоритм сортування бульбашкою, можна помітити:

  • якщо при обході частини масиву не відбувається обмін елементів, то цю область можна виключити, так як вона вже відсортована;
  • при проходженні від кінця масиву до початку, мінімальне значення переміщається на першу позицію, при цьому максимальний елемент зміщується тільки на один індекс вправо.

Виходячи з наведених ідей, модифікуємо сортування бульбашкою наступним чином:

  • на кожній ітерації, фіксуємо межі області масиву в якій відбувається обмін;
  • пробігаємо масив по черзі від початку до кінця, та від кінця до початку.

Таким чином, ми переміщуємо мінімальний елемент на початок масиву, а максимальний - в кінець, після чого, зменшуємо робочу область масиву.

Реалізація сортування змішуванням

using System;

class Program
{
    //метод обміну елементів
    static void Swap(ref int e1, ref int e2)
    {
        var temp = e1;
        e1 = e2;
        e2 = temp;
    }

    //сортування змішуванням
    static int[] ShakerSort(int[] array)
    {
        for (var i = 0; i < array.Length / 2; i++)
        {
            var swapFlag = false;
            //прохід зліва направо
            for (var j = i; j < array.Length - i - 1; j++)
            {
                if (array[j] > array[j + 1])
                {
                    Swap(ref array[j], ref array[j + 1]);
                    swapFlag = true;
                }
            }

            //прохід справа наліво
            for (var j = array.Length - 2 - i; j > i; j--)
            {
                if (array[j - 1] > array[j])
                {
                    Swap(ref array[j - 1], ref array[j]);
                    swapFlag = true;
                }
            }

            //якщо обмінів не було
            if (!swapFlag)
            {
                break;
            }
        }

        return array;
    }

    static void Main(string[] args)
    {
        Console.WriteLine("Сортування змішуванням");
        Console.Write("Введіть елементи масиву: ");
        var parts = Console.ReadLine().Split(new[] { " ", ",", ";" }, StringSplitOptions.RemoveEmptyEntries);
        var array = new int[parts.Length];
        for (int i = 0; i < parts.Length; i++)
        {
            array[i] = Convert.ToInt32(parts[i]);
        }

        Console.WriteLine("Впорядкований масив: {0}", string.Join(", ", ShakerSort(array)));

        Console.ReadLine();
    }
}

Результат роботи програми:

Дивіться також: