Ordenamiento por selección
Busca el menor valor restante y lo lleva con un intercambio a la siguiente posición. Hace muy pocos intercambios, pero siempre el mismo número de comparaciones.
- mejor caso Ω(n²)
- caso medio Θ(n²)
- peor caso O(n²)
- espacio O(1)
- no estable
- sin memoria extra
¿Qué significan estos términos?
- Mejor caso: cómo crece el tiempo con el tamaño n de la lista cuando la entrada es la más fácil para este algoritmo.
- Caso medio: cómo suele crecer el tiempo con n. Con n², el doble de valores tarda unas cuatro veces más; n log n crece mucho más despacio.
- Peor caso: el crecimiento con la entrada más difícil. Útil cuando la velocidad nunca debe caer.
- Espacio: cuánta memoria extra hace falta además de la lista. 1 son unas pocas variables; n, una copia de la lista.
- Estable: dos valores iguales conservan su orden original. Importa al ordenar registros por un solo campo.
- Sin memoria extra: ordena dentro de la propia lista, sin una segunda lista.
- comparando
- moviendo
- mínimo actual
- en su lugar final
Pulsa reproducir: las líneas muestran cómo crece el coste
Pulsa reproducir o avanza paso a paso.
Espacio: reproducir o pausar. Flechas izquierda y derecha: paso a paso. Inicio y Fin: saltar.
Prueba esto: Elige una lista invertida. El número de comparaciones es exactamente el mismo que con cualquier otra lista.
Cómo funciona
Recorre la parte sin ordenar y busca el menor valor. Lo intercambia con el primer valor sin ordenar, y así un valor más queda en su lugar final. Siempre revisa todos los valores restantes, aunque la lista ya esté ordenada.
Cuándo es una buena opción
Útil cuando mover datos es caro pero leerlos es barato, porque hace como mucho un intercambio por posición. En casi todos los demás casos, la mejor opción sencilla es el ordenamiento por inserción.