Programa Java 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.

// Java Program to implement Gnome Sort
 
import java.util.Arrays;
public class GFG {
 static void gnomeSort(int arr[], int n)
 {
  int index = 0;
 
  while (index < n) {
   if (index == 0)
    index++;
   if (arr[index] >= arr[index - 1])
    index++;
   else {
    int temp = 0;
    temp = arr[index];
    arr[index] = arr[index - 1];
    arr[index - 1] = temp;
    index--;
   }
  }
  return;
 }
 
 // Driver program to test above functions.
 public static void main(String[] args)
 {
  int arr[] = { 34, 2, 10, -9 };
 
  gnomeSort(arr, arr.length);
 
  System.out.print("Sorted sequence after applying Gnome sort: ");
  System.out.println(Arrays.toString(arr));
 }
}
 
// Code Contributed by Mohit Gupta_OMG

Sorted sequence after applying 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(n)

Para comprender Arrays.toString() , consulte: https://www.geeksforgeeks.org/arrays-tostring-in-java-with-examples/ Consulte el artículo completo sobre Gnome Sort para obtener más detalles.