Gnome Sort is brand new to the family.
The girlfriend of Pigeonhole Sort and a hopeless romantic, she is eager to meet his parents and siblings and make good impressions on them. She can't wait for a chance to show off the bounty of her vegetable garden, and has brought squash, carrots, and fresh spinach to the reunion in the hopes of impressing her (maybe, potentially, hopefully) soon-to-be in-laws.
She might be out of luck, though. Pigeon has done this before, and the girlfriends he brings to the reunion aren't seen at the next one. Nevertheless, Gnome Sort hopes her gifts of food and joy help tell Pigeon's family that maybe she really is the real deal.
Even if she isn't, the family figures, they still get free fresh veggies. That's a good deal.
The Rundown
- Created By: Hamid Sarbazi-Azad (2000)
- Type: Exchange
- Stable? Yes
- Average-Case: O(n2)
- Worst-Case: O(n2)
- Space Complexity: O(1)
- Sample Project: Over on GitHub
exceptionnotfound
Algorithm
- START at the beginning of the array.
- IF the pot at the current position and next-highest pot are in the correct order, go to next position.
- ELSE if they are not in order, SWAP them.
- GO TO 2, CONTINUE UNTIL all pots are sorted.
Visualization
The nice thing about this visualization is that it makes it obvious what the "gnome" is doing. It also makes it very clear that this is a terribly inefficient algorithm.
The part that the visualization is skipping is that when a number is place into it's final sorted position, the "gnome" needs to step back up the sorted items to find the next unsorted item. Even if it does this quickly, it's doing many more accesses than other algorithms.
This one also has an "audibilization"; it sounded kind of like a police siren on speed to me. What do you think?
C# Implementation
class GnomeSort
{
static void Sort(int[] arr, int length)
{
int index = 0;
while (index < length)
{ //If there is no pot next to the gnome, he is done.
if (index == 0) //If the gnome is at the start of the line...
{
index++;//he steps forward
}
//If the pots next to the gnome are in the correct order...
if (arr[index] >= arr[index - 1])
{
index++;//he goes to the next pot
}
else //If the pots are in the wrong order, he switches them.
{
int temp = 0;
temp = arr[index];
arr[index] = arr[index - 1];
arr[index - 1] = temp;
index--;
}
}
return;
}
public static void Main()
{
int[] array = { 84, 61, 15, 2, 7, 55, 19, 40, 78, 33 };
CommonFunctions.PrintInitial(array);
Sort(array, array.Length);
CommonFunctions.PrintFinal(array);
Console.ReadKey();
}
}Time and Space Complexity
The worst case for this algorithm (being the case we care about for real-world applications) is abysmal: O(n2). This is the same worst case as Bubble Sort, another poorly-performing sorting algorithm. Even with a constance O(1) space complexity, gnome sort doesn't really have anything in favor of using it. Then again, it wasn't designed to be a good algorithm.
Where this algorithm shines is in teaching. I'd be willing to bet that many of you, dear readers, have done this kind of sorting in real life, such as when organizing books or DVDs. It's not efficient, true, but it's simple to understand and implement, and therein lies Gnome Sort's true value.
Summary
Gnome Sort is a poor-performing algorithm, but one whose value lies in teaching, not in performance: it is a good example of what not to do. Her veggies are delicious, though, and the family hopes she sticks around, if for no other reason than to get those scrumptious greens.
The chillest dude on the block, Radix Sort, is next. At least, that's what he wants you to think.
Matthew Jones
Don't forget to check out the sample project over on GitHub!
Happy Coding!
