Сортировка массива C#. Алгоритм «Гномья сортировка»

Название этого алгоритма сортировки происходит от предполагаемого поведения садовых гномов при сортировке садовых горшков. Так Дик Грун описал поведение алгоритма: «Гномья сортировка основана на технике, используемой обычным голландским садовым гномом. Это метод, которым садовый гном сортирует линию цветочных горшков. По существу он смотрит на текущий и предыдущий садовые горшки: если они в правильном порядке, он шагает на один горшок вперёд, иначе он меняет их местами и шагает на один горшок назад. Граничные условия: если нет предыдущего горшка, он шагает вперёд; если нет следующего горшка, он закончил». Собственно, в этом описании и заложен весь алгоритм гномьей сортировки массива в C#.

Алгоритм

Цикл стартует не с нулевого, а первого элемента массива (см. граничные условия). В зависимости от того, как проходит сравнение двух элементов мы либо меняем их местами и отходим на шаг назад, либо не меняем и шагаем на шаг вперед. Особенность этого алгоритма заключается в том, что нам здесь не потребуются вложенные циклы, как, например, в пузырьковой сортировке.

Реализация гномьей сортировки массива в C#

Как и в случае с сортировкой перемешиванием нам потребуются два метода — Swap() для того, чтобы поменять два элемента местами и, собственно, метод реализующий гномью сортировку в C#.

//перестановка местами двух элементов в массиве
static void Swap(int[] array, int i, int j)
{
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

static void GnomeSort(int[] inArray)
{
    int i = 1;
    int j = 2;
    while (i < inArray.Length)
    {
        if (inArray[i - 1] < inArray[i])
        {
            i = j;
            j += 1;
        }
        else
        {
            Swap(inArray, i - 1, i);
            i -= 1;
            if (i == 0)
            {
                i = j;
                j += 1;
            }
        }
    }
}

Пример сортировки массива

Console.WriteLine("Введите через запятую целые числа и нажмите Enter");
string[] nums = Console.ReadLine().Split(new char[] { ',' });
int[] intArray = new int[nums.Length];
for (int i = 0; i < nums.Length; i++)
{
    intArray[i] = int.Parse(nums[i]);
}

GnomeSort(intArray);

Console.WriteLine("\r\nОтсортированный массив:");
foreach (int value in intArray)
{
    Console.Write($"{value} ");
}

Консольный вывод: