Sistemas electronicos
Páginas: 3 (549 palabras)
Publicado: 2 de diciembre de 2013
ORDENAMIENTO EXTERNO
INTERCALACIÓN (MERGE)
Estabilidad del algoritmo
Cuando los elementos iguales son indistinguibles, como con los enteros, o mas generalmente, cualquier dato en el que elelemento es la llave, la estabilidad no es un problema. 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 estecaso, el resultado puede ser dos ordenaciones posibles, 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)
Los ordenamientos inestables pueden cambiar el orden relativo, pero en el ordenamiento estable nunca sucede esto.
EFICIENCIA DEL ALGORITMO
MERGESORT es maseficiente que quicksort para algunos tipos de listas 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 forma secuencial 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 logn). Si el tiempo de ejecución de la intercalación para 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 mitadde 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 una cantidad muy grande de elementos y una lista de entrada ordenada aleatoriamente, el numero esperado (promedio) de comparaciones se aproxima α•n menos queel peor caso donde α es:
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...
INTERCALACIÓN (MERGE)
Estabilidad del algoritmo
Cuando los elementos iguales son indistinguibles, como con los enteros, o mas generalmente, cualquier dato en el que elelemento es la llave, la estabilidad no es un problema. 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 estecaso, el resultado puede ser dos ordenaciones posibles, 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)
Los ordenamientos inestables pueden cambiar el orden relativo, pero en el ordenamiento estable nunca sucede esto.
EFICIENCIA DEL ALGORITMO
MERGESORT es maseficiente que quicksort para algunos tipos de listas 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 forma secuencial 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 logn). Si el tiempo de ejecución de la intercalación para 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 mitadde 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 una cantidad muy grande de elementos y una lista de entrada ordenada aleatoriamente, el numero esperado (promedio) de comparaciones se aproxima α•n menos queel peor caso donde α es:
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...
Leer documento completo
Regístrate para leer el documento completo.