Сортування Шелла

Сортування Шелла (Shell sort) – алгоритм сортування масиву, який є узагальненням сортування включенням.

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

Алгоритм сортування Шелла базується на двох ідеях:

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

Для усунення недоліків алгоритму Insertion Sort, в сортуванні Шелла здійснюється декілька впорядкувань виключенням. При цьому кожного разу порівнюються елементи, що розташовані на різних відстанях один від одного, починаючи від найбільш віддалених(d = 1⁄2 довжини масиву) до порівняння сусідніх елементів(d = 1).

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

using System;

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

    static int[] ShellSort(int[] array)
    {
        //відстань між елементами, які порівнюються
        var d = array.Length / 2; 
        while (d >= 1)
        {
            for (var i = d; i < array.Length; i++)
            {
                var j = i;
                while ((j >= d) && (array[j - d] > array[j]))
                {
                    Swap(ref array[j], ref array[j - d]);
                    j = j - d;
                }
            }

            d = d / 2;
        }

        return array;
    }

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

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

        Console.ReadLine();
    }
}

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

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