Mathematics">
Informacion Del Algoritmo Merge Sort A Nov 2021
Informacion Del Algoritmo Merge Sort A Nov 2021
Informacion Del Algoritmo Merge Sort A Nov 2021
Este algoritmo fue desarrollado por el matemático húngaro John Von Neumann en 1945. Consiste en dividir en dos partes
iguales el vector a ordenar, ordenar por separado cada una de las partes, y luego mezclar ambas partes, manteniendo el
orden, en un solo vector ordenado.
El algoritmo MergeSort (u Ordenamiento por mezcla) es un algoritmo que sirve para ordenar secuencias de datos. Utiliza los
siguientes tres pasos:
1) DIVIDIR: divide la secuencia de "n" elementos a ordenar en dos subsecuencias de "n/2" elementos cada una.
2) VENCER: ordena las dos subsecuencias de manera recursiva mediante el algoritmo MERGESORT.
FUNCIONAMIENTO
El completo de ellos, grupo de datos a ordenar es dividido en sus dos mitades pues es más sencillo ordenar una parte de los
datos que el conjunto cuando quede un solo dato en un subgrupo se termina el proceso de división pues ese subgrupo ya
está ordenado. A continuación, se mezclan ambas mitades ordenando los datos a medida que se combinan, para ello se
emplea un algoritmo sencillo que requiere un espacio auxiliar del tamaño del grupo original para añadir el dato
correspondiente de cada subgrupo así:
Se comparan entonces los elementos de la mitad 1 en la posición pos1 y de la mitad 2 en la posición pos2, el
menor se copia en ‘mezcla’ en la posición posMezcla, se incrementan las posiciones del origen que se ha
copiado (pos1 o pos2) y la del espacio de destino (posMezcla) y se compara el nuevo par de elementos;
finalmente alguna de las dos mitades habrá sido copiada completamente, entonces se debe copiar en el
espacio de mezcla los elementos que hayan quedado sin copiar de la otra mitad.
El método de mezcla realiza un número de comparaciones que aumenta linealmente con el número de
elementos a intercalar
Supongamos que “A” es una lista ordenada de “NA”=500 elementos y “B” es otra lista ordenada de “NB”=600 elementos. La
operación que combina los elementos de “A” y “B” en una única lista ordenada de N=(NA+NB) elementos, se llama mezcla.
Una forma sencilla de mezclar es colocar los elementos de B tras los elementos de A y entonces hacer uso de algún algoritmo
de ordenación u ordenamiento (burbuja o inserción para la lista entera).
Este método no saca ventaja del hecho de que A y B estén ya individualmente ordenados. El algoritmo de mezcla permite
ordenar dichas listas ordenadas aprovechando o sacando ventaja que de manera individual ya estaban ordenados.
Este tipo de ordenamiento es útil cuando se tiene una estructura ordenada y los nuevos datos a añadir se almacenan
en una estructura temporal para después agregarlos a la estructura original de manera que vuelva a quedar
ordenada
Este tipo de ordenamiento es útil cuando se tiene una estructura ordenada y los nuevos datos a añadir
se almacenan en una estructura temporal para después agregarlos a la estructura original de manera
que vuelva a quedar ordenada.
INTERFASE DE ORDENAMIENTO POR MEZCLA
**************
Pseudocódigo
Como ven, la idea es bastante simple, pero programarla no tanto. Para
no dar de golpe la solución, veamos primero un pseudocódigo del
algoritmo:
function mergesort(array A[x..y])
begin
if (x-y > 1)):
array A1 := mergesort(A[x..(int( x+y / 2))])
array A2 := mergesort(A[int(1+(x+y / 2))..y])
return merge(A1, A2) /*** llamada recursiva
else:
return A
end
else
if (p2 <= n2 and A1[p1] > A2[p2]):
R[p1 + p2] := A2[p2]
p2 := p2 + 1
return R
end
TAREA A REALIZAR DEL ALGORITMO MERGE-SORT…. C/U DEBE CREAR UN PROGRAMA: