Merge Sort
-
Upload
humbertorayados -
Category
Technology
-
view
56 -
download
4
description
Transcript of Merge Sort
Ordenamiento de Mezcla
Dra. Elisa Schaeffer Algoritmos ComputacionalesHumberto Treviño Delgado 1495798
MERGE SORT
El ordenamiento del que hablaremos hoy, será el de Mezcla (merge sort), este es destacado por su técnica: divide y vencerás.
DESCRIPCION
Este ordenamiento fue desarrollado en 1945 por John Von Neumann
Merge sort es un ordenamiento estable, paraleliza mejor, y es más eficiente manejando medios secuenciales de acceso lento.
Merge sort es a menudo la mejor opción para ordenar una lista enlazada.
DESCRIPCION
Es fácil implementar merge sort de manera que sólo requiera Θ(1) espacio extra, y el mal rendimiento de las listas enlazadas ante el acceso aleatorio hace que otros algoritmos (como quicksort) den un bajo rendimiento, y para otros (como heapsort) sea algo imposible.
COMPLEJIDAD
El ordenamiento merge sort es de complejidad O(n log n).
Merge sort
Para empezar a entender un poco mejor el ordenamiento de mezcla observemos la animación.
Merge sort
Como pudimos ver en la imagen , lo que hace este metodo, es divir en 2 partes el arreglo, despues en otras 2 y asi hasta tener los elementos separados. Comparamos los elementos y escribimos el menor. Volvemos a comparar y asi hasta tener nuestro arreglo acomodado.
Merge sort
Para entender mejor lo anterior hay que observar la imagen y la animacion.
Merge sort
Divide y venceras
Pseudocódigo
Existen diversos lenguajes en los que se puede programar este ordenamiento, mas adelante esta nuestro código escrito en C.
Aplicaciones del Merge Sort
El ordenamiento de mezcla (merge sort) puede ser utilizado para:
●Para correr cintas magnéticas como dispositivos de entrada y salida, requiere muy poca memoria, y la memoria que requiere no depende del numero de grabaciones.
Los algoritmos de ordenamiento de mezcla permitieron a juegos de datos grandes para ser clasificados para los tempranos ordenadores que tenían pequeñas memorias de acceso arbitrarias por normas modernas. Los registros fueron almacenados sobre la cinta magnética y procesados sobre los bancos de unidades de cinta magnética magnéticas, como esta IBM 729s.
Analisis Asintotico
La relación de recurrencia del algoritmo es T(1) = 1, T(n) = 2 T(n/2) + n, cuya solución es T(n) = n lg n.
Suponiendo que se tiene un arreglo de 8 elementos, se ordenan los 4 elementos de cada arreglo y luego se mezclan. El arreglo de 4 elementos, se ordenan los 2 elementos de cada arreglo y luego se mezclan. El arreglo de 2 elementos, como cada arreglo sólo tiene n = 1 elemento, solo se mezclan.
Ejemplos (animaciones)
Ejemplos (animaciones)
Referencias
http://sistemas.ing.ula.ve/pr3/unidad_1/actividad/actividad2_6.html
http://es.wikipedia.org/wiki/Ordenamiento_por_mezcla
http://en.wikipedia.org/wiki/Merge_sort