Trabajar con el tipo de inserción es lo primero que viene a la mente. Sin embargo, la ordenación por inserción tiene dos operaciones principales: asignaciones de elementos y comparaciones de elementos. El costo total del tipo de inserción sería la suma de los costos de estas dos operaciones principales.
Más aún, se puede seguir el siguiente algoritmo de fusión modificado. En primer lugar, encontrará el elemento fuera de servicio y lo colocará en una variable auxiliar. Luego lo fusionará con los otros elementos utilizando el conocido algoritmo de fusión. El pseudocódigo se da a continuación. El primer ciclo costará O (n) y el algoritmo de fusión también costará O (n). Sin embargo, el costo total es [matemática] O (2n) = O (n) [/ matemática]
para i = 2 a n
si (A [i]> A [i-1])
aux1.add (A [i])
más
out_of_order_el = A [i]
descanso
terminara si
fusionar (aux1, aux2)
- Cómo calcular coeficientes binomiales para números muy grandes
- ¿La recursividad es más rápida que los bucles en MATLAB?
- ¿Cuáles son los algoritmos de nivel básico con los que debemos comenzar y cuáles son los algoritmos avanzados que debemos estudiar?
- ¿Cuál es el algoritmo utilizado para llenar el tablero en el juego Bejeweled Blitz?
- ¿Existen buenos libros o recursos para resolver problemas y algoritmos en C #, para la preparación de entrevistas SDET?
La observación final es que el algoritmo de fusión es solo la parte de fusión del algoritmo de clasificación de fusión.
