Solo me pregunto si alguien podría explicar por qué un "tipo inestable" se considera malo? Básicamente, no veo ninguna situación en la que realmente importe. ¿Alguien podría importar proporcionar uno?¿Por qué se considera que un "tipo inestable" es malo
Si tiene una GUI que permite a las personas ordenar en columnas individuales haciendo clic en esa columna, y utiliza una clasificación estable, las personas que la conocen pueden ordenarlas en varias columnas A, B, C haciendo clic en las columnas C, B, A en ese orden. Debido a que el género es estable, al hacer clic en B, los registros con las mismas teclas debajo de B seguirán ordenados por C, de modo que después de hacer clic en B los registros se ordenan por B, C. De manera similar, después de hacer clic en A, se ordenan los registros por A, B, C.
(Lamentablemente, la última vez que probé esto en un producto de Microsoft u otro, parecía que no usaba un tipo estable, por lo que no es sorprendente que este truco no se conozca mejor).
Buen ejemplo. ¿Pero quiere decir que hay un producto de Microsoft que no es estable? ¡Chocante! :) –
Me alegro de leer esto. no se me ocurrió que tal cosa no usaría un tipo confiable. –
¿Pero no se puede estabilizar una clasificación inestable agregando un Rownum/índice u otro tipo de contador único como último elemento de una clave de clasificación compuesta? A menos que me esté perdiendo algo, agregar eso parece trivial. – drake7707
Imagine que quería organizar una baraja de cartas. Puede ordenar primero por palo, luego por valor numérico. Si usabas un tipo estable, habrías terminado. Si usabas un ordenamiento inestable, estaría en orden numérico, pero los trajes se volverían a estropear de nuevo. Hay muchas situaciones equivalentes que surgen en problemas reales de desarrollo.
No creo que esta sea una comparación realmente buena, ya que tanto la demanda como el número deben tenerse en cuenta para cualquier función de comparación. También tenga en cuenta que si utiliza un método de clasificación estable para esto, tendría que ordenar por número y luego adaptarse, pero no a la inversa. –
No te estoy siguiendo, @Billy. En primer lugar, necesitaría una función de comparación que tuviera en cuenta ambas cosas si, y solo si, no tenía una clasificación estable. De lo contrario, podría tener una función de comparación simple del tipo que, en los lenguajes dinámicos, puede escribirse genéricamente para ordenar por una propiedad por su nombre. Y en segundo lugar, parece sentir que solo hay una forma de organizar un mazo de cartas. Te aseguro que "organizar" puede ser interpretado de múltiples maneras. –
Hay solo unos pocos casos en los que necesita un algoritmo de ordenamiento que sea estable. Un ejemplo de esto es si está implementando algo así como un ordenamiento de Radix, que depende de la idea de que el algoritmo de clasificación de comparación utilizado como elemento esencial es estable. (El género Radix puede funcionar en tiempo lineal, pero sus entradas son más restringidas que los algoritmos de clasificación de comparación. (Los tipos de comparación requieren O (n lg n) tiempo))
No es necesariamente que un tipo que es inestable sea "malo" ; es más que un tipo que es estable es "deseable en algunos casos". Es por eso que los lenguajes de programación, p. La Biblioteca de plantillas estándar de C++, proporciona ambas, p. std::sort y std::stable_sort - que le permiten especificar cuándo necesita estabilidad y cuándo no.
@Downvoter: ¿Qué pasa exactamente con esta respuesta? –
No tengo idea de quién votó negativamente, pero supongo que encontraron que su ejemplo de utilizar un género estable para realizar otro tipo es algo atípico. – Mehrdad
"que depende de la idea de que el algoritmo de clasificación [basado en la comparación] utilizado como elemento esencial es estable" - ¿a qué se refiere? ¿Cuál es el 'bloque de construcción' de clasificación de radix y por qué necesita ser estable? Independientemente de si eso tiene sentido o no, un género no es exactamente un buen ejemplo de por qué un tipo estable es deseable en algunos casos. – Dukeling
Debido a que pueden hacerlo mejor de lo que podía hacer ... desde Developer Fusion:
Hay dos tipos de algoritmos de clasificación : "Clasifica estable" y "ordena inestables". Estos términos se refieren a la acción que se toma cuando dos valores se comparan como iguales. Si usted tiene una serie T0..size con dos elementos Tn y TK para < n k, y estos dos elementos comparar iguales, en un ordenación estable que aparecerán en la ordenados de salida con el valor que estaba en Tn anterior Tk. La orden de salida conserva el orden de entrada original. Una clasificación inestable de , por el contrario, existe sin garantía del orden de estos dos elementos en la salida.
Tenga en cuenta que los algoritmos de ordenación como la ordenación rápida no son estables o inestables. La implementación determinará cuál es.
En cualquier caso, estable no es necesariamente mejor o peor que inestable, es solo que a veces se necesita la garantía del pedido para dos elementos iguales. Cuando hace necesita esa garantía, inestable no sería adecuado.
Creo que el OP entiende cuál es la diferencia entre los dos tipos de géneros. Él pregunta por qué un tipo que es inestable sería "malo", lo que implica que (s) sabe qué hace que un tipo sea inestable. –
@Billy - Muy cierto. Supongo que, a los fines de una mejor respuesta, quería explicar de qué se trata, así que podría decir mi último párrafo: uno no es necesariamente "malo" o "bueno", excepto en un caso específico. – JasCav
¿Quién lo considera "malo"? ¿Tiene una cita o una referencia o un enlace? Ayudaría tener un contexto para este tipo de juicio de valor. –
posible duplicado de [¿Cuál es el beneficio de que un algoritmo de ordenamiento sea estable?] (Http://stackoverflow.com/questions/808617/what-is-the-benefit-for-a-sort-algorithm-to-be -stable) – nawfal