algorithm
Clasificación
Buscar..
Parámetros
| Parámetro | Descripción |
|---|---|
| Estabilidad | Un algoritmo de clasificación es estable si conserva el orden relativo de elementos iguales después de la clasificación. |
| En su lugar | Un algoritmo de clasificación está en su lugar si se ordena utilizando solo la memoria auxiliar O(1) (sin contar la matriz que se necesita clasificar). |
| La mejor complejidad del caso | Un algoritmo de clasificación tiene una complejidad en el mejor de los casos de O(T(n)) si su tiempo de ejecución es al menos T(n) para todas las entradas posibles. |
| Complejidad media del caso | Un algoritmo de clasificación tiene una complejidad de tiempo de caso promedio de O(T(n)) si su tiempo de ejecución, promediado en todas las entradas posibles , es T(n) . |
| Peor complejidad del caso | Un algoritmo de clasificación tiene una complejidad en el peor de los casos de O(T(n)) si su tiempo de ejecución es a lo sumo T(n) . |
Estabilidad en la clasificación
La estabilidad en la clasificación significa si un algoritmo de clasificación mantiene el orden relativo de las claves iguales de la entrada original en la salida del resultado.
Por lo tanto, 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 aparecen en la matriz de entrada sin clasificar.
Considere una lista de pares:
(1, 2) (9, 7) (3, 4) (8, 6) (9, 3)
Ahora vamos a ordenar la lista utilizando el primer elemento de cada par.
Una clasificación estable de esta lista dará como resultado la siguiente lista:
(1, 2) (3, 4) (8, 6) (9, 7) (9, 3)
Porque (9, 3) aparece después de (9, 7) en la lista original también.
Una clasificación inestable generará la siguiente lista:
(1, 2) (3, 4) (8, 6) (9, 3) (9, 7)
La clasificación inestable puede generar la misma salida que la clasificación estable pero no siempre.
Clases estables bien conocidas:
Clases inestables bien conocidas: