Bogo sort en Python — el peor algoritmo de la historia (y por qué importa)

Bogo sort es el chiste de la informática. La idea: baraja la lista al azar, comprueba si por casualidad ha quedado ordenada, y si no, vuelve a barajar. Y otra vez. Y otra. Hasta que la suerte te sonría.

Es el peor algoritmo de ordenación que existe (en su versión “honesta”, la que no está diseñada para ser peor a propósito). Para n elementos, tarda en promedio n factorial intentos en encontrar la permutación correcta. Para n=15, eso son mil trescientos billones de intentos. Para n=20, no habría tiempo suficiente ni con todos los ordenadores del planeta combinados desde el Big Bang hasta hoy.

Pero bogo sort tiene una razón de ser: te enseña a entender qué significa el orden de magnitud de un algoritmo. Cuando ves la palabra “factorial” en una complejidad, tienes que entrar en pánico. Bogo lo demuestra en cifras crudas.

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

Bogo sort en una frase

while not ordenada: barajar(). Confiar.

Animación sobre 6 valores (con n=15 tardaría siglos):

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

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

• O(∞) — cota superior: en el peor caso, NO TERMINA. Si la suerte siempre te traiciona, la lista nunca se ordena. Teóricamente, ese es el peor caso.
• Ω(n) — cota inferior (mejor caso): la lista ya está ordenada de salida → una sola comprobación y termina.
• Θ(n · n!) — caso típico: en promedio, se prueban n!/2 permutaciones y por cada una se hace una comprobación O(n).

Bogo es el único algoritmo del clúster con caso medio factorial. Eso ya te dice todo. Explicación más larga en el pilar del clúster.

Cómo funciona — traza paso a paso

Ordenamos [3, 1, 2] (n=3, 3! = 6 permutaciones posibles).

Intento 1: barajamos → [2, 3, 1]. ¿Ordenada? No. (2 < 3 sí, pero 3 > 1).
Intento 2: barajamos → [1, 3, 2]. ¿Ordenada? No (3 > 2).
Intento 3: barajamos → [3, 2, 1]. ¿Ordenada? No (3 > 2).
Intento 4: barajamos → [2, 1, 3]. ¿Ordenada? No (2 > 1).
Intento 5: barajamos → [1, 2, 3]. ¿Ordenada? Sí. Fin.

5 intentos para n=3. En promedio habría sido 3 intentos (3! / 2 = 3). Pero “promedio” no significa “siempre”.

Para n=10, el promedio sube a 10! / 2 = 1.814.400. Para n=15, 15! / 2 ≈ 6 · 10¹¹. Para n=20, 20! / 2 ≈ 1,2 · 10¹⁸. Cifras absurdas.

Implementación en Python

import random


def ordenar(lista: list[int]) -> list[int]:
    while not _esta_ordenada(lista):
        random.shuffle(lista)
    return lista


def _esta_ordenada(lista: list[int]) -> bool:
    return all(lista[i] <= lista[i + 1] for i in range(len(lista) - 1))


if __name__ == "__main__":
    # Importante: usa con listas MUY pequeñas (n <= 8).
    print(ordenar([3, 1, 2]))  # [1, 2, 3]

Una observación importante: en una implementación seria conviene poner un límite de intentos para que no se cuelgue. Algo como:

def ordenar_con_limite(lista: list[int], max_intentos: int = 1_000_000) -> list[int]:
    intentos = 0
    while not _esta_ordenada(lista):
        if intentos >= max_intentos:
            raise RuntimeError(
                f"bogo se rindió tras {max_intentos} intentos. "
                f"Para n>10 esto es esperable: prueba otro algoritmo."
            )
        random.shuffle(lista)
        intentos += 1
    return lista

Implementación en JavaScript

function ordenar(lista) {
  while (!estaOrdenada(lista)) {
    shuffle(lista);
  }
  return lista;
}

function estaOrdenada(lista) {
  return lista.every((v, i) => i === 0 || lista[i - 1] <= v);
}

function shuffle(lista) {
  for (let i = lista.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [lista[i], lista[j]] = [lista[j], lista[i]];
  }
}

Implementación en Java

import java.util.Random;

public static void ordenar(int[] lista) {
    Random rng = new Random();
    while (!estaOrdenada(lista)) {
        shuffle(lista, rng);
    }
}

private static boolean estaOrdenada(int[] lista) {
    for (int i = 1; i < lista.length; i++) {
        if (lista[i - 1] > lista[i]) return false;
    }
    return true;
}

private static void shuffle(int[] lista, Random rng) {
    for (int i = lista.length - 1; i > 0; i--) {
        int j = rng.nextInt(i + 1);
        int tmp = lista[i]; lista[i] = lista[j]; lista[j] = tmp;
    }
}

Complejidad — “factorial” en cifras

Métrica	Mejor caso	Caso medio	Peor caso
Tiempo	Ω(n)	Θ(n · n!)	O(∞)
Memoria	O(1)	O(1)	O(1)
Estable	No	No	No

Por qué Θ(n · n!) en caso medio. Hay n! permutaciones posibles. Como elegimos al azar, en promedio probamos n!/2 antes de acertar. Por cada intento, comprobar “está ordenada” es O(n). Total: n · n!/2 = Θ(n · n!).

Por qué O(∞) en peor caso. Si la suerte siempre te traiciona y nunca te toca la permutación correcta, no termina nunca. Teóricamente, con un PRNG mal sembrado podría dar vueltas infinitas.

Cuántos intentos en cifras:

n	n!	n!/2
5	120	60
8	40.320	20.160
10	3.628.800	1.814.400
12	479 millones	240 millones
15	1.307 mil millones	654 mil millones
20	2.4 · 10¹⁸	1.2 · 10¹⁸

Para n=20, si tu ordenador hiciera mil millones de intentos por segundo, tardarías 38 AÑOS en ordenar. Para n=25, no llegarías a verlo nunca.

Ver en acción — bogo sort sobre las 10 listas (n=6, por necesidad)

Todo el clúster usa las mismas 10 listas fijas, pero para bogo bajamos a n=6 (6! = 720 permutaciones, manejable). Con n=15 no terminaría.

from sortlab import bench_estandar, formato_tabla
print(formato_tabla(bench_estandar("bogo", n=6)))

Salida real (n=6, semilla del shuffle fija para reproducibilidad):

Lista            Comp.  Interc.    Escr.  Tiempo (ms)       Caso  Θ observada
---------------  -----  -------  -------  -----------  ---------  -----------
ordenada         0            0        0        0.008  Aleatorio         Θ(n)
inversa          0            0  504.096       84.856  Aleatorio      Θ(n·n!)
casi_ordenada    0            0  649.952      110.606  Aleatorio      Θ(n·n!)
muy_desordenada  0            0    4.472        0.749  Aleatorio      Θ(n·n!)
duplicados       0            0       32        0.014  Aleatorio      Θ(n·n!)
aleatoria_s1     0            0   20.904        3.472  Aleatorio      Θ(n·n!)
aleatoria_s2     0            0   63.024       10.553  Aleatorio      Θ(n·n!)
aleatoria_s3     0            0  806.912      135.815  Aleatorio      Θ(n·n!)
aleatoria_s4     0            0   30.784        5.157  Aleatorio      Θ(n·n!)
aleatoria_s5     0            0  151.384       25.568  Aleatorio      Θ(n·n!)

Lectura de la tabla:

• Comp. = 0 en todas las filas. Bogo NO compara dos elementos: solo comprueba si la lista entera está ordenada después de cada barajado. La librería cuenta cero “comparaciones de algoritmo” porque las que hace son verificaciones globales.
• Escrituras varía DRAMÁTICAMENTE: desde 32 (suerte enorme con duplicados — uno de los pocos casos en los que el shuffle cae bien rápido) hasta 806.912 (aleatoria_s3, mala racha extrema). En casi_ordenada mide 649.952 escrituras — sí, mucho peor que muchas aleatorias, porque a bogo le da igual lo “casi” que estés: si no está, vuelta a barajar.
• ordenada → 0 escrituras: bogo comprueba al inicio, ve que ya está ordenada, y sale sin barajar ni una vez. Es el único caso predecible.
• El tiempo va de 8 microsegundos a 136 milisegundos según la suerte. Es una variabilidad de cuatro órdenes de magnitud sobre el mismo n. Es exactamente lo que hace bogo imposible de usar: no es que sea lento de media, es que es imposible de predecir.

El campo Caso siempre dice Aleatorio porque bogo no tiene un caso medio determinista. Cada ejecución es lotería.

¿Y si subimos a n=10? (no lo hagas en producción)

Probemos n=10 una vez con el shuffle determinista:

from sortlab import medir, generar
lista = generar("aleatoria_s1", 10)
r = medir("bogo", lista, mediciones_tiempo=1)
print(f"escrituras: {r.escrituras}, tiempo: {r.tiempo_ms:.0f} ms")

Resultado típico: entre 0,5 y 5 segundos, con escrituras del orden de millones. Para n=12, hablamos de minutos. Para n=15, horas. Para n=20, no llega a verse el final.

Reproducirlo sin instalar nada

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

import random


def bogo_medido(lista_original: list[int], max_intentos: int = 200_000) -> dict:
    arr = list(lista_original)
    intentos = 0
    escrituras = 0

    def ordenada() -> bool:
        return all(arr[i] <= arr[i + 1] for i in range(len(arr) - 1))

    while not ordenada():
        if intentos >= max_intentos:
            return {
                "ordenada": arr,
                "intentos": intentos,
                "escrituras": escrituras,
                "se_rindio": True,
            }
        random.shuffle(arr)
        escrituras += len(arr)
        intentos += 1
    return {
        "ordenada": arr,
        "intentos": intentos,
        "escrituras": escrituras,
        "se_rindio": False,
    }


# Hazlo con n=6 (720 permutaciones, manejable). Con n=10 ya tarda
# segundos. Con n=15 no termina en horas.
import random
random.seed(42)
listas = {
    "ordenada":  [1, 2, 3, 4, 5, 6],
    "inversa":   [6, 5, 4, 3, 2, 1],
    "aleatoria": [3, 6, 1, 4, 2, 5],
}
for nombre, lista in listas.items():
    r = bogo_medido(lista)
    print(f"{nombre:<12}  intentos={r['intentos']:>6}  esc={r['escrituras']:>6}")

Cada ejecución da números distintos (es aleatorio). Esa es exactamente la lección.

Cuándo usar bogo sort

Para nada productivo. Nunca.

Las únicas razones legítimas:

• Como ejemplo pedagógico de qué es una complejidad factorial.
• Como broma técnica entre programadores (existen variantes como “bozo sort”, “stupid sort” y “miracle sort” — esta última no toca la lista y espera a que se ordene por rayos cósmicos, en serio).
• Como vehículo viral en charlas / cursos / RRSS: la animación es muy llamativa.

Comparativa rápida

Algoritmo	Mejor	Peor	Memoria	Útil
Bogo	Ω(n)	O(∞)	O(1)	No
Bubble	Ω(n)	O(n²)	O(1)	Pedagógico
Insertion	Ω(n)	O(n²)	O(1)	Sí, dentro de Timsort
Timsort	Ω(n)	O(n log n)	O(n)	Sí, lo usa Python

Mitos que circulan sobre bogo sort

• “Es solo un chiste.” Bueno, en realidad enseña algo crucial: por qué la diferencia entre O(n log n) y O(n!) no es “un poquito peor”, es “imposible vs trivial”. Pedagógicamente vale más que muchos algoritmos serios.
• “Algún día le tocará la suerte.” Teóricamente sí, en promedio. Pero “promedio” puede ser 38 años para n=20. La estadística es brutal.
• “Es estable.” No (cada shuffle reordena al azar).

¿Y en la stdlib de Python?

Por supuesto que no. Lo más cerca que vas a estar es random.shuffle() que es la pieza que bogo usa. Combinar random.shuffle() con un bucle es bogo sort de una línea — pero por favor, no lo hagas en serio.

Trivia algorítmica

Existen variantes peores que bogo:

• Bozo sort: en vez de barajar todo, intercambia dos elementos al azar. Mismo orden de magnitud que bogo.
• Stupid sort (aka “stooge sort”): O(n^2.71). Mejor que bogo, peor que casi todo.
• Miracle sort: NO toca la lista. Espera a que un rayo cósmico cambie un bit y la lista quede ordenada por casualidad. Tiempo esperado: superior a la edad del universo.
• Quantum bogo sort: en cada iteración crea una rama paralela del multiverso barajando la lista; cuando una rama queda ordenada, las otras se autodestruyen. Asumiendo la interpretación de múltiples mundos de la mecánica cuántica, sería O(n). Sí, es en serio una propuesta académica de broma.

FAQ rápida

¿Es realista usar bogo sort en algún caso?
Para n ≤ 6, sí (puedes ejecutarlo y termina en milisegundos). Para n ≥ 10, no.

¿Por qué la implementación usa random.shuffle?
Porque es la primitiva más natural para “baraja todo al azar”. Internamente usa Fisher-Yates, que es O(n).

¿Hay una variante más “rápida”?
Cualquier cosa es más rápida. Insertion sort es n² (sí, esto es absurdo, pero contra bogo es infinitamente mejor).

¿Para qué lo enseñan?
Para que entiendas qué significa “factorial” en el contexto de Big-O. Cuando alguien te diga “este algoritmo es O(n!)”, tienes que entrar en pánico.

En resumen

Bogo sort es el chiste de los algoritmos de ordenación, pero un chiste educativo. Te enseña a entender el orden de magnitud n! mejor que ninguna clase teórica: cuando ves que para n=20 tu ordenador necesitaría décadas de cómputo, internalizas que la complejidad importa. No lo uses para nada serio. Pero tenlo presente cada vez que tengas la tentación de “iterar hasta que salga bien” sin pensar en el coste.

Si quieres aprender a detectar cuándo tu código tiene un orden de magnitud inviable —antes de que llegue a producción y te despierten a las 3 de la mañana— ese es el camino del curso de El Pythonista.