Блинная сортировка

Блинная сортировка (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();
    }
}

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

Смотрите также: