Algorithm Steps
- If you are at the start of the array then go to the right element (from arr[0] to arr[1]).
- 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++;
- 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--; }
- Repeat steps 2) and 3) till ‘i’ reaches the end of the array (i.e- ‘n-1’)
- If the end of the array is reached then stop and the array is sorted.
CPP
// A C++ Program to implement Gnome Sort #include <iostream> using namespace std; Â
// A function to sort the algorithm using gnome sort void gnomeSort( int arr[], int n) { Â int index = 0; Â
 while (index < n) {   if (index == 0)    index++;   if (arr[index] >= arr[index - 1])    index++;   else {    swap(arr[index], arr[index - 1]);    index--;   }  }  return ; } Â
// A utility function ot print an array of size n void printArray( int arr[], int n) { Â cout << "Sorted sequence after Gnome sort: " ; Â for ( int i = 0; i < n; i++) Â Â cout << arr[i] << " " ; Â cout << "\n" ; } Â
// Driver program to test above functions. int main() { Â int arr[] = { 34, 2, 10, -9 }; Â int n = sizeof (arr) / sizeof (arr[0]); Â
 gnomeSort(arr, n);  printArray(arr, n); Â
 return (0); } |
Sorted sequence after Gnome sort: -9 2 10 34
Time Complexity: O(n2). As there is 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) as the variable ‘index’ in the program doesn’t always get incremented, it gets decremented too.Â
Auxiliary Space: O(1)
Please refer complete article on Gnome Sort for more details!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!