Monday, September 29, 2025
HomeData Modelling & AIC++ Program for Gnome Sort

C++ Program for Gnome Sort

Algorithm Steps

  1. If you are at the start of the array then go to the right element (from arr[0] to arr[1]).
  2. 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++;
  1. 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--;
                       }
  1. Repeat steps 2) and 3) till ‘i’ reaches the end of the array (i.e- ‘n-1’)
  2. 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);
}


Output:

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!

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

RELATED ARTICLES

Most Popular

Dominic
32324 POSTS0 COMMENTS
Milvus
84 POSTS0 COMMENTS
Nango Kala
6695 POSTS0 COMMENTS
Nicole Veronica
11860 POSTS0 COMMENTS
Nokonwaba Nkukhwana
11918 POSTS0 COMMENTS
Shaida Kate Naidoo
6807 POSTS0 COMMENTS
Ted Musemwa
7073 POSTS0 COMMENTS
Thapelo Manthata
6763 POSTS0 COMMENTS
Umr Jansen
6771 POSTS0 COMMENTS