Сортування гребінцем

Сортування гребінцем (Comb sort) – алгоритм сортування масиву, є поліпшеним варіантом сортування бульбашкою, при цьому, по швидкості виконання, конкурує з алгоритмом швидкого сортування.

Основна ідея сортування гребінцем полягає в усуненні так званих “черепах” – маленьких значень в кінці масиву, які суттєво уповільнюють сортування бульбашкою.

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

У сортуванні бульбашкою завжди порівнюються два сусідні елементи масиву даних, відстань між якими дорівнює одиниці. Основна ідея сортування гребінцем полягає у використанні більшої відстані між порівнюваними елементами. При цьому спочатку необхідно брати велику відстань, і поступово зменшувати її, в міру упорядкування даних аж до одиниці. Спочатку порівнюється перший і останній елемент масиву, і на кожній ітерації зменшується розрив між елементами на фактор зменшення. Ітерації тривають до тих пір, поки різниця індексів більше одиниці, а потім масив сортується методом бульбашки.

Оптимальне значення фактора зменшення рівне 1/(1-e^-φ) ≈ 1.247, де е – основа натурального логарифма, а φ – золотий перетин.

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

using System;

class Program
{
    //метод обміну елементів
    static void Swap(ref int value1, ref int value2)
    {
        var temp = value1;
        value1 = value2;
        value2 = temp;
    }
    
    //метод генерування наступного кроку
    static int GetNextStep(int s)
    {
        s = s * 1000 / 1247;
        return s > 1 ? s : 1;
    }

    static int[] CombSort(int[] array)
    {
        var arrayLength = array.Length;
        var currentStep = arrayLength - 1;
        
        while (currentStep > 1)
        {
            for (int i = 0; i + currentStep < array.Length; i++)
            {
                if (array[i] > array[i + currentStep])
                {
                    Swap(ref array[i], ref array[i + currentStep]);
                }
            }

            currentStep = GetNextStep(currentStep);
        }

        //сортування бульбашкою
        for (var i = 1; i < arrayLength; i++)
        {
            var swapFlag = false;
            for (var j = 0; j < arrayLength - i; j++)
            {
                if (array[j] > array[j + 1])
                {
                    Swap(ref array[j], ref array[j + 1]);
                    swapFlag = true;
                }
            }

            if (!swapFlag)
            {
                break;
            }
        }

        return array;
    }

    //метод для отримання масиву заповненого випадковими числами
    static int[] GetRandomArray(int length, int minValue, int maxValue)
    {
        var r = new Random();
        var outputArray = new int[length];
        for (var i = 0; i < outputArray.Length; i++)
        {
            outputArray[i] = r.Next(minValue, maxValue);
        }

        return outputArray;
    }

    static void Main(string[] args)
    {
        var arr = GetRandomArray(15, 0, 10);
        Console.WriteLine("Вхідні дані: {0}", string.Join(", ", arr));
        Console.WriteLine("Впорядкований масив: {0}", string.Join(", ", CombSort(arr)));
        Console.ReadLine();
    }
}