Se dice que un género es estable si mantiene el orden relativo de los elementos con las mismas teclas. Supongo que mi pregunta es realmente, ¿cuál es el beneficio de mantener este orden relativo? ¿Alguien puede dar un ejemplo? Gracias.¿Cuál es el beneficio de que un algoritmo de ordenamiento sea estable?
No todas las clasificaciones se basan en el valor total. Considera una lista de personas. Es posible que solo desee ordenarlos por sus nombres, en lugar de toda su información. Con un algoritmo de clasificación estable, sé que si tengo dos personas llamadas "John Smith", se conservará su orden relativa.
Last First Phone
-----------------------------
Wilson Peter 555-1212
Smith John 123-4567
Smith John 012-3456
Adams Gabriel 533-5574
Puesto que los dos s "John Smith" ya están "ordenados" (que están en el orden de los quiero), no voy a querer que cambiar de posición. Si se clasifican estos materiales por último, a continuación, en primer lugar con un algoritmo de ordenación inestable, podría acabar bien con esto:
Last First Phone
-----------------------------
Adams Gabriel 533-5574
Smith John 123-4567
Smith John 012-3456
Wilson Peter 555-1212
¿Qué es lo que quiero, o podría terminar con esto:
Last First Phone
-----------------------------
Adams Gabriel 533-5574
Smith John 012-3456
Smith John 123-4567
Wilson Peter 555-1212
(Verá que los dos "John Smith" han cambiado de lugar). Esto no es lo que quiero.
Si utilicé un algoritmo de clasificación estable, tendría garantizada la primera opción, que es lo que busco.
Una cola de prioridad es un ejemplo de esto. Digamos que tiene esto:
Si ordena esto desde pequeña al mayor número, un tipo inestable podría hacer esto.
... pero entonces "Jane" se adelantó "bob" a pesar de que se suponía que era al revés.
Generalmente, son útiles para ordenar entradas múltiples en varios pasos.
Un algoritmo de clasificación es estable si conserva el orden de las claves duplicadas.
Bien, bien, pero ¿por qué debería ser tan importante? Bueno, la cuestión de la "estabilidad" en un algoritmo de clasificación surge cuando deseamos ordenar los mismos datos más de una vez de acuerdo con diferentes claves.
A veces los elementos de datos tienen varias claves. Por ejemplo, tal vez una clave primaria (única) como un número de seguro social o un número de identificación de estudiante, y una o más claves secundarias, como la ciudad de residencia o la sección de laboratorio. Y es posible que deseemos ordenar esos datos de acuerdo con más de una de las claves. El problema es que si clasificamos los mismos datos de acuerdo con una clave, y luego según una segunda clave, la segunda clave puede destruir la ordenación lograda por la primera clasificación. Pero esto no sucederá si nuestro segundo tipo es estable.
No he votado negativamente, pero todo lo que hizo fue copiar datos de un sitio web. Otros realmente se tomaron la molestia de explicar el problema, entonces tal vez por eso. No me parece que valga la pena, pero otros podrían pensarlo. –
Eso, IMO, no reinventar la rueda y también citar con la atribución adecuada. YMMV. – dirkgently
Upvoted; una cita concisa y un enlace a la fuente acreditada es mejor que muchas respuestas que flotan en este lugar. – Kevin
Uno de los casos es cuando se desea ordenar varias claves. Por ejemplo, para ordenar una lista de pares de nombre/apellido, primero puede ordenar por el primer nombre y luego por el apellido.
Si su ordenación no era estable, perdería el beneficio del primer tipo.
Significa que si desea ordenar por álbum, Y por número de pista, puede hacer clic primero en el número de pista y ordenarlo, luego haga clic en Nombre de álbum y los números de pista permanecen en el orden correcto para cada álbum.
Me pregunto cuántas personas se dan cuenta de que funciona de esta manera? Parece casi una notación polaca inversa. –
Le permite a su clase 'encadenarse' en múltiples condiciones.
Digamos que tiene una tabla con los nombres y apellidos en orden aleatorio. Si ordena por nombre y luego por apellido, el algoritmo de clasificación estable garantizará que las personas con el mismo apellido se clasifiquen por nombre.
Por ejemplo:
sea firme para estar en el orden correcto.
¿Por qué no incluir este nombre y apellido en el predicado de comparación? Luego debes ordenar solo una vez. – SebastianK
Es útil cuando no se conocen las condiciones con anticipación. Imagine una vista de lista donde el usuario hace clic en una columna para ordenar, y luego hace clic en otra columna para ordenar más. –
Un ejemplo:
Digamos que tiene una estructura de datos que contiene los pares de números telefónicos y los empleados que los llamó. Se agrega un registro de número/empleado después de cada llamada. Algunos empleados pueden llamar a algunos números telefónicos.
Además, supongamos que desea ordenar la lista por número de teléfono y dar un bono a las primeras 2 personas que llamaron a un número determinado.
Si ordena con un algoritmo inestable, no puede conservar el orden de las personas que llaman de un número determinado, y los empleados incorrectos podrían recibir la bonificación.
Un algoritmo estable asegura que los 2 empleados adecuados por número de teléfono obtengan la bonificación.
Hasta el punto de respuesta que estaba buscando. – bharatj
La ventaja de la clasificación estable para múltiples claves es dudosa, siempre puede usar una comparación que compare todas las claves a la vez. Es solo una ventaja si está ordenando un campo a la vez, ya que al hacer clic en el encabezado de una columna - Joe Koberg da un buen ejemplo.
Cualquier tipo se puede convertir en un tipo estable si puede permitirse agregar un número de secuencia al registro y utilizarlo como un desempate cuando se le presenten claves equivalentes.
La mayor ventaja se obtiene cuando el orden original tiene algún significado en sí mismo. No pude encontrar un buen ejemplo, pero veo que JeffH lo hizo mientras pensaba en ello.
Digamos que está ordenando en un conjunto de entrada que tiene dos campos, y que solo ordena en el primero. El '|' personaje divide los campos.
En el conjunto de entrada tiene muchas entradas, pero, tiene 3 entradas que se parecen a
. . . AAA | remolque . . . AAA | alquiler de coches . . . AAA | plomería . . .
Ahora, cuando termine de ordenar, espera que todos los campos con AAA estén juntos.
Un tipo estable le dará: . . . AAA | remolque AAA | alquiler de coches AAA | plomería . . .
es decir, los tres registros que tenían la misma clave de clasificación, AAA, están en el mismo orden en la salida que estaban en la entrada. Tenga en cuenta que no están ordenados en el segundo campo, porque no ordenó en el segundo campo en el registro.
Un tipo inestable le dará: . . . AAA | plomería AAA | alquiler de automóviles AAA | remolque . . .
Tenga en cuenta que los registros todavía se ordenan solo en el primer campo, y el orden del campo difiere del orden de entrada.
Un tipo inestable tiene el potencial de ser más rápido. Un tipo estable tiende a imitar lo que las personas que no son informáticos/no matemáticos tienen en mente cuando clasifican algo. Es decir, si hiciera una ordenación por inserción con tarjetas de índice, lo más probable es que tenga una clasificación estable.
No siempre puede comparar todos los campos a la vez. Un par de ejemplos: (1) límites de memoria, donde está ordenando un archivo de disco grande, y no hay espacio para todos los campos de todos los registros en la memoria principal; (2) Ordenando una lista de punteros de clase base, donde algunos de los objetos pueden derivarse subclases (solo tiene acceso a los campos de clase base).
Además, los géneros estables tienen una salida determinista dada la misma entrada, que puede ser importante para la depuración y la prueba.
upvoted; nadie más mencionó, preservación de pedidos "relativos". – techtrainer