Cualquier algoritmo de ordenación puede usarse para realizar una ordenación estable . ¡Si! Incluso los que no son inherentemente estables. ¿Pero cómo? La ordenación estable conserva el orden relativo de las claves.
Considere un ejemplo con clave de entero y algún otro atributo y desea una ordenación estable. A = [1: A 2: A 1: B 2: B]. La clasificación estable A debería dar [1: A 1: B 2: A 2: B]. Pero el ordenamiento por selección, el ordenamiento rápido o cualquier otro algoritmo de ordenamiento donde la estabilidad NO esté garantizada NO puede darle ese orden.
Entonces. ¿Cuál es el truco? Agregue un atributo más: la posición del elemento en la matriz original. Construye una matriz B desde A como esta
- ¿Cuál es el algoritmo de cifrado más complejo?
- ¿Qué es una matriz ordenada y en qué se diferencia de una que no está ordenada?
- ¿Cómo funciona el PageRank?
- ¿Es la prueba de primalidad Rabin-Miller más rápida que el tamiz de Eratóstenes?
- ¿Por qué estudiamos diferentes algoritmos para la misma tarea?
A = [1: A 2: A 1: B 2: B]
B = [1: A (1) 2: A (2) 1: B (3) 2: B (4)]
Ahora tiene que cambiar la función de comparación utilizada para ordenar un poco. Utilice [math] (OriginalKey, ElementPosition) [/ math] como clave para ordenar. Se garantiza que esta tupla es única para todos los elementos en B. Por lo tanto, la estabilidad del tipo no importa aquí. Ahora elimine el atributo de posición y devuelva la matriz ordenada.
La complejidad del espacio sigue siendo la misma, aunque la constante aumenta. También lo hace la complejidad del tiempo.
