Truly Awful Algorithms – Gnome Sort

Garden Gnome

During my pursuit to learn about new algorithms I came across one with a funny name, and a simple implementation, and is generally just awful to use in any real world case. So here we have Gnome Sort. Proposed by Hamid Sarbazi-Azad in 2000, this algorithm’s best feature is the existence of a single while to do all the sorting. Here’s an implementation of it in C# as an extension to an array of integers*:

public static class SortAlgorithms
    {
        public static int[] GnomeSort(this int[] a)
        {
            if (a.Length <= 1)
                return a;

            var i = 1;
            while (i < a.Length)             {
                if (a[i] >= a[i - 1])
                    i++;
                else
                {
                    var tmp = a[i];
                    a[i] = a[i - 1];
                    a[i - 1] = tmp;
                    if (i > 1)
                        i--;
                }
            }
            return a;
        }
    }

If you will, imagine you asked your garden gnome to sort your flower pots based on size, how would he go about it? Why he would walk down the line of flower pots and look at the one he was next to and the one behind it, and if the one he’s next to is small than the other one he’d swap them and continue to swap it backwards down the line until he no longer finds the pot he’s moving is smaller than the one before it. Then he just starts walking down the line again looking at pots. The best case for this sort is O(N) for an already sorted list, with O(N2) worst case time for a reverse sorted list. The alternative name for this sort is Stupid Sort, not because of the algorithm itself, but because gnomes are stupid and take the most direct approach to solving problems. On the plus side you only had to spend one loop!

* Consider this code MIT Licensed if for some insane reason you want to use it

Advertisements

3 thoughts on “Truly Awful Algorithms – Gnome Sort

    • It’s almost the same. In Bubble Sort you do multiple passes and may do a single swap at each step. In Gnome Sort you do one pass, but each time you check an element you may move it multiple times.

      Reply
  1. Pingback: Truly Awful Algorithms – BogoSort | NullWords Blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s