Introduction:
This is a tutorial on the sorting algorithm “Gnome Sort”, not quite one of the best known algorithms by any means but that certainly does not take away some of the valuable innovation and strategy that was used to create this algorithm. I think you’ll find this sorting algorithm to be quite interesting and useful in certain contexts within your programming career. So sit back, relax, grab your favorite lawn gnome, and enjoy the world that is Gnome Sort:
What is Gnome Sort?:
What is Gnome Sort indeed, the more sorting algorithms you tend to encounter the more you wonder what these people were smoking when the came up with the names. All of them however have logical reasons for utilizing the names they are given. Gnome Sort is no different in this case allow me to take a quote directly from the creator of the Gnome Sort algorithm, Dick Grune:
QUOTE
“Gnome Sort is based on the technique used by the standard Dutch Garden Gnome (Du.: tuinkabouter). Here is how a garden gnome sorts a line of flower pots. Basically, 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. Boundary conditions: if there is no previous pot, he steps forwards; if there is no pot next to him, he is done.”
Ok so the creator of this algorithm isn’t completely insane, there is some rhyme to his reason here. In fact on further inspection of what Gnome Sort actually is through the quote above, we see that it is more or less a combination of Insertion Sort (Check out my tutorial for more information) and Bubble Sort. The closer and closer we look at this the more it tends to make sense. Well alright now that we have a fairly broad idea as to what Gnome Sort is let us take a look at what the algorithm entails.
The Algorithm:
The quote from Dick Grune gives a straightforward algorithm that is used here in Gnome Sort. The flower pots would be the data items stored in the positions of the array, and the Gnome would be the if and else statements, and any loops within the code, making the decisions to swap or not to swap. A visual example on a test case of integers will be given now to help drive the point of what Gnome Sort is really all about (Aside from stealing underpants i.e. underpants gnomes).
Let us assume we have a list of integers (or flower pots, underpants, etc.):
-- 0 1 2 3
[ 6 0 9 5 ]
Put yourself in the mental mindset of a lawn gnome….Yes I know enthralling is it not? Look upon these numbers here, and notice that the variable “i” is made to be incremented to 1 and the “j” variable is incremented to be 2. These are the initial states of the “i” and “j” values.
-- 0 1 2 3
[ 6 0 9 5 ]
Our lawn gnome intuition has forced us to progress through the flower pots and we end up with “i” incremented to 2 and “j” incremented to 3.
-- 0 1 2 3
[ 6 0 9 5 ]
Finally a job fit only for that of a lawn gnome, position [1] and position [2] are swapped as well as their respective elements held at those positions. At this point “i” is decremented to 1 but “j” stays at the value of 3.
-- 0 1 2 3
[ 6 9 0 5 ]
As we can see here, the elements from position [0] have been switched with that of position [1]. “i” is now 1 and “j” is still holding it down at 3:
-- 0 1 2 3
[ 9 6 0 5 ]
No violations so no swaps here, however we still have to move the “i” and “j” variables, so “i” is now incremented to 3 and “j” is 4:
-- 0 1 2 3
[ 9 6 0 5 ]
A swap for is no needed from position [3] and [2], and as to be expected “i” is decremented to 2 and “j” is 4:
-- 0 1 2 3
[ 9 6 5 0 ]
No swaps here, however “i” is now incremented to 3 and “j” is 5.
-- 0 1 2 3
[ 9 6 5 0 ]
As stated above the algorithm on the next pass “i” will be over 4, it must be less than 4 for it to continue. Thus the algorithm exits. This a basic run down of what happens in the code of Gnome Sort. What I provide next is a snippet of Gnome Sort in the code section.
The Code
Gnome Sort routine:
cpp
//gnomeSort Function
void gnomeSort(int elements, int arr[])
{
int i = 0, temp;
while( i < elements ){
if ( i == 0 || arr [i - 1] <= arr[i] )
i++;
else{
temp = arr[i];
arr[i] = arr[i - 1];
arr[--i] = temp;
}//end else
}//end while
}//end GnomeSort Function
For all the explanation that was required in the algorithm section, this sure is not a lot of code. That’s really the shining point of the algorithm is that when you fully understand the concept, the code is surprisingly easy to implement and put on paper. Of course however, shorter code does not mean faster running time, this is usually the converse. Never the less a bit of simplicity never hurt anybody.
Analysis && Conclusion
As we have found out, Gnome Sort can be a nice little trick to add to your arsenal. It combines aspects of both Bubble Sort and Insertion Sort with a bit of spice. It is probably one of the simplest sorts to implement code-wise due to its short length. So what is the running time of this algorithm? Overall this algorithm has a running time of O(N*N) or O(N)(squared), mainly because regardless of the scenario it must first traverse and swap if necessary.
, could you add the colors once again to the examples?