Programa C++ para Gnome Sort

Pasos del algoritmo

1. Si está al comienzo de la array, vaya al elemento correcto (de arr[0] a arr[1]).
2. Si el elemento de array actual es más grande o igual que el elemento de array anterior, vaya un paso a la derecha

                   if (arr[i] >= arr[i-1])
                      i++;

1. Si el elemento de array actual es más pequeño que el elemento de array anterior, intercambie estos dos elementos y retroceda un paso

                       if (arr[i] < arr[i-1])
                       {
                           swap(arr[i], arr[i-1]);
                           i--;
                       }

1. Repita los pasos 2) y 3) hasta que ‘i’ llegue al final de la array (es decir, ‘n-1’)
2. Si se llega al final de la array, se detiene y se ordena la array.

// 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

Complejidad Temporal: O(n ² ). Como no hay un bucle anidado (solo un tiempo), puede parecer que se trata de un algoritmo de tiempo lineal O (n). Pero la complejidad del tiempo es O (n ^ 2) ya que la variable ‘índice’ en el programa no siempre se incrementa, también se reduce. 
Espacio Auxiliar: O(1)

¡ Consulte el artículo completo sobre Gnome Sort para obtener más detalles!