Ordenamiento por Selección (Selection Sort) – Conceptos, Implementación en Python y Comparativas

Introducción

El ordenamiento por selección es uno de los algoritmos clásicos de clasificación de listas. Aunque su complejidad temporal es O(n²) y no es el método más eficiente para grandes volúmenes de datos, su simplicidad lo convierte en una excelente herramienta pedagógica y en una solución viable para colecciones pequeñas o cuando se necesita una implementación con bajo consumo de memoria.

¿Cómo funciona?

El algoritmo recorre la lista buscando el elemento mínimo (o máximo, según el orden deseado) y lo coloca en la posición correcta. El proceso se repite para el resto de la lista, reduciendo gradualmente la zona sin ordenar.

Pasos básicos:
1. Para i = 0 hasta n-2
2.   Encontrar el índice del elemento mínimo en A[i…n-1]
3.   Intercambiar A[i] con A[min]
4.   i = i + 1

Complejidad y análisis

• Tiempo peor y promedio: O(n²) comparaciones y O(n) intercambios.
• Tiempo mejor: O(n²) (aún se realizan n‑1 comparaciones en cada iteración).
• Espacio adicional: O(1) – algoritmo in‑place.
• Estabilidad: No estable (el intercambio puede cambiar el orden relativo de elementos iguales).

Debido a su bajo número de intercambios, el algoritmo es útil en entornos donde el coste de escritura es crítico, como en dispositivos de memoria flash.

Implementación en Python

def selection_sort(arr, reverse=False):
    """Ordena una lista usando el algoritmo de selección.

    Args:
        arr (list): Lista mutable a ordenar.
        reverse (bool): Si True, ordena de mayor a menor.
    """
    n = len(arr)
    for i in range(n - 1):
        # Índice del elemento óptimo (mínimo o máximo)
        opt_idx = i
        for j in range(i + 1, n):
            if (not reverse and arr[j] < arr[opt_idx]) or (reverse and arr[j] > arr[opt_idx]):
                opt_idx = j
        # Intercambio solo si es necesario
        if opt_idx != i:
            arr[i], arr[opt_idx] = arr[opt_idx], arr[i]
    return arr

# Ejemplo de uso
if __name__ == "__main__":
    lista = [64, 25, 12, 22, 11]
    print("Original:", lista)
    print("Ordenada ascendente:", selection_sort(lista.copy()))
    print("Ordenada descendente:", selection_sort(lista.copy(), reverse=True))

El bloque if __name__ == "__main__" permite ejecutar ejemplos rápidos sin afectar la importación del módulo en otros scripts.

Ejemplos del mundo real

• Ordenar pequeñas colecciones de configuraciones de dispositivos IoT donde la memoria es limitada.
• Clasificar resultados parciales de un algoritmo de búsqueda que ya devuelve una lista casi ordenada.
• Implementar un paso de “pre‑ordenamiento” antes de aplicar algoritmos más complejos como QuickSort para reducir swaps costosos.

Comparativa con otros algoritmos de ordenamiento

Para volúmenes de datos mayores, algoritmos como Merge Sort (O(n log n) y estable) o QuickSort (O(n log n) promedio) son preferibles.

Optimización y buenas prácticas

1. Detección temprana de listas ya ordenadas: antes de iniciar, verifica si el arreglo está ordenado; si lo está, retorna inmediatamente.
2. Minimizar swaps: usa una variable temporal para intercambiar solo cuando el índice óptimo difiere del actual.
3. Uso de tipos de datos mutables: evita copiar la lista si no es necesario; el algoritmo trabaja in‑place.
4. Profiling: aprovecha cProfile o timeit para medir el impacto en entornos críticos.

Solución de problemas (troubleshooting)

• Resultado incorrecto: verifica que el comparador (< o >) corresponda al orden deseado y que no haya sobrescrito accidentalmente la lista original.
• Rendimiento inesperado: confirma que la lista no sea extremadamente grande; para n > 10⁴, considera cambiar a un algoritmo O(n log n).
• Errores de tipo: el algoritmo asume que los elementos son comparables entre sí; si la lista contiene tipos mixtos, conviértelos o define una función key personalizada.

Conclusiones

El ordenamiento por selección sigue siendo una herramienta valiosa para entender los fundamentos de los algoritmos de clasificación. Su bajo consumo de memoria y la mínima cantidad de escrituras lo hacen adecuado para dispositivos embebidos y escenarios donde la estabilidad no es crítica. Sin embargo, para volúmenes de datos significativos, es preferible migrar a algoritmos con complejidad O(n log n).