Ordenamiento Por Mezcla

1.
Introduccin
Es sabido que las estructuras de datos son utilizadas para guardar informacin, luego
para recuperar esta informacin es necesario que este ordenada de manera eficiente,
es aqu donde son introducidos los Algoritmos de Ordenamiento.
Los Algoritmos de Ordenamientos son mtodos para ordenar las diferentes estructuras
de datos bsicas, nos permite cambiar el orden (posicin) de los elementos para
dejarlos ordenados segn un criterio fijo (numricamente, de menor a mayor, de
mayor a menor, etc.).
A continuacin los invitamos a conocer el Algoritmo de ordenamiento llamado

MergeSort, uno de los buenos algoritmos de ordenamientos visto en el curso
Computacin I.
2. Marco terico
MergeSort (u Ordenamiento por mezcla) es uno de los Algoritmos de Ordenamientos

ms eficientes que existen, fue creado en 1945 por John Von Neumann, el cual se
encuentra entre los ms grandes matemticos del siglo XX con conocimientos en
economa y ciencias de la computacin.
El Algoritmo MergeSort 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.
Utiliza los siguientes tres pasos:
Dividir: Divide la secuencia de n elementos a ordenar en dos subsecuencias de n/2

elementos cada una, pues es ms sencillo ordenar una parte de los datos que el
conjunto completo de ellos.
Ordenar: Ordena las dos subsecuencias de manera recursiva mediante el algoritmo

MergeSort, comparando cada elemento de las subsecuencias.
Combinar: Combina las dos subsecuencias ordenadas para generar la solucin, cuando
quede un solo dato en un subgrupo se termina el proceso de divisin pues ese
subgrupo ya est ordenado.
La caracterstica principal de MergeSort es la eficiencia que posee en tiempo de

ejecucin en comparacin con otros algoritmos, ya que su manera de trabajo por
grupos pequeos agiliza la organizacin de los datos, su utilizacin se da con mucha
frecuencia cuando la cantidad de registros no es muy grande ya que para hacer las
mezclas ste mtodo utiliza el doble del espacio que gasta el arreglo original de
valores.
Una gran ventaja del MergeSort es que su algoritmo tiene mucha estabilidad (se evitan
los problemas de intercambio de claves en la manipulacin de datos).
Su principal desventaja radica en que est definido recursivamente y su

implementacin no recursiva emplea una pila, por lo que requiere un espacio adicional
de memoria para almacenarla, gasta el doble de espacio del que ocupan inicialmente
los datos.
2.1 Anlisis
Como cualquiera de los algoritmos de ordenamiento recursivo tiene complejidad

logartmica: O(n log2n).
Si el tiempo de ordenamiento de MergeSort para una lista de n elementos es T(n)

entonces la repeticin T(n) = 2T( n/2 ) + n sigue de la definicin del algoritmo (Aplicar
el algoritmo a las dos listas de la mitad del tamao de la lista original y aumentar los n
pasos tomados para utilizar MergeSort en las dos listas resultantes).
Algoritmo de ordenacin :
Solucin de la ecuacin T (n) = 2T (n/2) + O(n)
2.2 Funcionamiento
El proceso de este algoritmo es fusionar sucesivamente mitades ya ordenadas de

datos:
El grupo de datos a ordenar es dividido en sus dos mitades pues es ms sencillo

ordenar una parte de los datos que el conjunto completo de ellos, cuando quede un
solo dato en un subgrupo se termina el proceso de divisin pues ese subgrupo ya est
ordenado.
Se comparan entonces los elementos de la mitad 1 en la posicin pos1 y de la mitad 2

en la posicin pos2, el menor se copia en mezcla en la posicin 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.
2.3 Caractersticas
La eficiencia de este algoritmo es bastante notable en tiempo de ejecucin en
comparacin con otros, ya que su manera de trabajo por grupos pequeos agiliza la
organizacin de los datos.
Su utilizacin se da con mucha frecuencia cuando la cantidad de registros no es muy

grande ya que para hacer las mezclas ste mtodo utiliza el doble del espacio que
gasta el arreglo original de valores.
2.4 Ventajas
A diferencia de algunas versiones mejoradas del QuickSort, MergeSort es un mtodo

estable de ordenamiento mientras la operacin de mezcla (Merge) sea implementada
correctamente.
Una gran ventaja del MergeSort es que su algoritmo tiene mucha estabilidad (se evitan
los problemas de intercambio de claves en la manipulacin de datos). En la gestin de
Bases de Datos se utiliza comnmente cuando la cantidad de registros en el ndice es
relativamente baja, ya que en caso contrario es poco productivo debido a que gasta el
doble de espacio del que ocupan inicialmente los datos.
2.5 Desventajas
Su principal desventaja radica en que est definido recursivamente y su

implementacin no recursiva emplea una pila, por lo que requiere un espacio adicional
de memoria para almacenarla.
A los algoritmos que realizan el proceso de ordenamiento dentro del mismo vector se
les denomina algoritmos de ordenamiento "in-situ", el algoritmo de MergeSort no
pertenece a esta familia ya que no utiliza el espacio sobre el que estn almacenados
los datos sino que para poder funcionar requiere de un espacio de memoria adicional
del tamao de los datos a ordenar en el cual se realicen las mezclas.
2.6. Grado de Complejidad
Esta es la tabla de comparacin del grado de complejidad entre los otros

ordenamientos.
Metodo Complejidad
Burbuja n2
Insercin n2
Seleccin n2
Montculo nlog2n
Fusion nlog2n
Shell nlog2n
Quicksort nlog2n
3. Marco Practico
Merge Sort est basado en la tcnica de diseo de algoritmos Divide y Vencers, de la

cual se habl aqu mismo hace un tiempo. Recordando un poco, esta tcina consiste en
dividir el problema a resolver en subproblemas del mismo tipo que a su vez se
dividirn, mientras no sean suficientemente pequeos o triviales.
Veamos una panormica de la estrategia que sigue este algoritmo para ordenar una
secuencia S de n elementos:
Si S tiene uno o ningn elemento, est ordenada
Si S tiene al menos dos elementos se divide en dos secuencias S1 y S2
S1 contiene los primeros n/2 elementos y S2 los restantes
Ordenar S1 y S2, aplicando recursivamente este procedimiento
Mezclar S1 y S2 en S, de forma que ya S1 y S2 estn ordenados
Veamos ahora como sera la estrategia para mezclar las secuencias:
Se tienen referencias al principio de cada una de las secuencias a mezclar (S1 y S2).
Mientras en alguna secuencia queden elementos, se inserta en la secuencia resultante
(S) el menor de los elementos referenciados y se avanza esa referencia una posicin.
3.1 Codigo
#include "stdafx.h"
void mergesort(int *v, int i, int f);
void merge(int *v, int i, int m, int f);
int _tmain(int argc, _TCHAR* argv[])

{
int *v, n;
printf("Ingrese N: ");
scanf("%d", &n);
v = new int[n];
for(int i=0; i<n; i++)
{
printf("Elemento %d: ", i+1);
scanf("%d", &v[i]);
}
mergesort(v, 0, n-1);
for(int i=0; i<n; i++)

printf("%d ", v[i]);
return 0;
}
void mergesort(int *v, int i, int f)

{
if(i!=f)
{
int m = (i+f)/2;
mergesort(v, i, m);
mergesort(v, m+1, f);
merge(v, i, m, f);
}
}
void merge(int *v, int i, int m, int f) {
int *aux = new int[m-i+1];
for(int j=i; j<=m; j++)
aux[j-i] = v[j];
int c1=0, c2=m+1;

for(int j=i; j<=f; j++) {
if(aux[c1] < v[c2]) {
v[j] = aux[c1++];
if(c1==m-i+1)
for(int k=c2; k<=f; k++)
v[++j] = v[k];
}
else {
v[j] = v[c2++];
if(c2==f+1)
for(int k=c1; k<=m-i; k++)
v[++j] = aux[k];
}
}
}
4. Conclusiones
Los Algoritmos de Ordenamientos son mtodos para ordenar las diferentes estructuras
de datos bsicas, nos permite cambiar el orden (posicin) de los elementos para
dejarlos ordenados segn un criterio fijo (numricamente, de menor a mayor, de
mayor a menor, etc.).
Hay mtodos simples de implementar que son tiles cuando el nmero de objetos a
ordenar es pequeo, pero por otro lado estn los mtodos ms complejos que son
aplicables a un nmero mayor de objetos, obteniendo una gran velocidad de
ordenamiento.
La eficiencia de los algoritmos se mide por el nmero de comparaciones e

intercambios que tienen que hacer, es decir, se toma n como el nmero de elementos
que tiene el arreglo a ordenar y se dice que un algoritmo realiza O(n2) o nlog (n)
comparaciones.
5. Biografa
http://es.wikipedia.org/wiki/Ordenamiento_por_mezcla
http://comunidad.dragonjar.org/f179/mergesort-ordenamiento-por-mezcla-
10082/
https://librosweb.es/libro/algoritmos_python/capitulo_20/ordenamiento_p
or_mezcla_o_merge_sort.html
http://es.slideshare.net/pambele/ordenamiento-por-mezcla-13842785

Ordenamiento Por Mezcla

Cargado por

Copyright:

Formatos disponibles

Ordenamiento Por Mezcla

Cargado por

Información del documento

Descripción original:

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Ordenamiento Por Mezcla

Cargado por

Copyright:

Formatos disponibles

1.

A continuacin los invitamos a conocer el Algoritmo de ordenamiento llamado

MergeSort (u Ordenamiento por mezcla) es uno de los Algoritmos de Ordenamientos

El Algoritmo MergeSort consiste en dividir en dos partes iguales el vector a ordenar,

Utiliza los siguientes tres pasos:

Dividir: Divide la secuencia de n elementos a ordenar en dos subsecuencias de n/2

Ordenar: Ordena las dos subsecuencias de manera recursiva mediante el algoritmo

La caracterstica principal de MergeSort es la eficiencia que posee en tiempo de

Su principal desventaja radica en que est definido recursivamente y su

Como cualquiera de los algoritmos de ordenamiento recursivo tiene complejidad

Si el tiempo de ordenamiento de MergeSort para una lista de n elementos es T(n)

Solucin de la ecuacin T (n) = 2T (n/2) + O(n)

El proceso de este algoritmo es fusionar sucesivamente mitades ya ordenadas de

El grupo de datos a ordenar es dividido en sus dos mitades pues es ms sencillo

Se comparan entonces los elementos de la mitad 1 en la posicin pos1 y de la mitad 2

Su utilizacin se da con mucha frecuencia cuando la cantidad de registros no es muy

A diferencia de algunas versiones mejoradas del QuickSort, MergeSort es un mtodo

Su principal desventaja radica en que est definido recursivamente y su

2.6. Grado de Complejidad

Esta es la tabla de comparacin del grado de complejidad entre los otros

Merge Sort est basado en la tcnica de diseo de algoritmos Divide y Vencers, de la

int _tmain(int argc, _TCHAR* argv[])

for(int i=0; i<n; i++)

void mergesort(int *v, int i, int f)

int c1=0, c2=m+1;

La eficiencia de los algoritmos se mide por el nmero de comparaciones e

También podría gustarte