Selection sort en Python — explicado paso a paso (con animación)

Selection sort es lo que harías si tuvieras un cajón de calcetines desordenados y los quisieras ordenar por talla: sacas primero el más pequeño, luego el siguiente más pequeño, y así hasta vaciar el cajón. Cada elección es una pasada completa por la parte sin ordenar.

Sencillo de explicar, sencillo de programar, y siempre del orden de n² comparaciones — pase lo que pase. Pero tiene una virtud que los otros O(n²) no tienen: hace muy pocos intercambios, justo n-1 en total. Eso lo convierte en la mejor opción cuando escribir en memoria es caro (memoria flash, BD, ficheros grandes).

Esta entrada cubre el algoritmo en serio: cómo funciona, implementación en Python, JavaScript y Java, su complejidad real, y dónde se sigue justificando hoy.

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

Selection sort en una frase

Encuentra el mínimo de la parte sin ordenar, intercámbialo con la primera posición sin ordenar. Repite con el resto. La parte ordenada crece por la izquierda.

Animación sobre 12 valores con sus contadores en vivo:

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

En las tablas verás tres símbolos: O, Θ y Ω. Idea rápida:

• O(n²) — “O grande”, cota superior (peor caso).
• Ω(n²) — “Omega”, cota inferior (mejor caso). En selection sort, es igual de mala que la superior: siempre hace n² comparaciones, da igual la entrada.
• Θ(n²) — “Theta”: superior e inferior coinciden. Selection sort es Θ(n²) literal, no como bubble o insertion que tienen un mejor caso mejor.

Esta es la diferencia más importante de selection respecto a otros O(n²): el mejor y el peor caso son iguales. La forma de la entrada no influye en las comparaciones. Explicación más larga en el pilar del clúster.

Cómo funciona — traza paso a paso

Ordenamos [3, 1, 4, 1, 5] a mano.

i = 0, buscamos el mínimo en [3, 1, 4, 1, 5]:
– Recorro: el mínimo es 1 (en posición 1).
– Intercambio posición 0 con posición 1 → [1, 3, 4, 1, 5].
– Parte ordenada: [1].

i = 1, buscamos el mínimo en [3, 4, 1, 5]:
– El mínimo es 1 (en posición 3).
– Intercambio posición 1 con posición 3 → [1, 1, 4, 3, 5].
– Parte ordenada: [1, 1].

i = 2, buscamos el mínimo en [4, 3, 5]:
– El mínimo es 3 (en posición 3).
– Intercambio posición 2 con posición 3 → [1, 1, 3, 4, 5].
– Parte ordenada: [1, 1, 3].

i = 3, buscamos el mínimo en [4, 5]:
– El mínimo es 4 (en posición 3). Ya está en su sitio → no toca.

Total: 10 comparaciones, 3 intercambios para 5 elementos. Importante: las comparaciones son siempre las mismas, da igual cómo esté ordenada la entrada — siempre haces todas para encontrar cada mínimo. Esa es la mayor pega de selection sort.

Implementación en Python

def ordenar(lista: list[int]) -> list[int]:
    n = len(lista)
    for i in range(n - 1):
        minimo = i
        for j in range(i + 1, n):
            if lista[j] < lista[minimo]:
                minimo = j
        if minimo != i:
            lista[i], lista[minimo] = lista[minimo], lista[i]
    return lista


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

Tres detalles:

1. La variable minimo guarda el índice del mínimo, no el valor. Así puedo intercambiar sin recalcular.
2. El bucle interno empieza en i + 1, no en 0: ya hemos colocado los i primeros, no tiene sentido volver a mirarlos.
3. El if minimo != i ahorra el intercambio cuando ya estaba en su sitio. Es la única optimización trivial.

En entrevistas, cuando expliques selection, subraya que hace exactamente n-1 intercambios (en el peor caso, antes de la optimización del if). Es la diferencia que lo justifica frente a otros O(n²).

Implementación en JavaScript

function ordenar(lista) {
  const n = lista.length;
  for (let i = 0; i < n - 1; i++) {
    let minimo = i;
    for (let j = i + 1; j < n; j++) {
      if (lista[j] < lista[minimo]) {
        minimo = j;
      }
    }
    if (minimo !== i) {
      [lista[i], lista[minimo]] = [lista[minimo], lista[i]];
    }
  }
  return lista;
}

console.log(ordenar([3, 1, 4, 1, 5])); // [1, 1, 3, 4, 5]

Implementación en Java

public static void ordenar(int[] lista) {
    int n = lista.length;
    for (int i = 0; i < n - 1; i++) {
        int minimo = i;
        for (int j = i + 1; j < n; j++) {
            if (lista[j] < lista[minimo]) {
                minimo = j;
            }
        }
        if (minimo != i) {
            int tmp = lista[i];
            lista[i] = lista[minimo];
            lista[minimo] = tmp;
        }
    }
}

Complejidad — por qué siempre es O(n²) pero hace pocos intercambios

Esto es lo curioso de selection:

• Comparaciones: siempre n²/2 (más o menos). Da igual cómo esté la lista de entrada. Recorre la parte sin ordenar SIEMPRE entera para encontrar el mínimo. Por eso no se beneficia de listas casi ordenadas como insertion.
• Intercambios: solo n - 1 como mucho. Uno por pasada, y a veces ni eso. Esto es lo mejor que ofrece selection.

Por qué NO es estable. El intercambio “salta” sobre elementos intermedios. Imagina la lista [3a, 2, 3b, 1] (donde 3a y 3b son iguales en clave pero distintos en identidad). El primer paso busca el mínimo (1 en posición 3) y lo intercambia con la posición 0 → [1, 2, 3b, 3a]. El 3a y el 3b han cambiado su orden relativo. Por eso selection NO es estable de fábrica.

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

Todo el clúster usa las mismas 10 listas fijas (n=15) para cruzar honestamente unos algoritmos con otros:

Aplicamos selection sort sobre las 10:

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

Salida real:

Lista            Comp.  Interc.  Escr.  Tiempo (ms)   Caso  Θ observada
---------------  -----  -------  -----  -----------  -----  -----------
ordenada         105          0      0        0.006  Único        Θ(n²)
inversa          105          7     14        0.007  Único        Θ(n²)
casi_ordenada    105          1      2        0.006  Único        Θ(n²)
muy_desordenada  105         13     26        0.008  Único        Θ(n²)
duplicados       105         11     22        0.007  Único        Θ(n²)
aleatoria_s1     105         10     20        0.007  Único        Θ(n²)
aleatoria_s2     105         12     24        0.007  Único        Θ(n²)
aleatoria_s3     105         12     24        0.007  Único        Θ(n²)
aleatoria_s4     105         13     26        0.008  Único        Θ(n²)
aleatoria_s5     105         10     20        0.007  Único        Θ(n²)

La columna Comp. vale 105 en TODAS las filas. Esto es la marca de fábrica de selection: sin importar la forma de la entrada, siempre hace n*(n-1)/2 = 15*14/2 = 105 comparaciones. La librería lo detecta y clasifica todas las filas como Único (no hay distinción real entre mejor, medio y peor caso) con complejidad observada Θ(n²).

Lo que SÍ varía son los intercambios:

• ordenada → 0 intercambios. El if minimo != i se salta el swap cuando el mínimo ya estaba en su sitio.
• casi_ordenada → 1 intercambio. La mayoría ya estaba bien.
• inversa → 7 intercambios (≈n/2). Cada pasada encuentra un mínimo lejano.
• duplicados, muy_desordenada, aleatorias → entre 10 y 13 intercambios. Lo esperable estadísticamente para n=15.

Esto es el punto vendedor de selection sort: si en tu escenario escribir cuesta caro (memoria flash, BBDD, índices) y comparar cuesta barato, selection minimiza la operación cara. Compara con sus rivales O(n²) sobre casi_ordenada:

Selection paga el precio máximo en comparaciones a cambio del mínimo absoluto en intercambios. Cada algoritmo paga en una moneda distinta.

¿Y el escalado? Sobre aleatoria_s1:

Casi 50 millones de comparaciones para n=10.000. Es la cara cruda del Θ(n²) puro, sin matices.

Reproducirlo sin instalar nada

sortlab vive privado en el Python profesional: medir, optimizar y escalar. Versión instrumentada inline para reproducir sin la librería:

def selection_medido(lista_original: list[int]) -> dict:
    arr = list(lista_original)
    comparaciones = 0
    intercambios = 0
    n = len(arr)
    for i in range(n - 1):
        minimo = i
        for j in range(i + 1, n):
            comparaciones += 1
            if arr[j] < arr[minimo]:
                minimo = j
        if minimo != i:
            arr[i], arr[minimo] = arr[minimo], arr[i]
            intercambios += 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 = selection_medido(lista)
    print(f"{nombre:<16}  comp={r['comparaciones']:>3}  swap={r['intercambios']:>3}")

Verás: comparaciones siempre 105 (la marca de selection); intercambios variables. Cuadra con la tabla de sortlab.

Mitos que circulan sobre selection sort

• “Es mejor que bubble porque es más sencillo.” Es igual de sencillo. La diferencia real es que selection minimiza intercambios y bubble los maximiza. Si tu cuello de botella son las escrituras, selection gana; si no, insertion (que ni siquiera es bubble) gana.
• “Selection no se usa para nada.” Falso. En hardware embebido con memoria flash, donde cada escritura desgasta el chip físico, selection sort es la opción correcta justamente por hacer el mínimo de escrituras.
• “Selection es estable.” No lo es. El intercambio “a distancia” puede separar elementos iguales. Si necesitas estabilidad, usa insertion sort.

¿Y en la stdlib de Python?

No. No hay selection sort en la stdlib. Para ordenar usa list.sort() (Timsort). Si tienes un escenario raro donde escribir cuesta caro y quieres minimizar swaps, tendrías que implementártelo o usar una variante de selection custom.

Trivia algorítmica

Selection sort tiene una variante elegante llamada heapsort que sigue la misma idea (“encuentra el mayor/menor y sácalo”) pero usa una estructura de datos (el heap) para encontrarlo en O(log n) en vez de O(n). Resultado: O(n log n) en total, ya en la liga buena. Lo cubrimos en el post de heapsort.

Cuándo usar selection (poco, pero hay casos reales)

Sí:

• Cuando escribir en memoria es caro. Memoria flash, escrituras a disco, BBDD con índices… ahí cada intercambio cuesta más que una comparación, y selection minimiza intercambios.
• Como pieza didáctica. Es uno de los algoritmos más fáciles de explicar y de programar a mano.
• Listas muy pequeñas donde el overhead de algoritmos más sofisticados no compensa.

No:

• Casi cualquier escenario “normal”. Insertion lo bate en listas casi ordenadas, quicksort y merge lo barren en cuanto la lista crece, y nadie en producción lo usa como sort principal.

Comparativa rápida

Conviene saber: la métrica “intercambios mínimos” es la única en la que selection brilla absolutamente. Por eso aparece en libros como el algoritmo de elección cuando las escrituras son la operación cara — un escenario raro en RAM moderna, pero perfectamente real en hardware embebido o BBDD pesadas.

FAQ rápida

¿Por qué selection sort NO es estable?
Porque el intercambio “salta” sobre elementos intermedios. Dos valores iguales pueden cambiar su orden relativo durante un swap a distancia.

¿Se puede hacer estable?
Sí, sustituyendo el intercambio por un desplazamiento (igual que insertion sort hace shifts). Pero entonces pierdes la ventaja de “mínimos intercambios” y se vuelve básicamente insertion. No tiene sentido.

¿Por qué siempre es O(n²) incluso si la lista ya está ordenada?
Porque para encontrar el mínimo de cada subarray, siempre tienes que recorrerlo entero. No hay forma de “saber” que ya estaba ordenado sin haberlo comprobado.

¿Por qué se usa todavía en sistemas embebidos?
Porque hace pocas escrituras y eso ahorra ciclos de vida en memorias flash, donde cada escritura desgasta el chip. En hardware moderno con RAM rápida la métrica deja de ser relevante.

¿Cuál es la diferencia clave con insertion?
Insertion construye el orden insertando cada elemento en su sitio (los moves son por desplazamiento). Selection lo construye seleccionando el mínimo y trayéndolo (los moves son por intercambio a distancia). Diferente filosofía, mismo Big-O en el peor caso.

En resumen

Selection sort es el algoritmo “honesto”: sabes exactamente cuántas operaciones hará antes de empezar (n²/2 comparaciones, máximo n-1 intercambios). Esa predictibilidad lo hace didáctico y útil en escenarios donde escribir es caro. Pero para listas grandes o ya casi ordenadas, está claramente superado.

Si quieres aprender a elegir el algoritmo correcto para tu problema real —no solo a recitar Big-O— ese es el camino del curso de El Pythonista.