Сортування гнома

Сортування гнома (Gnome sort) – простий в реалізації алгоритм сортування масиву, названий на честь садового гнома, який в такий спосіб сортує садові горщики.

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

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

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

using System;

class Program
{
    //метод для обміну елементів
    static void Swap(ref int item1, ref int item2)
    {
        var temp = item1;
        item1 = item2;
        item2 = temp;
    }

    //сортування Гнома
    static int[] GnomeSort(int[] unsortedArray)
    {
        var index = 1;
        var nextIndex = index + 1;

        while (index < unsortedArray.Length)
        {
            if (unsortedArray[index - 1] < unsortedArray[index])
            {
                index = nextIndex;
                nextIndex++;
            }
            else
            {
                Swap(ref unsortedArray[index - 1], ref unsortedArray[index]);
                index--;
                if (index == 0)
                {
                    index = nextIndex;
                    nextIndex++;
                }
            }
        }

        return unsortedArray;
    }

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

        Console.ReadLine();
    }
}