Млинцеве сортування

Млинцеве сортування (pancake sort) – алгоритм сортування масиву, в якому сортування здійснюється переворотом частини масиву.

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

В цьому алгоритмі до масиву можна застосовувати тільки одну операцію – переворот частини масиву. І на відміну від інших методів сортування, де намагаються зменшити кількість операцій порівняння, в цьому потрібно мінімізувати кількість переворотів.

Ідея алгоритму полягає в тому, щоб за кожен прохід, перемістити максимальний елемент в кінець масиву. Для цього необхідно виконати наступні кроки:

  1. На початку вибрати підмасив рівний по довжині поточному масиву;
  2. Знайти в ньому позицію максимального елементу;
  3. Якщо максимальний елемент розташований не в кінці підмасиву, то:
    • Перевертаємо частину масиву від початку до максимального значення;
    • Перевертаємо весь обраний підмасив;
  4. Зменшуємо робочу область масиву і переходимо до другого кроку.

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

using System;

class Program
{
    //метод для отримання індексу максимального елемента підмасиву
    static int IndexOfMax(int[] array, int n)
    {
        int result = 0;
        for (var i = 1; i <= n; ++i)
        {
            if (array[i] > array[result])
            {
                result = i;
            }
        }

        return result;
    }

    //метод для перевороту масиву
    static void Flip(int[] array, int end)
    {
        for (var start = 0; start < end; start++, end--)
        {
            var temp = array[start];
            array[start] = array[end];
            array[end] = temp;
        }
    }

    //млинцеве сортування
    static int[] PancakeSort(int[] array)
    {
        for (var subArrayLength = array.Length - 1; subArrayLength >= 0; subArrayLength--)
        {
            //отримуємо позицію максимального елементу підмасиву
            var indexOfMax = IndexOfMax(array, subArrayLength);
            if (indexOfMax != subArrayLength)
            {
                //переворот масиву до індексу максимального елементу
                //максимальний елемент підмасиву розташується на початку
                Flip(array, indexOfMax);
                //переворот всього вибраного підмасиву
                Flip(array, subArrayLength);
            }
        }

        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(", ", PancakeSort(array)));

        Console.ReadLine();
    }
}

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

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