Nuestros mejores investigadores agotaron sus reservas de café, investigando noche y día por la resolución, hasta que Emanuel encontró la solución en Bitbucket así que en este momento la comparte contigo.
Solución:
Se dice que un algoritmo de clasificación es estable si dos objetos con igual keys aparecen en el mismo orden en la salida ordenada que aparecen en la entrada array para ser ordenado Algunos algoritmos de clasificación son estables por naturaleza, como la clasificación por inserción, la clasificación por combinación, la clasificación por burbuja, etc. Y algunos algoritmos de clasificación no lo son, como la clasificación en montón, la clasificación rápida, etc.
Fondo: un algoritmo de clasificación “estable” mantiene los elementos con la misma clasificación key en orden. Supongamos que tenemos una lista de palabras de 5 letras:
peach
straw
apple
spork
Si ordenamos la lista solo por la primera letra de cada palabra, una ordenación estable produciría:
apple
peach
straw
spork
en un inestable algoritmo de clasificación, straw o spork pueden intercambiarse, pero en uno estable, se mantienen en las mismas posiciones relativas (es decir, ya que straw aparece antes spork en la entrada, también aparece antes spork en la salida).
Podríamos ordenar la lista de palabras usando este algoritmo: ordenación estable por columna 5, luego 4, luego 3, luego 2, luego 1. Al final, se ordenará correctamente. Convéncete de eso. (por cierto, ese algoritmo se llama radix sort)
Ahora, para responder a su pregunta, supongamos que tenemos una lista de nombres y apellidos. Se nos pide ordenar “por apellido, luego por nombre”. Primero podríamos ordenar (estable o inestable) por el nombre, luego ordenar estable por el apellido. Después de estas clasificaciones, la lista se clasifica principalmente por apellido. Sin embargo, cuando los apellidos son iguales, se ordenan los nombres.
No puede apilar clases inestables de la misma manera.
Un algoritmo de clasificación estable es el que ordena los elementos idénticos en el mismo orden en que aparecen en la entrada, mientras que la ordenación inestable podría no satisfacer el caso. – Agradezco a mi profesor de algoritmos, Didem Gozupek, por haber proporcionado información sobre los algoritmos..
Algoritmos de clasificación estables:
- Tipo de inserción
- Ordenar por fusión
- Ordenamiento de burbuja
- Ordenar Tim
- Clasificación de conteo
- Ordenar bloque
- Clasificación cuádruple
- Clasificación de biblioteca
- Coctelera Ordenar
- Clasificación de gnomos
- Clasificación par-impar
Algoritmos de clasificación inestables:
- Ordenar montones
- Clasificación de selección
- Clasificación de concha
- Ordenación rápida
- Introsort (sujeto a Quicksort)
- Tipo de árbol
- Clasificación de ciclo
- Clasificación suave
- Clasificación de torneo (sujeto a Hesapsort)
La estabilidad de clasificación significa que los registros con el mismo key conservan su orden relativo antes y después de la ordenación.
Entonces, la estabilidad importa si, y solo si, el problema que está resolviendo requiere la retención de ese orden relativo.
Si no necesita estabilidad, puede usar un algoritmo rápido que consuma memoria de una biblioteca, como heapsort o quicksort, y olvídese.
Si necesitas estabilidad, es más complicado. Los algoritmos estables tienen un mayor uso de CPU y/o memoria de Big-O que los algoritmos inestables. Entonces, cuando tiene un gran conjunto de datos, debe elegir entre golpear la CPU o la memoria. Si está limitado tanto en la CPU como en la memoria, tiene un problema. Un buen algoritmo estable de compromiso es un tipo de árbol binario; el artículo de Wikipedia tiene una implementación de C++ patéticamente fácil basada en STL.
Puede convertir un algoritmo inestable en uno estable agregando el número de registro original como el último lugar key para cada registro.
Finalizando este artículo puedes encontrar las observaciones de otros administradores, tú aún eres capaz mostrar el tuyo si lo crees conveniente.