Gnome sort en Python — el algoritmo del paseo (con animación)

Gnome sort es uno de los algoritmos más curiosos de la familia. La idea es absurdamente simple: imagina un gnomo de jardín ordenando una fila de macetas. Si las dos que tiene delante están bien, da un paso adelante. Si están mal, las intercambia y da un paso atrás. Y repite. Cuando llega al final sin hacer intercambios, el jardín está ordenado.

Es didácticamente brillante porque captura la esencia de la ordenación con una sola regla — sin bucles anidados, sin variables auxiliares, sin nada. Lo inventó Hamid Sarbazi-Azad en 2000, originalmente llamándolo “stupid sort” (que ya estaba pillado por otro algoritmo), y luego lo rebautizó como gnome sort cuando alguien le señaló que se parecía mucho a cómo un gnomo de jardín ordenaría flores.

¿Lo bueno? Es el algoritmo más fácil de programar de memoria: un solo bucle, una condición. ¿Lo malo? Sigue siendo O(n²) en el peor caso. Nadie lo usa en producción. Pero como pieza didáctica es oro.

Si quieres el panorama de los 14 algoritmos del clúster: Algoritmos de ordenación en Python — los 14 explicados.

Gnome sort en una frase

Mantén un índice i. Si i == 0 o arr[i-1] <= arr[i], avanza (i += 1). Si no, intercambia y retrocede (i -= 1). Termina cuando i llega al final.

Animación sobre 12 valores:

Antes de seguir: qué quieren decir O, Θ y Ω

En las tablas verás los tres símbolos. Idea rápida:

• O(n²) — cota superior (peor caso).
• Ω(n) — cota inferior (mejor caso): lista ya ordenada → un paseo de ida sin retrocesos.
• Θ(n²) — caso típico.

Gnome sort es Ω(n) (mejor caso), Θ(n²) (caso medio) y O(n²) (peor caso). Esencialmente la misma familia que insertion. Explicación más larga en el pilar del clúster.

Cómo funciona — traza paso a paso

Ordenamos [3, 1, 2] (n=3) a mano.

estado: [3, 1, 2]   i = 0
- i == 0 → avanza   → i = 1

estado: [3, 1, 2]   i = 1
- ¿arr[0]=3 > arr[1]=1? Sí → intercambia → [1, 3, 2]
- retrocede → i = 0

estado: [1, 3, 2]   i = 0
- i == 0 → avanza   → i = 1

estado: [1, 3, 2]   i = 1
- ¿arr[0]=1 > arr[1]=3? No → avanza → i = 2

estado: [1, 3, 2]   i = 2
- ¿arr[1]=3 > arr[2]=2? Sí → intercambia → [1, 2, 3]
- retrocede → i = 1

estado: [1, 2, 3]   i = 1
- ¿arr[0]=1 > arr[1]=2? No → avanza → i = 2

estado: [1, 2, 3]   i = 2
- ¿arr[1]=2 > arr[2]=3? No → avanza → i = 3

i == n → fin. Lista ordenada.

Total: 5 comparaciones y 2 intercambios para 3 elementos. Cada intercambio te hace “retroceder” como si hubieras visto al gnomo bajar una flor.

La idea profunda: gnome sort es insertion sort sin acumulador. Insertion mete el elemento actual en un bucle interno hasta su sitio; gnome lo hace con un solo bucle, retrocediendo de uno en uno hasta que la lista a la izquierda quede bien.

Implementación en Python

def ordenar(lista: list[int]) -> list[int]:
    n = len(lista)
    i = 0
    while i < n:
        if i == 0 or lista[i - 1] <= lista[i]:
            i += 1
        else:
            lista[i - 1], lista[i] = lista[i], lista[i - 1]
            i -= 1
    return lista


if __name__ == "__main__":
    print(ordenar([3, 1, 2]))  # [1, 2, 3]

Esta es la implementación entera. 8 líneas. No hay bucle anidado, no hay índices auxiliares. Por eso es ideal para enseñar la idea de ordenación a alguien que viene de cero.

En entrevistas, gnome sort es una respuesta válida a “implementa un sort sencillo de cabeza”. Demuestras que dominas la idea de la ordenación con la mínima maquinaria.

Implementación en JavaScript

function ordenar(lista) {
  let i = 0;
  while (i < lista.length) {
    if (i === 0 || lista[i - 1] <= lista[i]) {
      i++;
    } else {
      [lista[i - 1], lista[i]] = [lista[i], lista[i - 1]];
      i--;
    }
  }
  return lista;
}

Implementación en Java

public static void ordenar(int[] lista) {
    int i = 0;
    while (i < lista.length) {
        if (i == 0 || lista[i - 1] <= lista[i]) {
            i++;
        } else {
            int tmp = lista[i - 1]; lista[i - 1] = lista[i]; lista[i] = tmp;
            i--;
        }
    }
}

Complejidad — primo de insertion

Métrica	Mejor caso	Caso medio	Peor caso
Tiempo	Ω(n)	Θ(n²)	O(n²)
Memoria	O(1)	O(1)	O(1)
Estable	Sí	Sí	Sí

Por qué es estable. La condición lista[i - 1] <= lista[i] (con <=, no <) evita el intercambio cuando son iguales. Mantiene el orden relativo.

Comparado con insertion sort (su pariente cercano): gnome hace exactamente las mismas comparaciones e intercambios que la versión por intercambios de insertion. La diferencia es solo el “estilo”: gnome usa un puntero que sube y baja; insertion usa un bucle interno explícito.

Ver en acción — gnome sort sobre 10 listas fijas

Todo el clúster usa las mismas 10 listas fijas (n=15):

#	Nombre	Qué es
1	ordenada	1, 2, 3, ..., 15
2	inversa	15, 14, ..., 1
3	casi_ordenada	1..15 con un par de swaps
4	muy_desordenada	Patrón min-max alternado
5	duplicados	Enteros del rango [1..5] repetidos
6-10	aleatoria_s1 .. aleatoria_s5	5 permutaciones aleatorias deterministas

Aplicamos gnome sort:

from sortlab import bench_estandar, formato_tabla
print(formato_tabla(bench_estandar("gnome", n=15)))

Salida real:

Lista            Comp.  Interc.  Escr.  Tiempo (ms)   Caso  Θ observada
---------------  -----  -------  -----  -----------  -----  -----------
ordenada         14           0      0        0.001  Mejor         Θ(n)
inversa          210        105    210        0.027   Peor        Θ(n²)
casi_ordenada    48          17     34        0.006  Mejor   Θ(n log n)
muy_desordenada  112         49     98        0.014  Medio        Θ(n²)
duplicados       92          39     78        0.011  Medio        Θ(n²)
aleatoria_s1     136         62    124        0.017  Medio        Θ(n²)
aleatoria_s2     118         54    108        0.014  Medio        Θ(n²)
aleatoria_s3     135         62    124        0.016  Medio        Θ(n²)
aleatoria_s4     150         69    138        0.018  Medio        Θ(n²)
aleatoria_s5     112         50    100        0.013  Medio        Θ(n²)

Lectura de la tabla:

• ordenada → 14 comparaciones, Mejor + Θ(n). El gnomo pasea de izquierda a derecha sin retroceder ni una vez. Es Ω(n) exacto: n-1 = 14 comparaciones.
• inversa → 210 comparaciones, Peor + Θ(n²). Cada elemento tiene que retroceder hasta el principio. Es n*(n-1) = 210 (literalmente el doble del peor caso de bubble/insertion porque gnome cuenta cada comparación del retroceso). El sello del peor caso.
• casi_ordenada → 48 comparaciones, Mejor. Como insertion, gnome aprovecha que la lista está cerca de ordenada: solo retrocede sobre los pocos elementos descolocados.
• Aleatorias → 112-150 comparaciones. El caso medio: cada elemento retrocede en promedio una pequeña distancia.

Compara con insertion sort:

Lista	Insertion (comp.)	Gnome (comp.)
ordenada	14	14
inversa	105	210
aleatoria_s1	74	136

Gnome hace el doble de comparaciones que insertion en aleatorias e inversa. ¿Por qué? Porque cada retroceso del gnomo vuelve a comparar la misma pareja una vez más para confirmar que ya está bien antes de subir el puntero. Insertion (versión con shifts) evita esa doble comparación con un bucle interno.

Es la lección honesta: gnome es elegante pero ineficiente. Insertion es ligeramente más complicado pero hace literalmente la mitad del trabajo en escenarios reales.

Reproducirlo sin instalar nada

sortlab vive privada en el Python profesional: medir, optimizar y escalar. Versión instrumentada inline:

def gnome_medido(lista_original: list[int]) -> dict:
    arr = list(lista_original)
    comparaciones = 0
    intercambios = 0
    i = 0
    while i < len(arr):
        if i == 0:
            i += 1
            continue
        comparaciones += 1
        if arr[i - 1] <= arr[i]:
            i += 1
        else:
            arr[i - 1], arr[i] = arr[i], arr[i - 1]
            intercambios += 1
            i -= 1
    return {"ordenada": arr, "comparaciones": comparaciones, "intercambios": intercambios}


listas = {
    "ordenada":         list(range(1, 16)),
    "inversa":          list(range(15, 0, -1)),
    "casi_ordenada":    [1, 11, 3, 4, 5, 6, 7, 8, 9, 10, 2, 12, 13, 14, 15],
    "muy_desordenada":  [1, 15, 2, 14, 3, 13, 4, 12, 5, 11, 6, 10, 7, 9, 8],
    "duplicados":       [1, 1, 3, 2, 2, 2, 1, 5, 1, 5, 4, 1, 1, 1, 2],
}
for nombre, lista in listas.items():
    r = gnome_medido(lista)
    print(f"{nombre:<16}  comp={r['comparaciones']:>3}  swap={r['intercambios']:>3}")

Cuándo usar gnome sort

Sí:

• Para enseñar la idea de ordenación a alguien que viene de cero. 8 líneas, una condición, un puntero. Imposible más simple.
• Para entrevistas donde te piden “implementa un sort de cabeza”. Lo escribes en 30 segundos sin dudar.

No:

• Nada de producción. Sigue siendo O(n²) y, encima, peor que insertion en cifras reales por la doble comparación.

Comparativa rápida

Algoritmo	Mejor	Peor	Memoria	Estable	Simplicidad
Bubble	Ω(n)	O(n²)	O(1)	Sí	Trivial
Insertion	Ω(n)	O(n²)	O(1)	Sí	Sencillo
Gnome	Ω(n)	O(n²)	O(1)	Sí	El más simple posible
Selection	Ω(n²)	O(n²)	O(1)	No	Sencillo

El nicho de gnome es la simplicidad pura. Si tu único requisito es “implementa un sort que se entienda en 30 segundos”, gnome es la respuesta. Para cualquier otra cosa, hay alternativas mejores.

Mitos que circulan sobre gnome sort

• “Es más simple que bubble.” Discutible. Tiene menos código que bubble (una sola condición), pero requiere entender que el puntero “baja”. Bubble tiene dos bucles anidados pero la idea es más directa.
• “Es más lento que bubble.” En cifras, hace aproximadamente el doble de comparaciones que insertion. Bubble está en el medio.
• “Es estable.” Sí, con la condición <= estricta. Solo si la implementas correctamente con lista[i-1] <= lista[i] (no <).

¿Y en la stdlib de Python?

No. Nunca lo verás en ninguna stdlib. Es pedagogía pura.

Trivia algorítmica

Hamid Sarbazi-Azad lo llamó originalmente “stupid sort” (“ordenación tonta”) por su simplicidad absurda. Cuando se dio cuenta de que ese nombre ya estaba ocupado por otro algoritmo, lo rebautizó como “gnome sort” por sugerencia de un colega que apuntó la similitud con cómo un gnomo de jardín ordenaría macetas: paseando, retrocediendo cuando ve algo descolocado. El nombre ha cuajado.

FAQ rápida

¿Es lo mismo que insertion sort?
Conceptualmente sí (haces lo mismo). La diferencia es la implementación: gnome usa un puntero que sube y baja; insertion usa un bucle interno explícito. Insertion hace literalmente menos operaciones porque no re-compara al volver a subir.

¿Por qué se llama “gnome”?
Por la analogía: un gnomo de jardín ordenando macetas. Avanza si están bien; retrocede si están mal. Idea de Hamid Sarbazi-Azad en 2000.

¿Es estable?
Sí, con la condición <= estricta.

¿Sirve para algo útil?
Para enseñar. Para producción, casi nunca. Si necesitas algo simple, usa insertion sort.

En resumen

Gnome sort es insertion sort llevado a su mínima expresión: un puntero, una condición, un solo bucle. Su valor es didáctico, no productivo. Sirve para enseñar la esencia de la ordenación a alguien que viene de cero: ordenar es “comparar dos vecinos y mover si están mal, repetir hasta que todo esté bien”. 8 líneas. Imposible más simple. En la práctica, insertion lo bate. Pero la lección de simplicidad sigue siendo única.

Si quieres aprender cómo simplificar tu código sin sacrificar claridad —el verdadero arte de la programación— ese es el camino del curso de El Pythonista.