Gnome Sort, a Variant of Insertion Sort

Written by Raza on. Posted in C++

Last time, we discussed a sorting technique known as insertion sort. It is a very good sorting procedure and the simplest sorting algorithm for short lists and small amount of data. For larger lists, it’s running time increases exponentially which renders it inefficient. A number of variations have also been introduced to insertion sort, some of which are more efficient and some are equally good. Shell sort and Gnome Sort are two such variations. I prefer Gnome Sort so I will explain it to you in this article.

Insertion sort iterates through the list and then places each element at its proper position. This process goes on and on for each element of the array. Gnome sort does the same trick but slightly differently. It runs through the array starting from the second element and compares it with its previous element. If the current element is less than the previous element, it swaps them and goes back one step. Then it checks it again with its previous element and so on.

In short, it runs through the array but only if required. If the current element is greater than the previous element, it moves forward one step immediately. Suppose we have an Array of integers. If the array is already sorted, the loop would run just once looking at each element. If it is unsorted, it would run the normal procedure, looking at each element and then moving one step forwards or backwards.

We have the following Array of integers of length 6 in this case.

(5, 7, 4, 10, 1, 2)

Let us see for each value of the loop counter what it does with the array. Elements being considered to swap are shown in bold and the current position of the loop is underlined. Note along the way that the counter never comes at the first element of the Array. When it is on the second element, it only increases its value. Guess why? There is some memory issue involved here.

 

First Step:

(5, 7, 4, 10, 1, 2)   —>   Counter = 1

(5, 7, 4, 10, 1, 2)   —>    (5, 7, 4, 10, 1, 2)   —>    Counter = 2

 

Second Step:

(5, 7, 4, 10, 1, 2)   —>   Counter = 2

(5, 7, 4, 10, 1, 2)   —>    (5, 4, 7, 10, 1, 2)   —>    Counter = 1

(5, 4, 7, 10, 1, 2)   —>    (4, 5, 7, 10, 1, 2)   —>    Counter = 2

 

Third Step:

(4, 5, 7, 10, 1, 2)   —>   Counter = 2

(4, 5, 7, 10, 1, 2)   —>    (4, 5, 7, 10, 1, 2)   —>   Counter = 3

 

Fourth Step:

(4, 5, 7, 10, 1, 2)   —>   Counter = 3

(4, 5, 7, 10, 1, 2)   —>   (4, 5, 7, 10, 1, 2)   —>    Counter = 4

 

Fifth Step:

(4, 5, 7, 10, 1, 2)   —>   Counter = 4

(4, 5, 7, 10, 1, 2)   —>   (4, 5, 7, 1, 10, 2)   —>    Counter = 3

(4, 5, 7, 1, 10, 2)   —>   (4, 5, 1, 7, 10, 2)   —>    Counter = 2

(4, 5, 1, 7, 10, 2)   —>   (4, 1, 5, 7, 10, 2)   —>     Counter = 1

(4, 1, 5, 7, 10, 2)   —>   (1, 4, 5, 7, 10, 2)    —>    Counter = 2

 

Sixth Step:

(1, 4, 5, 7, 10, 2)   —>    Counter = 2

(1, 4, 5, 7, 10, 2)   —>   (1, 4, 5, 7, 10, 2)   —>    Counter = 3

(1, 4, 5, 7, 10, 2)   —>   (1, 4, 5, 7, 10, 2)   —>    Counter = 4

(1, 4, 5, 7, 10, 2)   —>   (1, 4, 5, 7, 10, 2)   —>   Counter = 5

 

Seventh Step:

(1, 4, 5, 7, 10, 2)   —>    Counter = 5s

(1, 4, 5, 7, 10, 2)   —>   (1, 4, 5, 7, 2, 10)   —>   Counter = 4

(1, 4, 5, 7, 2, 10)   —>   (1, 4, 5, 2, 7, 10)   —>   Counter = 3

(1, 4, 5, 2, 7, 10)   —>   (1, 4, 2, 5, 7, 10)   —>   Counter = 2

(1, 4, 2, 5, 7, 10)   —>   (1, 2, 4, 5, 7, 10)   —>   Counter = 1

(1, 2, 4, 5, 7, 10)   —>   (1, 2, 4, 5, 7, 10)   —>    Counter = 2

 

The basic source code for Gnome Sort would be like this.

 

</p>
<p>void Gnome_Sort (int arr[], const int SIZE)</p>
<p>{</p>
<p>&nbsp; &nbsp; &nbsp;for (int i = 1 ; i &lt; SIZE; ++i) &nbsp; &nbsp; { &nbsp; &nbsp; &nbsp; &nbsp; if (arr [i] &gt;= arr[i-1])</p>
<p>&nbsp; &nbsp; &nbsp; &nbsp; {</p>
<p>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ++i ;</p>
<p>&nbsp; &nbsp; &nbsp; &nbsp; }</p>
<p>&nbsp; &nbsp; &nbsp; &nbsp; else</p>
<p>&nbsp; &nbsp; &nbsp; &nbsp; {</p>
<p>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; swap (arr[i], arr[i-1]) ;</p>
<p>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (i == 1)</p>
<p>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ++i ;</p>
<p>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else</p>
<p>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; --i ;</p>
<p>&nbsp; &nbsp; &nbsp; &nbsp; }</p>
<p>&nbsp; &nbsp; }</p>
<p>}</p>
<p>int main ()</p>
<p>{</p>
<p>&nbsp; &nbsp; const int SIZE = 6 ;</p>
<p>&nbsp; &nbsp; int arr [SIZE] = {5, 7, 4, 10, 1, 2} ;</p>
<p>&nbsp; &nbsp; Gnome_Sort (arr, SIZE) ;</p>
<p>}</p>
<p>

 

Gnome Sort is the sorting technique more close to human procedure of sorting a list, therefore it easier to comprehend. It is equally good as Insertion Sort but sometimes insertion sort is a better option. But wait! It could be improved as it is evident from the source code above. You could place some checks and conditions in between which make the Algorithm even better. Now it is up to you to try them out. Good Luck!

Tags: , , ,