algorithm - seleccion - ¿Cuál es el beneficio de que un algoritmo de ordenamiento sea estable?
ordenamiento por seleccion c++ (10)
Se dice que un género es estable si mantiene el orden relativo de los elementos con las mismas claves. Supongo que mi pregunta es realmente, ¿cuál es el beneficio de mantener este orden relativo? ¿Alguien puede dar un ejemplo? Gracias.
Un algoritmo de clasificación es estable si conserva el orden de las claves duplicadas.
OK, bien, pero ¿por qué debería ser 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.
Digamos que está ordenando un conjunto de entrada que tiene dos campos y solo ordena 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 te 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 el resultado 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 te 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 segundo 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.
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 clasifica un campo a la vez, como 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 usarlo como un desempate cuando se le presenten claves equivalentes.
La mayor ventaja viene cuando la orden original tiene algún significado en sí misma. No pude encontrar un buen ejemplo, pero veo que JeffH hizo mientras pensaba en ello.
Le permite a su especie ''encadenarse'' en múltiples condiciones.
Supongamos 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:
- Smith, Alfred
- Smith, Zed
Se garantizará que esté en el orden correcto.
No siempre se pueden 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 determinística dada la misma entrada, que puede ser importante para la depuración y la prueba.
No todas las clasificaciones se basan en el valor completo. 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
Dado que los dos "John Smith" ya están "ordenados" (están en el orden en que los quiero), no quiero que cambien de posición. Si clasifico estos elementos por último, primero con un algoritmo de clasificación inestable, podría terminar con esto:
Last First Phone
-----------------------------
Adams Gabriel 533-5574
Smith John 123-4567
Smith John 012-3456
Wilson Peter 555-1212
Que 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 utilizara un algoritmo de clasificación estable, me garantizarían la primera opción, que es lo que busco.
Significa que si desea ordenar por álbum, Y por número de pista, puede hacer clic primero en Número de pista, y se ordena, luego, haga clic en Nombre de álbum y los números de pista permanecen en el orden correcto para cada álbum.
Un caso es cuando desea ordenar por 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 género no fuera estable, perdería el beneficio del primer tipo.
Una cola de prioridad es un ejemplo de esto. Digamos que tienes esto:
- (1, "bob")
- (3, "factura")
- (1, "jane")
Si ordena esto del número más pequeño al más grande, una ordenación inestable podría hacer esto.
- (1, "jane")
- (1, "bob")
- (3, "factura")
... pero luego "jane" se adelantó a "bob" a pesar de que se suponía que era al revés.
En general, son útiles para clasificar entradas múltiples en varios pasos.
Un ejemplo:
Supongamos que tiene una estructura de datos que contiene pares de números de teléfono y empleados que los llamaron. 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 otorgar una bonificación 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 correctos por número de teléfono obtengan la bonificación.