algorithm - quick - ¿Por qué Selection Sort no es estable?
quicksort python (3)
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?
El medio estable no calcula más si los elementos ya están ordenados, pero calcula hasta el final, por lo tanto, no es estable.
El problema es que la selección ordena el intercambio de 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 estoy clasificando
(4, 0), (4, 1), (1, 0)
El tipo de selección primero intercambia el (1, 0) al frente:
(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!
Un pequeño ejemplo:
Deje b = B en
<B>, <b>, <a>, <C> (con a <b <c)
Después de un ciclo, la secuencia se ordena, pero el orden de B y b ha cambiado:
<a>, <b>, <B>, <c>
Pero puede implementar Selecciones Ordenar 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.