Intercalcion directa

Solo disponible en BuenasTareas
  • Páginas : 3 (540 palabras )
  • Descarga(s) : 0
  • Publicado : 1 de diciembre de 2010
Leer documento completo
Vista previa del texto
Estabilidad del algoritmo
Cuando los elementos iguales son indistinguibles, como con los enteros, o mas generalmente, cualquier dato en el que el elemento es la llave, la estabilidad no es unproblema. Sin embargo, asumamos que los siguientes pares de números se van a ordenar por su primera componente:
(4, 1)  (3, 7)  (3, 1)  (5, 6)

En este caso, el resultado puede ser dos ordenacionesposibles, uno que mantiene el orden relativo de los registros con llaves iguales y otro que no:

(3, 7)  (3, 1)  (4, 1)  (5, 6) (Se mantiene)
(3, 1)  (3, 7)  (4, 1)  (5, 6) (Se cambia)

Losordenamientos inestables pueden cambiar el orden relativo, pero en el ordenamiento estable nunca sucede esto. 
 
Eficiencia del algoritmo
MERGESORT es mas eficiente que quicksort  para algunos tipos delistas con datos a ordenar que pueden ser solamente accesadas eficientemente de manera secuencial, y esto es popular en lenguajes de programación como LISP, donde  el acceso a estructuras de datos de formasecuencial es muy común.

Análisis de complejidad
Al ordenar n elementos, este ordenamiento tiene un tiempo promedio y de un peor caso de O(n log n). Si el tiempo de ejecución de la intercalaciónpara una lista de tamaño n es T(n), entonces

 T(n) = 2T(n/2) + n
siguiendo la definición del algoritmo (aplicar el algoritmo a dos listar de la mitad de tamaño de la lista original, y añadir los n pasos necesarios para mezclar el resultado en dos listas). 
En el peor caso hace:  (n ⌈lg n⌉ - 2⌈lg n⌉ + 1)  comparaciones, lo que es entre  (n lg n - n + 1) y (n lg n + n + O(lg n)). 
Para unacantidad muy grande de elementos y una lista de entrada ordenada aleatoriamente, el numero esperado (promedio) de comparaciones se aproxima  α·n menos que el peor caso donde  α es:
[pic]Intercalación en dispositivos de memoria externa
La intercalación directa es un método de ordenación inherentemente secuencial y debido a esto es muy practico para 
usarse en dispositivos de almacenamiento...
tracking img