Gnome sort

Updated: 15.09.2019

Gnome sort – an easy-to-implement array sorting algorithm, named after the garden gnome, which supposedly sorts garden pots using this method.

Description of the Gnome sorting algorithm

The algorithm finds the first pair of unsorted array elements and swaps them. This takes into account the fact that the obstruction leads to an incorrect arrangement of elements adjacent on both sides to the newly rearranged ones. Since all elements of the array after rearranged are not sorted, it is necessary to double-check only the elements before rearranged.

Implementation of the Gnome sort algorithm

using System;

class program
{
    // method for exchanging elements
    static void Swap(ref int item1, ref int item2)
    {
        var temp = item1;
        item1 = item2;
        item2 = temp;
    }

    // Gnome sort
    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("Gnome sorting");
        Console.Write("Enter elements of the array:");
        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("Sorted array: {0}", string.Join(",", GnomeSort(array)));

        Console.ReadLine();
    }
}
comments powered by Disqus