Сортування по частинах

Сортування по частинах (Stooge sort) – рекурсивний алгоритм сортування масиву.

Опис алгоритму сортування по частинах

Алгоритм сортування stooge sort полягає в наступному:

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

Реалізація сортування по частинах

using System;

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

    //сортування по частинах
    static int[] StoogeSort(int[] array, int startIndex, int endIndex)
    {
        if (array[startIndex] > array[endIndex])
        {
            Swap(ref array[startIndex], ref array[endIndex]);
        }

        if (endIndex - startIndex > 1)
        {
            var len = (endIndex - startIndex + 1) / 3;
            StoogeSort(array, startIndex, endIndex - len);
            StoogeSort(array, startIndex + len, endIndex);
            StoogeSort(array, startIndex, endIndex - len);
        }

        return array;
    }

    static int[] StoogeSort(int[] array)
    {
        return StoogeSort(array, 0, array.Length - 1);
    }

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

        Console.ReadLine();
    }
}

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

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