¿Qué significa que un algoritmo de clasificación sea "estable"?

Una clasificación estable es aquella que conserva el orden original del conjunto de entrada, donde el algoritmo de comparación no distingue entre dos o más elementos.

Considere un algoritmo de clasificación que ordene las tarjetas por rango , pero no por palo. El ordenamiento estable garantizará que se mantenga el orden original de las tarjetas que tienen el mismo rango; la ordenación inestable no lo hará.

Los algoritmos estables conservan el orden relativo de los elementos.

Por lo tanto, un algoritmo de clasificación estable conservará el orden relativo de los valores que se comparan como iguales.

Considere un algoritmo de clasificación donde ordenemos una colección de puntos 2d en función de su dimensión X.

Colección a ordenar: {(6, 3), (5, 5), (6, 1), (1, 3)}

Clasificación estable: {(1, 3), (5, 5), (6, 3), (6, 1)}

Ordenados regulares: ya sea {(1, 3), (5, 5), (6, 3), (6, 1)} o {(1, 3), (5, 5), (6, 1), (6, 3)}

En cuanto a la compensación ... bueno, la clasificación estable es menos eficiente, pero a veces la necesitas.

Por ejemplo, cuando un usuario hace clic en el encabezado de una columna para ordenar los valores en una interfaz de usuario, es razonable esperar que se utilice su orden de clasificación anterior en el caso de valores iguales.