Gnome sort is an extremely simple sorting algorithm, very similar to insertion sort. Also, it is another comparison and exchange sort. You could say that it looks like bubble sort, and you would be right.
How it works:
In gnome sort, two adjacent elements are compared, and if they are in the wrong order, they are swapped. The comparison continues with the next element, and the same condition is checked, but the order is wrong, a swap takes place, and after the swap, the lower element is now compared to the previous element and if they are not in order, another swap takes place. Then, it continues with the comparison where it left off, after the swap, the highest element so far is compared to next, swapped if necessary and so on. Let us take a look at a example for you to understand.
Step by step example :
Having the following list, let’s try to use comb sort to arrange the numbers from lowest to greatest:
Unsorted list: 33, 98, 74, 13, 55, 20
The first step, the first two elements are compared:
33, 98, 74, 13, 55, 20
They are in the proper order, so we can go ahead with the next comparison:
33, 98, 74, 13, 55, 20
Now, the order is wrong, so the elements must swap:
33, 74, 98, 13, 55, 20
After the swap has taken place, we must compare 74 with the previous element :
33, 74, 98, 13, 55, 20
They seem to be in the proper order, so we continue from where we left off, with the head of the list 98:
33, 74, 98, 13, 55, 20
A swap is required for the elements to be in proper order:
33, 74, 13, 98, 55, 20
Now the element must percolate down, and be compared to the previous elements:
33, 74, 13, 98, 55, 20
The elements swap:
33, 13, 74, 98, 55, 20
There is one more element for 13 to be compared to:
33, 13, 74, 98, 55, 20
And again a swap is required:
13, 33, 74, 98,55, 20
We continue from where we left off, with 98, and it has to be compared to 55. The algorithm ends when there are no more elements to be compared to.
Sample code:
#include < iostream >using namespace std;
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;
}}}int main()
{int n;
int *a;
cout << "Please insert the number of elements to be sorted: ";
cin >> n; // The total number of elements
a = (int *)calloc(n, sizeof(int));
for(int i=0;i< n;i++)
{cout << "Input " << i << " element: ";
cin >>a[i]; // Adding the elements to the array
}cout << "Unsorted list:" << endl; // Displaying the unsorted array
for(int i=0;i< n;i++)
{cout << a[i] << " ";
}gnomeSort(n, a);
cout << "nSorted list:" << endl; // Display the sorted array
for(int i=0;i < n;i++)
{cout << a[i] << " ";
}return 0;
}
Output:
Code explanation:
The gnomesort method takes care of the sorting. The algorithm passes through the array, and checks for order between the elements, and if they are in the wrong order, they are swapped.
Complexity:
This is not a very efficient algorithm. It’s time and space complexity is exactly that of the Bubble Sort. That is, the time complexity is O(n^2), and space complexity for in-place sorting is O(1).
Advantages:
- is a very simple algorithm to learn;
Disadvantages:
- the complexity is O(n^2);
- not good on large data sets;
Conclusion:
Gnome sort is a simple algorithm, best suited for those who want to learn sorting and are at the beginning of algorithms.
