El ordenamiento por selección (selection sort) en Python
En esta lección vas a implementar el ordenamiento por selección buscando cada vez el elemento más pequeño para colocarlo en su sitio.
Introducción
El problema
Algunos algoritmos de ordenación intentan hacer el menor número posible de movimientos, algo importante cuando mover un elemento es caro. El ordenamiento por selección muestra una estrategia distinta a la de burbuja: primero encuentra el elemento correcto y luego lo mueve una sola vez.
Imagínalo así
El ordenamiento por selección es como formar un equipo por estatura. Miras a todos los que siguen esperando, llamas al más bajo y lo pones en el siguiente sitio de la fila. Luego vuelves a mirar al resto para encontrar al siguiente más bajo, hasta que no queda nadie.
for start in range(len(result)):📍 El siguiente sitio libre de la filaminimum = start🤔 Supón que esta persona es la más bajaresult[index] < result[minimum]🔎 Busca entre el resto a alguien más bajoresult[start], result[minimum] = ...🔄 Pon al más bajo en el sitio libreEl ordenamiento por selección busca una y otra vez el elemento más pequeño de la parte sin ordenar y lo intercambia a la siguiente posición de la parte ordenada. Hace O(n²) comparaciones, pero como mucho n - 1 intercambios.
Puntos clave
- Todo lo que está a la izquierda de
startya está ordenado; desdestarten adelante, no. minimumrecuerda el índice del valor más pequeño encontrado hasta ahora en la parte sin ordenar.- El bucle interior
for index in range(start + 1, len(result)):revisa el resto de la lista. result[start], result[minimum] = result[minimum], result[start]hace un intercambio por posición.
¿Cuándo se usa?
- Aprender estrategias de ordenación y compararlas.
- Situaciones en las que escribir o mover elementos es caro y comparar es barato.
- Encontrar los k elementos más pequeños parando tras k pasadas.
Cuándo no hace falta
- Programas reales:
sorted()es mucho más rápido. - Datos casi ordenados: la selección sigue revisándolo todo, mientras que la inserción termina enseguida.
Visualizador de El ordenamiento por selección (selection sort) en Python
O(n²)Usa Reproducir o Paso para seguir cada comparación y movimiento de datos.
Código de ejemplo
def selection_sort(values):
result = values.copy()
for start in range(len(result)):
minimum = start
for index in range(start + 1, len(result)):
if result[index] < result[minimum]:
minimum = index
result[start], result[minimum] = result[minimum], result[start]
return result
print(selection_sort([64, 25, 12, 22, 11]))
Resultado de la ejecución
[11, 12, 22, 25, 64]
Explicación del código
La variable minimum recuerda la posición del valor más pequeño en el resto de la lista. Al final de cada pasada, ese valor se intercambia con la posición start. El algoritmo siempre tiene una complejidad de O(n²) por las muchas comparaciones, pero hace como mucho n intercambios.
Cambia los valores y ejecuta el programa en el compilador Python online de CodeUtility sin instalar Python.
Ejercicios de práctica
Prueba a modificar el código siguiendo las ideas de abajo. Cambiar el código y ver el resultado te ayudará a entender la lección mucho mejor que solo leerla.
- Prueba con una lista vacía, una lista de un solo elemento y una lista con repetidos.
- Muestra el estado después de cada paso para ver el algoritmo en acción.
- Mide el tiempo de ejecución con 100, 1.000 y 10.000 elementos y compáralo con otra solución.
Errores comunes
Intercambiar dentro del bucle interior
Eso lo convierte en un ordenamiento más lento y desordenado, con muchos intercambios.
for index in range(start + 1, len(result)):
if result[index] < result[start]:
result[start], result[index] = result[index], result[start]
for index in range(start + 1, len(result)):
if result[index] < result[minimum]:
minimum = index
result[start], result[minimum] = result[minimum], result[start]
¿Terminaste esta lección?
Márcala como aprendida para seguir tu progreso.
Practica con un reto
Usa lo que cubre esta lección para resolver un problema real. Cada reto se ejecuta en el navegador, con pruebas al instante y una revisión de IA.
- Mínimo de un Arreglo Encuentra el valor más pequeño en una lista. Fácil
- K-th Smallest Element Find the k-th smallest value without fully sorting. Intermedio