Merge sort
-
Upload
cristian-hernandez -
Category
Documents
-
view
41 -
download
4
description
Transcript of Merge sort
![Page 1: Merge sort](https://reader033.fdocumento.com/reader033/viewer/2022061111/5455e9ffaf7959fe018b63d6/html5/thumbnails/1.jpg)
![Page 2: Merge sort](https://reader033.fdocumento.com/reader033/viewer/2022061111/5455e9ffaf7959fe018b63d6/html5/thumbnails/2.jpg)
Merge Sort
• Este algoritmo tambien es llamado de Intercalación o combinación, debido que combina (intercala) dos estructuras previamente ordenadas.
![Page 3: Merge sort](https://reader033.fdocumento.com/reader033/viewer/2022061111/5455e9ffaf7959fe018b63d6/html5/thumbnails/3.jpg)
Historia Fue desarrollado en 1945 por John Von Neumann.Conceptualmente, el ordenamiento por mezcla
funciona de la siguiente manera:
Si la longitud de la lista es 0 ó 1, entonces ya está ordenada. En otro caso:
Dividir la lista desordenada en dos sublistas de aproximadamente la mitad del tamaño.
Ordenar cada sublista recursivamente aplicando el ordenamiento por mezcla.
Mezclar las dos sublistas en una sola lista ordenada.
![Page 4: Merge sort](https://reader033.fdocumento.com/reader033/viewer/2022061111/5455e9ffaf7959fe018b63d6/html5/thumbnails/4.jpg)
![Page 5: Merge sort](https://reader033.fdocumento.com/reader033/viewer/2022061111/5455e9ffaf7959fe018b63d6/html5/thumbnails/5.jpg)
Merge Sort Supongamos los siguientes vectores
previamente ordenados, el nuevo vector contendra la cantidad de elementos de ambos
3 5 8 12 17 1 6 9 24
Se comparan los primeros elementos 3 y 1, el menor se copia
![Page 6: Merge sort](https://reader033.fdocumento.com/reader033/viewer/2022061111/5455e9ffaf7959fe018b63d6/html5/thumbnails/6.jpg)
Merge Sort
3 5 8 12 17 1 6 9 24
1
Se comparan los siguientes valores 3 y 6, se mueve el menor
Se copia el valor del vector B y los subindices K y J, se mueven una posición
![Page 7: Merge sort](https://reader033.fdocumento.com/reader033/viewer/2022061111/5455e9ffaf7959fe018b63d6/html5/thumbnails/7.jpg)
Merge Sort
3 5 8 12 17 1 6 9 24
1 3
Se comparan los siguientes valores 5 y 6, se mueve el menor
Se copia el valor del vector A y los subindices K e I, se mueven una posición
![Page 8: Merge sort](https://reader033.fdocumento.com/reader033/viewer/2022061111/5455e9ffaf7959fe018b63d6/html5/thumbnails/8.jpg)
Merge Sort
3 5 8 12 17 1 6 9 24
1 3 5
Se comparan los siguientes valores 8 y 6, se mueve el menor
Se copia el valor del vector A y los subindices K e I, se mueven una posición
![Page 9: Merge sort](https://reader033.fdocumento.com/reader033/viewer/2022061111/5455e9ffaf7959fe018b63d6/html5/thumbnails/9.jpg)
Merge Sort
3 5 8 12 17 1 6 9 24
1 3 5 6
Se comparan los siguientes valores 8 y 9, se mueve el menor
Se copia el valor del vector B y los subindices K y J, se mueven una posición
![Page 10: Merge sort](https://reader033.fdocumento.com/reader033/viewer/2022061111/5455e9ffaf7959fe018b63d6/html5/thumbnails/10.jpg)
Merge Sort
3 5 8 12 17 1 6 9 24
1 3 5 6 8
Se comparan los siguientes valores 12 y 9, se mueve el menor
Se copia el valor del vector A y los subindices K e I, se mueven una posición
![Page 11: Merge sort](https://reader033.fdocumento.com/reader033/viewer/2022061111/5455e9ffaf7959fe018b63d6/html5/thumbnails/11.jpg)
Merge Sort
3 5 8 12 17 1 6 9 24
1 3 5 6 8 9
Se comparan los siguientes valores 12 y 24, se mueve el menor
Se copia el valor del vector B y los subindices K y J, se mueven una posición
![Page 12: Merge sort](https://reader033.fdocumento.com/reader033/viewer/2022061111/5455e9ffaf7959fe018b63d6/html5/thumbnails/12.jpg)
Merge Sort
3 5 8 12 17 1 6 9 24
1 3 5 6 8 9 12
Se comparan los siguientes valores 17 y 24, se mueve el menor
Se copia el valor del vector A y los subindices K e I, se mueven una posición
![Page 13: Merge sort](https://reader033.fdocumento.com/reader033/viewer/2022061111/5455e9ffaf7959fe018b63d6/html5/thumbnails/13.jpg)
Merge Sort
1 3 5 6 8 9 12 17 24
El proceso termina cuando uno de los dos subindices I o J, llega hasta la longitud del vector. En ese momento se termina de copiar los siguientes valores del vector
De igual forma se sigue con los siguientes valores hasta completar el recorrido
![Page 14: Merge sort](https://reader033.fdocumento.com/reader033/viewer/2022061111/5455e9ffaf7959fe018b63d6/html5/thumbnails/14.jpg)
VENTAJAS
Método estable de ordenamiento mientras la operación de mezclas (merge) este bien implementada.
Este algoritmo es efectivo para conjuntos de datos que se puedan acceder como arreglos , vectores y listas ligadas.
![Page 15: Merge sort](https://reader033.fdocumento.com/reader033/viewer/2022061111/5455e9ffaf7959fe018b63d6/html5/thumbnails/15.jpg)
DESVENTAJAS
Su principal desventaja radica en que esta definido recursivamente y su implementación no recursiva emplea una pila , por lo que requiere un espacio adicional de memoria para almacenarla.
![Page 16: Merge sort](https://reader033.fdocumento.com/reader033/viewer/2022061111/5455e9ffaf7959fe018b63d6/html5/thumbnails/16.jpg)
http://ingecomp.mforos.com/674005/3017040-animacion-de-algoritmos-de-ordenamiento-resubido/
![Page 17: Merge sort](https://reader033.fdocumento.com/reader033/viewer/2022061111/5455e9ffaf7959fe018b63d6/html5/thumbnails/17.jpg)
Merge SortInicio combina( A : vector ; B : vector)Crear Vector C con longitudes de A y BI 1J 1K 1Mientras (I < longitud A) y (j < longitud B) hacer Si A[ I ] < B[ J ] entonces
C[ K ] A[ I ]K K + 1I I + 1
de lo contrarioC[ K ] B[ J ]K K + 1J J + 1
fin hacer
Mientras (I < longitud A) hacerC[ K ] A[ I ]K K + 1I I + 1
Mientras (J < longitud B) hacerC[ K ] B[ J ]K K + 1J J + 1
Fin combina
![Page 18: Merge sort](https://reader033.fdocumento.com/reader033/viewer/2022061111/5455e9ffaf7959fe018b63d6/html5/thumbnails/18.jpg)
Merge Sort Se puede utilizar este algoritmo para
ordenar un vector.
Inicio MergeSort( A : vector ; liminf : entero ; limsup: entero) Si (liminf = limsup) entonces finalizarde lo contrario medio liminf + limsup / 2 (combina (MergeSort (A , liminf, medio), MergeSort( A , medio, limsup))Fin Inicio