Cómo funciona
El array se divide en una parte ordenada y definitiva, a la izquierda, y el resto.
En cada pasada un haz recorre todo el resto buscando su mínimo: la etiqueta «mín»
salta cada vez que aparece uno menor. Al acabar, un único intercambio lleva ese
mínimo al frente, donde ya no se moverá.
No hay atajos: para saber cuál es el menor hay que mirarlos todos. Por eso hace siempre
n(n−1)/2 comparaciones, esté como esté el array. A cambio, hace como mucho n − 1
intercambios, uno por pasada y solo si hace falta: útil cuando escribir es caro, como en
algunas memorias flash.
Paso a paso con [5, 3, 5, 1]
Los dos 5 llevan una letra para poder seguirlos: 5a es el que empieza delante.
- 01Pasada 1: mín = 5a; 3 < 5a, mín = 3; 5b no es menor; 1 < 3, mín = 1. Intercambia 5a y 1 →
[1, 3, 5b, 5a]. El 5a salta por encima del 5b. 3 comparaciones.
- 02Pasada 2: mín = 3; ni 5b ni 5a son menores. El 3 ya está en su sitio: no intercambia. 2 comparaciones.
- 03Pasada 3: mín = 5b; 5a no es menor (empate: se queda el primero). No intercambia. 1 comparación. El último queda en su sitio solo.
- ΣTotal: 6 comparaciones (4·3/2, como siempre con n = 4) y un solo intercambio; Bubble Sort, con el mismo array, haría 4. Pero los dos 5 han acabado al revés, 5b delante de 5a: Selection Sort no es estable.
Por qué no es estable
Un algoritmo es estable si los elementos iguales conservan su orden original, algo importante al
ordenar por varios criterios (por ejemplo, por apellido y luego por nota). El intercambio de
Selection Sort es de larga distancia: el número que estaba al frente salta hasta donde estaba el
mínimo, y puede pasar por encima de otro igual a él. Bubble e Insertion Sort solo mueven vecinos
y nunca cruzan dos iguales, por eso sí son estables.
Complejidad
- Mejor caso
- O(n²)
- Caso promedio
- O(n²)
- Peor caso
- O(n²)
- Intercambios
- O(n)
- Estable
- No
- Espacio extra
- O(1)