¿Por qué Selection Sort no es estable?

Question

Esto podría ser trivial, pero no entiendo por qué la implementación predeterminada de Selection Sort no es estable?

En cada iteración se encuentra el elemento mínimo en la matriz restante. Al encontrar este mínimo, puede elegir el primer mínimo que encuentre, y solo actualizarlo cuando un elemento es realmente más pequeño que él. Entonces, el elemento elegido en cada iteración es el primer mínimo, es decir, es el primero en el orden de clasificación anterior. Por lo tanto, a mi entender, el género actual no destruirá un orden generado por un género anterior en elementos iguales.

¿Qué me estoy perdiendo?

Answer 1

Un pequeño ejemplo:

Sea B = B en

< B>, < b>, < a>, < C> (con un < b < c)

Después de una ciclo la secuencia está ordenada pero el orden de B y b ha cambiado:

< a>, < b>, < B >, < c>

Pero puede implementar Selecciones Clasificar estable si, en lugar de cambiar, inserte el valor mínimo. Pero para que eso sea eficiente, debe tener una estructura de datos que admita la inserción a bajo costo o de lo contrario terminará con una complejidad cuadrática.

Answer 2

El problema es que la ordenación de selección intercambia elementos del frente de la matriz en el lugar desocupado por el elemento mínimo, lo que puede arruinar el orden ordenado. Por ejemplo, supongamos que yo estoy clasificación

(4, 0), (4, 1), (1, 0) 

Selección tipo primero intercambia los (1, 0) en la parte delantera:

(1, 0), (4, 1), (4, 0) 

Y ahora el (4, 0) y (4, 1) están fuera de servicio desde donde comenzaron en el género. Ejecutar esto hasta su finalización deja los elementos en este orden, y los 4s están fuera de servicio.

Espero que esto ayude!

Answer 3

Estable significa que no calcula más si los elementos ya están ordenados, pero calcula hasta el final, por lo tanto, no es estable.