Merge Sort
jueves, 24 de mayo de 2012
Ventajas y Desventajas
- Método de ordenamiento estable mientras la función de mezcla sea implementada correctamente.
- Muy estable cuando la cantidad de registros a acomodar es de índice bajo, en caso contrario gasta el doble del espacio que ocupan inicialmente los datos.
- Efectivo para conjunto de datos a los que se puede acceder secuencialmente (arreglos, vectores, etc.)
- Principal desventaja: está definido recursivamente. Si se deseara implementarla no recursivamente se tendría que emplear una pila y se requeriría un espacio adicional de memoria para almacenarla.
Tiempo de ejecución
No hay más que
log2n pasadas en este algoritmo, y cada
una implica n o menos comparaciones. Por lo tanto, requiere no menos de n log2 n comparaciones.
En el peor de
los casos, Mergesort NUNCA requiere mas de n log2 n.
Divide y Vencerás
Consiste en dividir en dos partes el vector a ordenar, ordenar por separado cada una de esas partes y finalmente
mezclar ambas partes, manteniendo el orden en un solo vector ordenado.
Este algoritmo es una estrategia básica de “Divide y vencerás”.
- DIVIDIR: Divide la secuencia de “n” elementos a ordenar en dos subsecuencias de “n/2” elementos cada una.
- VENCER: Ordena las dos subsecuencias en una sola de manera recursiva.
Antecedentes
El algoritmo de Merge Sort fue desarrollado por el matemático húngaro John Von Neumann en 1945.
Éste algoritmo sirve para ordenar secuencias de datos. También se le conoce como Método de Intercalación o Método de Combinación.
Suscribirse a:
Entradas (Atom)