Intercalcion directa
Páginas: 3 (540 palabras)
Publicado: 1 de diciembre de 2010
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...
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...
Leer documento completo
Regístrate para leer el documento completo.