Gnome Sort

Reading time: 20 minutes | Coding time: 5 minutes

Gnome Sort is a simple sorting algorithm with time complexity O(N^2) where the key idea is to swap adjacent elements (if not in order) to sort the entire list. It is similar to Insertion sort except the fact that in this case, we swap adjacent elements.

It is inspired by the standard Dutch Garden Gnome sorting his flower pots. A garden gnome sorts the flower pots by the following method:

• If the flower pot just before and after him are in correct order, then he moves one step forward.
• If it is not in correct order, he swaps the pots and moves back one step.
• At the starting when there is no pot before him, he steps forward and on reaching the end of the pot line, the list is sorted.

The simplest sort algorithm is not Bubble Sort..., it is not Insertion Sort..., it's Gnome Sort!

Pseudocode

Here is pseudocode for the gnome sort using a zero-based array:

procedure gnomeSort(a[]):
pos := 0
while pos < length(a):
   if (pos == 0 or a[pos] >= a[pos-1]):
       pos := pos + 1
   else:
       swap a[pos] and a[pos-1]
       pos := pos - 1

Example

Put items in order by comparing the current item with the previous item. If they are in order, move to the next item (or stop if the end is reached). If they are out of order, swap them and move to the previous item. If there is no previous item, move to the next item.

Given an unsorted array, a = [5, 3, 2, 4], the gnome sort takes the following steps during the while loop. The current position is highlighted in bold and indicated as a value of the variable pos.

Current array	pos	Condition in effect	Action to take
[5, 3, 2, 4]	0	pos == 0	increment pos
[5, 3, 2, 4]	1	a[pos] < a[pos-1]	swap, decrement pos
[3, 5, 2, 4]	0	pos == 0	increment pos
[3, 5, 2, 4]	1	a[pos] ≥ a[pos-1]	increment pos
[3, 5, 2, 4]	2	a[pos] < a[pos-1]	swap, decrement pos
[3, 2, 5, 4]	1	a[pos] < a[pos-1]	swap, decrement pos
[2, 3, 5, 4]	0	pos == 0	increment pos
[2, 3, 5, 4]	1	a[pos] ≥ a[pos-1]	increment pos
[2, 3, 5, 4]	2	a[pos] ≥ a[pos-1]	increment pos:
[2, 3, 5, 4]	3	a[pos] < a[pos-1]	swap, decrement pos
[2, 3, 4, 5]	2	a[pos] ≥ a[pos-1]	increment pos
[2, 3, 4, 5]	3	a[pos] ≥ a[pos-1]	increment pos
[2, 3, 4, 5]	4	pos == length(a)	finished

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(n2), and space complexity for in-place sorting is O(1)

• Worst case time complexity: Θ(N^2)
• Average case time complexity: Θ(N^2)
• Best case time complexity: Θ(N)
• Space complexity: Θ(1) auxiliary

Implementations

Gnome sort is a sorting algorithm which is similar to Insertion sort, except that moving an element to its proper place is accomplished by a series of swaps, as in Bubble Sort.

Following is the implementation in C:

    #include <stdio.h> 
    void main()
    {
        int i, temp, ar[10], n;
        printf("\nEnter the elements number:");
        scanf("%d", &n);
        printf("\nEnter elements:\n");
        for (i = 0; i < n; i++)
            scanf("%d", &ar[i]);
        i = 0;
        while (i < n)
        {
            if (i == 0 || ar[i - 1] <= ar[i])
                i++;
            else
            {
                temp = ar[i-1];
                ar[i - 1] = ar[i];
                ar[i] = temp;
                i = i - 1;
            }
        }
        for (i = 0;i < n;i++)
            printf("%d\t", ar[i]);
    }

Following is the implementation in C++:

    #include <iostream> 
    using namespace std; 
  
    //gnome sort 
    void gnomeSort(int arr[], int n) 
    { 
        int index = 0; 
  
        while (index < n) { 
            if (index == 0) 
                index++; 
            if (arr[index] >= arr[index - 1]) 
                index++; 
            else { 
                swap(arr[index], arr[index - 1]); 
                index--; 
            } 
        } 
        return; 
    } 
  
    //print an array
    void printArray(int arr[], int n) 
    { 
        cout << "Sorted sequence after Gnome sort: "; 
        for (int i = 0; i < n; i++) 
            cout << arr[i] << " "; 
        cout << "\n"; 
    } 
  
    int main() 
    { 
        int arr[] = { 5, 3, 2, 4 }; 
        int n = sizeof(arr) / sizeof(arr[0]); 
  
        gnomeSort(arr, n); 
        printArray(arr, n); 
  
        return (0); 
    }

Following is the implementation in Java:

    public class GnomeSort {

        private static void gnomeSort(int[] ar) {
            int i = 1;
            int n = ar.length;
            while (i < n) {
                if (i == 0 || ar[i - 1] <= ar[i]) {
                    i++;
                } else {
                    int tmp = ar[i];
                    ar[i] = ar[i - 1];
                    ar[--i] = tmp;
                }
            }
        }

        public static void main(String[] args) {
            int[] ar= {5, 3, 2, 4};
            gnomeSort(ar);
            for (int i = 0; i < ar.length; i++) {
                System.out.println(ar[i]);
            }
        }
    }

Applications

• Gnome sort is used everywhere where a stable sort is not needed.
• Gnome Sort is an in-place sort that is does not require any extra storage.
• The gnome sort is a sorting algorithm which is similar to insertion sort in that it works with one item at a time but gets the item to the proper place by a series of swaps, similar to a bubble sort.
• It is conceptually simple, requiring no nested loops. The average running time is O(n^2) but tends towards O(n) if the list is initially almost sorted