Gnome Sort

Gnome Sort also called Stupid sort is based on the concept of a Garden Gnome sorting his flower pots. A garden gnome sorts the flower pots by the following method-

• He looks at the flower pot next to him and the previous one; if they are in the right order he steps one pot forward, otherwise he swaps them and steps one pot backwards.
• If there is no previous pot (he is at the starting of the pot line), he steps forwards; if there is no pot next to him (he is at the end of the pot line), he is done.

Input :

Array- arr[]   
Total elements - n

Algorithm :

1. If you are at the start of the array then go to the right element (from arr[0] to arr[1]).
2. If the current array element is larger or equal to the previous array element then go one step right

                   if (arr[i] >= arr[i-1])
                      i++;

3. If the current array element is smaller than the previous array element then swap these two elements and go one step backwards

                       if (arr[i] < arr[i-1])
                       {
                           swap(arr[i], arr[i-1]);
                           i--;
                       }

4. Repeat steps 2) and 3) till ‘i’ reaches the end of the array (i.e- ‘n-1’)
5. If the end of the array is reached then stop and the array is sorted.

Example

   34 2 10 -9

• Underlined elements are the pair under consideration.
• “Red” colored are the pair which needs to be swapped.
• Result of the swapping is colored as “blue”

CODE:

# Python program to implement Gnome Sort 
  
# A function to sort the given list using Gnome sort 
def gnomeSort( arr, n): 
    index = 0
    while index < n: 
        if index == 0: 
            index = index + 1
        if arr[index] >= arr[index - 1]: 
            index = index + 1
        else: 
            arr[index], arr[index-1] = arr[index-1], arr[index] 
            index = index - 1
  
    return arr 
  
# Driver Code 
arr = [ 34, 2, 10, -9] 
n = len(arr) 
  
arr = gnomeSort(arr, n) 
print "Sorted seqquence after applying Gnome Sort :", 
for i in arr: 
    print (i) 

Output:           
Sorted sequence after applying Gnome sort: -9 2 10 34

Time Complexity – As there are no nested loop (only one while) it may seem that this is a linear O(N) time algorithm. But the time complexity is O(N^2). This is because the variable – ‘index’ in our program doesn’t always gets incremented, it gets decremented too.
However this sorting algorithm is adaptive and performs better if the array is already/partially sorted.

Auxiliary Space –  This is an in-place algorithm. So O(1) auxiliary space is needed.