Estabilidad de ordenamiento

Cuando nosotros ordenamos elementos en una lista, a veces nos interesa que estos elementos mantengan su orden relativo original. Quizas tenemos dos o mas criterios de ordenamiento, y queremos reordenar la lista sin perder el orden previamente establecido.

Un ejemplo común de esto, pueden ser datos varios en cualquier tabla como las de excell. Supongamos que el profesor quiere ordenar a sus alumnos por nota, porque quiere establecer un nuevo criterio de promocion o lo que sea. Ahora, va a haber muchos empates en ese criterio, puede haber muchos que se sacaron un 10, otros tantos un 9, y asi sucesivamente. En este ejemplo solo hay 10 numeros para elegir, y quizas tenemos mas de 200 alumnos.

Ahora bien, resulta que la lista de alumnos, previo a ser ordenada por nota, esta ordenada alfabeticamente. Primero esta Alvarez, luego Benitez, y asi. El profesor no quiere perder ese orden al ponerse a ordenar en base a la nota, por lo que quiere que la lista quede ordenada por nota, pero en caso de empate, mantener el orden alfabetico.

Bueno, esto lo podria hacer a mano, lo cual es un delirio personalmente, pero si, es posible. Pero tambien, podria usar algunos de los algoritmos de ordenamiento. Veran, como dijimos antes, hay algoritmos que son estables, es decir, que no van a romper ese criterio previamente establecido.

Un "algoritmo" que sirve para ordenar listas con muchos criterios de orden es el llamado radix, que consiste en ordenar primero por el criterio menos relevante con cualquier algoritmo, y luego el mas relevante con un algoritmo estable, para no perder el orden anterior.

En particular, los algoritmos estables son:

Por otro lado, ejemplos de algoritmos inestables podrian ser: