¿Qué es la estabilidad en los algoritmos de clasificación y por qué es importante?

Tengo mucha curiosidad, ¿por qué la estabilidad es o no importante en la clasificación de algoritmos?

Se dice que un algoritmo de ordenación es estable si dos objetos con claves iguales aparecen en el mismo orden en la salida ordenada que aparecen en la matriz de entrada a ordenar. Algunos algoritmos de ordenación son estables por naturaleza, como la ordenación por inserción, la ordenación por fusión, la ordenación por burbujas, etc. Y algunos algoritmos de ordenación no lo son, como la ordenación por montón, la ordenación rápida, etc.

Antecedentes : un algoritmo de clasificación "estable" mantiene los elementos con la misma clave de clasificación en orden. Supongamos que tenemos una lista de palabras de 5 letras:

peach
straw
apple
spork

Si clasificamos la lista solo por la primera letra de cada palabra, un tipo estable produciría:

apple
peach
straw
spork

En un algoritmo de ordenamiento inestable , strawo sporkpuede intercambiarse, pero en uno estable, permanecen en las mismas posiciones relativas (es decir, como strawaparece antes sporken la entrada, también aparece antes sporken 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énzase de eso. (por cierto, ese algoritmo se llama clasificación de radix)

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 estable ordenar por el apellido. Después de estos tipos, la lista se ordena principalmente por el apellido. Sin embargo, donde los apellidos son iguales, los nombres se ordenan.

No puedes apilar tipos inestables de la misma manera.

Un algoritmo de ordenación estable es el que clasifica los elementos idénticos en el mismo orden en que aparecen en la entrada, mientras que la ordenación inestable puede 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 fusión
• Ordenamiento de burbuja
• Tim Sort
• Contando Ordenar
• Orden de bloque
• Quadsort
• Ordenar biblioteca
• Coctelera Ordenar
• Gnome Sort
• Clases pares e impares

Algoritmos de clasificación inestables:

• Tipo de montón
• Tipo de selección
• Tipo de concha
• Ordenación rápida
• Introsort (sujeto a Quicksort)
• Tipo de árbol
• Tipo de ciclo
• Smoothsort
• Clasificación de torneo (sujeto a Hesapsort)

La estabilidad de clasificación significa que los registros con la misma clave conservan su orden relativo antes y después de la clasificación.

Entonces, la estabilidad es importante 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 extracción de memoria de una biblioteca, como ordenamiento dinámico o rápido, y olvidarse de él.

Si necesita estabilidad, es más complicado. Los algoritmos estables tienen mayor uso de CPU y / o memoria big-O que los algoritmos inestables. Entonces, cuando tiene un gran conjunto de datos, debe elegir entre golpear la CPU o la memoria. Si tiene limitaciones tanto en la CPU como en la memoria, tiene un problema. Un buen algoritmo de compromiso estable es un árbol binario; el artículo de Wikipedia tiene un patéticamente fácil aplicación C ++ basado en la STL.

Puede convertir un algoritmo inestable en uno estable agregando el número de registro original como la clave de último lugar para cada registro.

Depende de lo que hagas.

Imagine que tiene algunos registros de personas con un campo de nombre y apellido. 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.

Hay algunas razones por las cuales la estabilidad puede ser importante. Una es que, si no es necesario intercambiar dos registros intercambiándolos, puede provocar una actualización de memoria, una página está marcada como sucia y debe reescribirse en el disco (u otro medio lento).

Se dice que un algoritmo de clasificación es estable si dos objetos con claves iguales aparecen en el mismo orden en la salida ordenada que en la matriz sin clasificar de entrada. Algunos algoritmos de ordenación son estables por naturaleza, como la ordenación por inserción, la ordenación por fusión, la ordenación por burbujas, etc. Y algunos algoritmos de ordenación no lo son, como la ordenación por montón, la ordenación rápida, etc.

Sin embargo, cualquier orden de clasificación que no sea estable puede modificarse para que sea estable. Puede haber formas específicas de clasificación para hacerlo estable, pero en general, cualquier algoritmo de clasificación basado en la comparación que no sea estable por naturaleza puede modificarse para que sea estable cambiando la operación de comparación de claves para que la comparación de dos claves considere la posición como un factor para objetos con claves iguales.

Referencias: http://www.math.uic.edu/~leon/cs-mcs401-s08/handouts/stability.pdf http://en.wikipedia.org/wiki/Sorting_algorithm#Stability

Sé que hay muchas respuestas para esto, pero para mí, esta respuesta , de Robert Harvey , lo resumió mucho más claramente:

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

Fuente

Si asume 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 idénticos), entonces el problema de 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 ordenació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 según 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 cuesta.

Por supuesto, puede intentar asignar el valor emparejado [T, L] a un número real [R] con algún algoritmo que siga las reglas y luego clasificar a todos los jugadores con el valor [R].

Sin embargo, si la ordenación estable es factible, entonces simplemente puede ordenar la lista completa por [T] (primero los jugadores más rápidos) y luego por [L]. En este caso, el orden relativo de los jugadores (por costo de tiempo) no cambiará después de haberlos agrupado 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.

La ordenación estable siempre devolverá la misma solución (permutación) en la misma entrada.

Por ejemplo, [2,1,2] se ordenará utilizando una clasificación 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 elegir el pivote. Algunas implementaciones comienzan al azar y eso puede hacer que la ordenación rápida produzca diferentes permutaciones en la misma entrada usando el mismo algoritmo.

El algoritmo de clasificación estable es necesario determinista.

Algunos ejemplos más de la razón por la que se desean tipos estables. Las bases de datos son un ejemplo común. Tome el caso de una base de datos de transacciones que incluya apellido | nombre, fecha | hora de compra, número de artículo, precio. Digamos que la base de datos normalmente está ordenada por fecha | hora. Luego se realiza una consulta para hacer una copia ordenada de la base de datos por apellido |, ya que una ordenación estable conserva el orden original, aunque la comparación de consultas solo involucra el apellido, las transacciones para cada apellido | estar en orden de datos | tiempo.

Un ejemplo similar es el Excel clásico, que limita las clases a 3 columnas a la vez. Para ordenar 6 columnas, se realiza una ordenación con las 3 columnas menos significativas, seguida de una ordenación con las 3 columnas más significativas.

Un ejemplo clásico de una clasificación de radix estable es un clasificador de tarjetas, usado para clasificar por un campo de columnas numéricas de base 10. Las tarjetas se ordenan del dígito menos significativo al dígito más significativo. En cada pase, se lee un mazo de cartas y se separa en 10 compartimientos diferentes de acuerdo con el dígito en esa columna. Luego, las 10 bandejas de tarjetas se vuelven a colocar en la tolva de entrada en orden (las tarjetas "0" primero, las tarjetas "9" al final). Luego se realiza otro pase en la siguiente columna, hasta que todas las columnas estén ordenadas. Los clasificadores de tarjetas reales tienen más de 10 bandejas, ya que hay 12 zonas en una tarjeta, una columna puede estar en blanco y hay una bandeja de lectura incorrecta. Para ordenar letras, se necesitan 2 pasadas por columna, 1ra pasada para el dígito, 2da pasada para la zona 12 11.

Más tarde (1937) hubo máquinas de clasificación (fusión) de tarjetas que podían fusionar dos barajas de cartas al comparar campos. La entrada era dos mazos de cartas ya ordenados, un mazo maestro y un mazo de actualización. El intercalador fusionó las dos cubiertas en una nueva papelera y una papelera de archivo, que se usaba opcionalmente para duplicados maestros para que la nueva papelera maestra solo tuviera tarjetas de actualización en caso de duplicados. Esta fue probablemente la base de la idea detrás del tipo de fusión original (de abajo hacia arriba).