After a bit of down time for personal reasons, here is the fourth post in the series on sorting algorithms. This time round we’re taking a good look at the Gnome Sort.

People often do a double-take when hearing the term “Gnome Sort” because it’s not that common. The Gnome Sort is extremely simple, and is very similar to the principle behind the Insertion Sort (which we’ll be covering soon).

The Gnome Sort is yet another comparison and exchange sort which has elements that are similar to the Bubble Sort. If you haven’t read up on the Bubble Sort, be sure to do that before reading this article as it may help with your understanding.

Let’s get straight into it!

Common Terms

• Data set - the array or list of items that is to be sorted.
• n - the number of elements in the data set.
• Bubble - perform a Bubble Sort-like shuffle of an item in a given direction.

The Algorithm

The first principle to bear in mind when doing a Gnome Sort is that as the algorithm progresses, all items to the left of the current item are always in order. Each iteration of the algorithm moves the current item to the correct spot with respect to the previously sorted items.

The first part of the algorithm looks at the first two items in the data set and swaps them around if they are in the wrong order. Then, for each iteration thereafter, the next item is bubbled backwards towards to head of the list until a value is encountered which is less than the current item (or the head of the list is reached). At this point, the current item is left alone, and the sort continues from the next item.

The Example

As per usual we will use the same initial data set that we used for the Bubble Sort and Cocktail Sort to aid in highlighting the differences.

The initial set looks like this:

33 98 74 13 55 20 77 45 64 83

The first step is to compare the firs two values:

33 98 74 13 55 20 77 45 64 83

Given that they are in the correct order we leave this two values alone. We can say that two items in the data set are in order.

Next we look at the item immediately after the in order items and compare that to the last sorted item:

33 98 74 13 55 20 77 45 64 83

We can see that these two are not in the correct order, so we swap them:

33 74 98 13 55 20 77 45 64 83

Given that we had to swap the values in the previous step, we can’t assume that the current item is in the right location with respect to the other in order items, and hence we need to continue to work backwards. We compare the current item to the preceeding item in the data set:

33 74 98 13 55 20 77 45 64 83

These two values are in the correct order, so we can now stop this iteration. At this point, the first three items in the set are sorted with respect to each other. Next, we move to the fourth item, and compare that with the last of the in order items:

33 74 98 13 55 20 77 45 64 83

They’re out of order, so we swap them:

33 74 13 98 55 20 77 45 64 83

… and we keep bubbling backwards until we reach either a value that is smaller or the head of the list:

33 74 13 98 55 20 77 45 64 83 33 13 74 98 55 20 77 45 64 83 33 13 74 98 55 20 77 45 64 83 13 33 74 98 55 20 77 45 64 83

Here we can see that 13 was the smallest number, so it was bubbled all the way to the head of the list. We then move on to the next iteration where we again compare the next item with the head of the list, and again bubble backwards until we reach the correct location. Here is a summary of the steps for the next iteration:

13 33 74 98 55 20 77 45 64 83 13 33 74 55 98 20 77 45 64 83 13 33 74 55 98 20 77 45 64 83 13 33 55 74 98 20 77 45 64 83 13 33 55 74 98 20 77 45 64 83

55 is now in the correct spot with regards to the other pre-sorted items, so we move onto the next item. At this point it should be fairly obvious what’s going on, so I shall show a summary for the rest of the example:

13 33 55 74 98 20 77 45 64 83 13 33 55 74 20 98 77 45 64 83 13 33 55 74 20 98 77 45 64 83 13 33 55 20 74 98 77 45 64 83 13 33 55 20 74 98 77 45 64 83 13 33 20 55 74 98 77 45 64 83 13 33 20 55 74 98 77 45 64 83 13 20 33 55 74 98 77 45 64 83 13 20 33 55 74 98 77 45 64 83 13 20 33 55 74 98 77 45 64 83 13 20 33 55 74 77 98 45 64 83 13 20 33 55 74 77 98 45 64 83 13 20 33 55 74 77 98 45 64 83 13 20 33 55 74 77 45 98 64 83 13 20 33 55 74 77 45 98 64 83 13 20 33 55 74 45 77 98 64 83 13 20 33 55 74 45 77 98 64 83 13 20 33 55 45 74 77 98 64 83 13 20 33 55 45 74 77 98 64 83 13 20 33 45 55 74 77 98 64 83 13 20 33 45 55 74 77 98 64 83 13 20 33 45 55 74 77 98 64 83 13 20 33 45 55 74 77 64 98 83 13 20 33 45 55 74 77 64 98 83 13 20 33 45 55 74 64 77 98 83 13 20 33 45 55 74 64 77 98 83 13 20 33 45 55 64 74 77 98 83 13 20 33 45 55 64 74 77 98 83 13 20 33 45 55 64 74 77 98 83 13 20 33 45 55 64 74 77 83 98 13 20 33 45 55 64 74 77 83 98 13 20 33 45 55 64 74 77 83 98

Note that we do not know for sure that an item is in the correct location until the entire set has been sorted.

The Implementation

Here is a sample implementation written in C#. It is heavily commented in the hope that it will aid in understanding how the algorithm works:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

/// <summary>
/// Example implementation of the Gnome Sort algorithm.
/// </summary>
/// <param name="dataSet">Array of items to be sorted.</param>
static void GnomeSort(int[] dataSet)
{
    // start at the second item
    int i = 1;

    // keep track of the 'next' item so we
    // can jump to it when the current iteration
    // is finished.
    int j = 2;

    // loop until we reach the end of the data set
    while (i < dataSet.Length)
    {
        // swap if required
        if (dataSet[i - 1] > dataSet[i])
        {
            Swap(dataSet, i - 1, i);

            // move backwards through the sorted items
            // until we find the rightful spot.
            --i;

            // stop at the head of the list
            if (i == 0)
            {
                // jump to the next item in the set
                i = j++;
            }
        }
        else
        {
            // jump to the next item in the set
            i = j++;
        }
    }
}

The Complexity

This is not a very efficient algorithm. It’s time and space complexity are exactly that of the Bubble Sort. That is, the time complexity is O(n²), and space complexity for in-place sorting is O(1).

Other Implementations

I’m slowly gathering a collection of implementations of all the sorting algorithms, including the ones listed above, that I’m covering in this series and posting them up on BitBucket. The Gnome Sort implementations can be found here.

Note: You’ll need Mercurial if you want to pull directly from the repository, otherwise you’ll have to copy and paste from the web.

References and Other Information

1. Wikipedia - Gnome sort

Next up, we’ll be looking at the first of the mind-bending algorithms: the Quick Sort.

Disclaimer

I’m no expert, nor an authority. The post above is based on my experience and a bit of research. If you find something wrong with anything I’ve said please let me know. Comments and feedback are greatly appreciated.

Note: For those reading this article in an RSS reader, you may find the colours do not appear in the examples properly. For some reason the feed is stripping out some of the formatting. I will do my best to fix this up soon.