algorithm - ¿Qué es la estabilidad en los algoritmos de clasificación y por qué es importante?
sorting language-agnostic (9)
Depende de lo que hagas
Imagina que tienes algunos registros de personas con un primer y un último campo de nombre. Primero ordena la lista por nombre. Si luego ordena la lista con un algoritmo estable por apellido, tendrá una lista ordenada por nombre y apellido.
Tengo mucha curiosidad, ¿por qué la estabilidad es o no es importante en los algoritmos de clasificación?
Hay algunas razones por las que la estabilidad puede ser importante. Una es que si no es necesario intercambiar dos registros intercambiándolos, puede causar una actualización de la memoria, una página se marca como sucia y necesita ser reescrita en el disco (u otro medio lento).
La clasificación estable siempre devolverá la misma solución (permutación) en la misma entrada.
Por ejemplo, [2,1,2] se ordenará utilizando el género estable como permutación [2,1,3] (primero es el índice 2, luego el índice 1 y luego el índice 3 en la salida ordenada) Eso significa que la salida siempre se baraja de la misma manera. Otra permutación no estable, pero aún correcta es [2,3,1].
La ordenación rápida no es estable y las diferencias de permutación entre los mismos elementos dependen del algoritmo para seleccionar el pivote. Algunas implementaciones se recogen al azar y pueden hacer que la ordenación rápida produzca permutaciones diferentes en la misma entrada usando el mismo algoritmo.
Algoritmo de clasificación estable es necesario determinista.
La estabilidad de clasificación significa que los registros con la misma clave 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 de memoria de una biblioteca, como heapsort o quicksort, y olvidarse de ello.
Si necesitas estabilidad, es más complicado. Los algoritmos estables tienen una mayor CPU-O y / o mayor uso de memoria que los algoritmos inestables. Entonces, cuando tienes un gran conjunto de datos, debes 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 C ++ patéticamente fácil basada en el STL.
Puede convertir un algoritmo inestable en uno estable agregando el número de registro original como la clave del último lugar para cada registro.
Sé que hay muchas respuestas para esto, pero para mí, esta respuesta , de Robert Harvey , la resumió mucho más claramente:
Un tipo estable es aquel que preserva el orden original del conjunto de entrada, donde el algoritmo [inestable] no distingue entre dos o más elementos.
Se dice que un algoritmo de clasificación es estable si dos objetos con las mismas claves aparecen en el mismo orden en la salida ordenada que aparecen en la matriz de entrada que se va a ordenar. Algunos algoritmos de ordenación son estables por naturaleza, como tipo de inserción, tipo de fusión, tipo de burbuja, etc. Y algunos algoritmos de ordenación no son, por ejemplo, tipo de ordenamiento, clasificación rápida, etc.
Antecedentes : un algoritmo de clasificación "estable" mantiene en orden los elementos con la misma clave de clasificación. Supongamos que tenemos una lista de palabras de 5 letras:
peach
straw
apple
spork
Si clasificamos la lista con solo la primera letra de cada palabra, entonces una clasificación estable produciría:
apple
peach
straw
spork
En un algoritmo de clasificación inestable , la straw o spork pueden intercambiarse, pero en una estable, permanecen en las mismas posiciones relativas (es decir, dado que la straw aparece antes de spork en la entrada, también aparece antes de spork en la salida).
Podríamos ordenar la lista de palabras usando este algoritmo: clasificación estable en la columna 5, luego 4, luego 3, luego 2, luego 1. Al final, se ordenará correctamente. Convénzase de eso. (por cierto, ese algoritmo se llama ordenar de raíz)
Ahora para responder a su pregunta, supongamos que tenemos una lista de nombres y apellidos. Se nos pide que ordenemos "por apellido, luego por primero". Primero podríamos ordenar (estable o inestable) por el primer nombre, luego ordenarlo por el apellido. Después de este tipo, la lista está ordenada principalmente por el apellido. Sin embargo, cuando los apellidos son los mismos, los primeros nombres se ordenan.
No puede apilar géneros inestables de la misma manera.
Se dice que un algoritmo de clasificación es estable si dos objetos con las mismas teclas aparecen en el mismo orden en la salida ordenada que aparecen en la matriz sin clasificar de entrada. Algunos algoritmos de ordenación son estables por naturaleza, como tipo de inserción, tipo de fusión, tipo de burbuja, etc. Y algunos algoritmos de ordenación no son, por ejemplo, tipo de ordenamiento, clasificación rápida, etc.
Sin embargo, cualquier algoritmo de clasificación dado que no sea estable se puede modificar para que sea estable. Puede haber formas algo específicas para hacerlo estable, pero en general, cualquier algoritmo de clasificación basado en comparación que no sea estable por naturaleza se puede modificar para que sea estable cambiando la operación de comparación de teclas para que la comparación de dos claves considere la posición como una factor para objetos con llaves iguales.
Referencias: http://www.math.uic.edu/~leon/cs-mcs401-s08/handouts/stability.pdf http://en.wikipedia.org/wiki/Sorting_algorithm#Stability
Si supone que lo que está ordenando son solo números y solo sus valores los identifican / distinguen (por ejemplo, los elementos con el mismo valor son identículos), entonces la cuestión de la estabilidad de la clasificación no tiene sentido.
Sin embargo, los objetos con la misma prioridad en la clasificación pueden ser distintos, y en algún momento su orden relativo es información significativa. En este caso, la clasificación inestable genera problemas.
Por ejemplo, tiene una lista de datos que contiene el costo de tiempo [T] de todos los jugadores para limpiar un laberinto con Nivel [L] en un juego. Supongamos que necesitamos clasificar a los jugadores por la rapidez con que limpian el laberinto. Sin embargo, se aplica una regla adicional: los jugadores que limpian el laberinto con un nivel superior siempre tienen un rango más alto, sin importar cuánto tiempo sea el costo del tiempo.
Por supuesto, puede tratar de asignar el valor apareado [T, L] a un número real [R] con algún algoritmo que siga las reglas y clasificar a todos los jugadores con el valor [R].
Sin embargo, si la clasificación estable es factible, entonces simplemente puede ordenar la lista completa por [T] (jugadores más rápidos primero) y luego por [L]. En este caso, el orden relativo de los jugadores (por costo de tiempo) no cambiará después de agruparlos por nivel de laberinto que limpiaron.
PD: por supuesto, el enfoque para ordenar dos veces no es la mejor solución para el problema en particular, pero para explicar la cuestión del póster, debería ser suficiente.
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 clasificación inestable puede no satisfacer el caso.
Algoritmos de clasificación estables:
- Tipo de inserción
- Merge Sort
- Ordenamiento de burbuja
- Tim Sort
- Contando Sort
Algoritmos de clasificación inestables:
- Heap Sort
- Clasificación de selección
- Tipo de concha
- Ordenación rápida
