Programa Python para Gnome Sort

Pasos del algoritmo:

• Si está al comienzo de la array, vaya al elemento correcto (de arr[0] a arr[1]).
• 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++;

• 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--;
                       }

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

# Python program to implement Gnome Sort
 
# A function to sort the given list using Gnome sort
def gnomeSort( arr, n):
    index = 0
    while index < n:
        if index == 0:
            index = index + 1
        if arr[index] >= arr[index - 1]:
            index = index + 1
        else:
            arr[index], arr[index-1] = arr[index-1], arr[index]
            index = index - 1
 
    return arr
 
# Driver Code
arr = [ 34, 2, 10, -9]
n = len(arr)
 
arr = gnomeSort(arr, n)
print "Sorted sequence after applying Gnome Sort :",
for i in arr:
    print i,
 
# Contributed By Harshit Agrawal

Sorted sequence after applying Gnome Sort : -9 2 10 34

Complejidad temporal: O(n ² )

Espacio auxiliar: O (1) ¡
Consulte el artículo completo sobre Gnome Sort para obtener más detalles!