MergeSort - Historial de revisiones

Carlos idict: Texto reemplazado: «
» por «»

2019-08-29T01:07:09Z

Texto reemplazado: «<div align="justify">» por «»

Astroboy en 23:59 18 feb 2012

2012-02-18T23:59:21Z

Astroboy en 23:54 18 feb 2012

2012-02-18T23:54:59Z

Mostrar los cambios

Astroboy: Merge sort trasladada a MergeSort

2012-02-18T23:12:13Z

Merge sort trasladada a MergeSort

Yennivert4jccmg: /* Mezclas Sucesivas (Merge sort) */

2012-01-09T16:17:19Z

‎Mezclas Sucesivas (Merge sort)

Yennivert4jccmg: /* Consideraciones */

2012-01-09T16:07:56Z

‎Consideraciones

Midel en 20:34 24 nov 2011

2011-11-24T20:34:33Z

Reynier idict: Algoritmo de Ordenamiento Merge sort trasladada a Merge sort

2011-11-10T19:25:09Z

Algoritmo de Ordenamiento Merge sort trasladada a Merge sort

Reynier idict en 19:21 10 nov 2011

2011-11-10T19:21:28Z

Yorch: Página creada con '{{Definición|Nombre=Algoritmo de ordenamiento. Merge sort|imagen=Ams.JPG|concepto=Se tiene un arreglo de 8 elementos, se ordenan los 4 elementos de cada arreglo y luego se mezc...'

2011-10-18T14:27:00Z

Página creada con '{{Definición|Nombre=Algoritmo de ordenamiento. Merge sort|imagen=Ams.JPG|concepto=Se tiene un arreglo de 8 elementos, se ordenan los 4 elementos de cada arreglo y luego se mezc...'

Página nueva

{{Definición|Nombre=Algoritmo de ordenamiento. Merge sort|imagen=Ams.JPG|concepto=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.
}}
==Ordenamiento==
===DEFINICIÓN===
'''Entrada:''' Una secuencia de n números <a1 , a2 , …, an>, usualmente en la forma de un arreglo de n elementos. <br>
'''Salida:''' Una permutación <a’1 , a’2, …, a’n> de la secuencia de entrada tal que a’1 = a’2 = … = a’n.
===CONSIDERACIONES===
Cada número es normalmente una [[clave]] que forma parte de un [[registro]]; cada [[registro]] contiene además datos [[satélites]] que se mueven junto con la [[clave]]; si cada [[registro]] incluye muchos datos [[satélites]],entonces movemos [[punteros]] a los registros y no los registros.

Un [[método]] de [[ordenación]] se denomina estable si el orden relativo de los elementos no se altera por el [[proceso]] de ordenamiento. Importante cuanto se ordena por varias claves.

'''Hay dos categorías importantes y disjuntas de algoritmos de ordenación:'''

*[[Ordenación]] [[interna]]: La cantidad de registros es suficientemente pequeña y el [[proceso]] puede llevarse a cabo en [[memoria]].
*[[Ordenación externa]]: Hay demasiados registros para permitir ordenación interna; deben almacenarse en [[disco]].

==Ordenamiento por Mezclas Sucesivas (Merge sort)==

Fue desarrollado en [[1945]] por [[John Von Neumann]].Se aplica la [[técnica]] divide y vencerás, dividiendo la [[secuencia]] de datos en dos subsecuencias hasta que las subsecuencias tengan un único [[elemento]], luego se ordenan mezclando dos subsecuencias ordenadas en una [[secuencia ordenada]], en forma sucesiva hasta obtener una [[secuencia]] única ya ordenada. Si n = 1 solo hay un [[elemento]] por ordenar, sino se hace una [[ordenación]] de [[mezcla]] de la primera mitad del [[arreglo]] con la segunda mitad. Las dos mitades se ordenan de igual forma.<br>
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]]: en esta situación es relativamente fácil implementar merge sort de manera que sólo requiera O(1) espacio extra, y el mal rendimiento de las listas enlazadas ante el [[acceso aleatori]]o hace que otros algoritmos como [[quicksort]] den un bajo [[rendimiento]], y para otros como [[heapsort]] sea algo imposible.El algoritmo de MergeSort es un [[algortimo]] de sort que presenta algunas propiedades interesantes. En primer lugar, el orden del algorimo es en el caso (n log n), y esto ocurre tanto en el peor caso, como en el mejor caso, como medio ya que el tiempo que insume el [[algoritmo]] no depende de la [[disposición]] inicial de los elementos del [[vector]]. En segundo lugar es un [[algoritmo]] que requiere de un espacio extra de [[almacenanimiento]] para poder funcionar.
== Implementación==
A continuación se muestra el Ordenamiento Merge sort en el [[lenguaje]] de [[programación]] de alto nivel [[C++]]:

void ordenarMezcla(TipoEle A[], int izq, int der)
{
if ( izq < der )
{
centro = ( izq + der ) % 2;
ordenarMezcla( A, izq, centro );
ordenarMezcla( A, centro+1, der);
intercalar( A, izq, centro, der );
}
}
void intercalar(TipoEle A[], int a, int c, int b )
{
k = 0;
i = a;
j = c + 1;
n = b - a;
while ( i < c + 1 ) && ( j < b + 1 )
{
if ( A[i] < A[j] )
{
B[k] = A[i];
i = i + 1;
}
else
{
B[k] = A[j];
j = j + 1;
}
k = k + 1;
};
while ( i < c + 1 )
{
B[k] = A[i];
i++;
k++;
};
while ( j < b + 1 )
{
B[k] = A[j];
j++;
k++;
};
i = a;
for ( k = 0; k < n; i++ )
{
A[i] = B[k];
i++;
};
};
==Fuente==
*PEÑA M., Ricardo. Diseño de programas. Formalismo y abstracción.
Prentice-Hall, 1998.
*WEISS, M. A., Estructuras de datos y algoritmos. Addison-Wesley
Iberoamericana, 1995.
*WIRTH, Niklaus. Algoritmos y Estructuras de Datos. Pentice Hall, 1987.
[[Category:Algoritmos]]

@@ Línea 7: / Línea 7: @@
 '''Merge sort'''. Algoritmo basado en la técnica de diseño de algoritmos Divide y Vencerás.
-===Definición===
+==Definición==
 Consiste en dividir el problema a resolver en subproblemas del mismo tipo que a su vez se dividirán, mientras no sean suficientemente pequeños o triviales.
-===Pasos===
+==Pasos==
 #Ordenar una secuencia S de elementos:
@@ Línea 22: / Línea 22: @@
 ##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 posición.
-===Seudocódigo===
+==Seudocódigo==
   MergeSort (T [ ] a,  entero n)
@@ Línea 65: / Línea 65: @@
+  }
-===Complejidad del algoritmo===
+==Complejidad del algoritmo==
 [[Image:Mergesort.png|200px]]<br/>
 Para ordenar un arreglo de tamaño n se ordenan 2 arreglos de tamaño n/2, de aquí el 2T(n/2), y luego se consume O(n) en realizar la mezcla. Resolviendo la ecuación recurrente tenemos que T(n) = O(n log n)
-===Propiedades===
+==Propiedades==
 *Es Estable.

@@ Línea 15: / Línea 15: @@
 ===Consideraciones===
-Cada número es normalmente una  [[clave]] que forma parte de un  [[registro]]; cada [[registro]] contiene además  datos [[satélites]] que se mueven junto con la [[clave]]; si cada [[registro]] incluye muchos datos [[satélites]],entonces movemos [[punteros]] a los registros  y no los registros.
+Cada número es normalmente una  [[clave]] que forma parte de un  [[registro]]; cada [[registro]] contiene además  datos [[satélites]] que se mueven junto con la [[clave]]; si cada [[registro]] incluye muchos datos [[satélites]], entonces movemos [[punteros]] a los registros  y no los registros.
 Un [[método]] de [[ordenación]] se denomina  estable si el orden relativo de los elementos no se altera por el [[proceso]] de ordenamiento. Importante cuanto se ordena por  varias claves.

← Revisión anterior		Revisión del 19:25 10 nov 2011
Línea 1:		Línea 1:
−	~~{{Normalizar}}~~
−	~~{{Mejorar}}~~
	{{Definición\|Nombre=Algoritmo de ordenamiento. Merge sort\|imagen=Ams.JPG\|concepto=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.		{{Definición\|Nombre=Algoritmo de ordenamiento. Merge sort\|imagen=Ams.JPG\|concepto=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.
	}}		}}

← Revisión anterior		Revisión del 19:21 10 nov 2011
Línea 1:		Línea 1:
		+	{{Normalizar}}
		+	{{Mejorar}}
	{{Definición\|Nombre=Algoritmo de ordenamiento. Merge sort\|imagen=Ams.JPG\|concepto=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.		{{Definición\|Nombre=Algoritmo de ordenamiento. Merge sort\|imagen=Ams.JPG\|concepto=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.
	}}		}}

@@ Línea 4: / Línea 4: @@
 |concepto=
 }}
-<div align="justify">
 '''Merge sort'''. Algoritmo basado en la técnica de diseño de algoritmos Divide y Vencerás.

← Revisión anterior	Revisión del 23:12 18 feb 2012
(Sin diferencias)

@@ Línea 28: / Línea 28: @@
 Fue desarrollado en  [[1945]] por [[John Von Neumann]].Se aplica la [[técnica]] divide y vencerás, dividiendo la [[secuencia]] de datos en dos subsecuencias hasta que las subsecuencias tengan un único [[elemento]], luego se ordenan mezclando dos subsecuencias ordenadas en una [[secuencia ordenada]], en forma sucesiva hasta obtener una [[secuencia]] única ya ordenada. Si n = 1 solo hay un [[elemento]] por ordenar, sino se hace una [[ordenación]] de [[mezcla]] de la primera mitad del [[arreglo]] con la segunda mitad. Las dos mitades se ordenan de igual forma.
-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]]: en esta situación es relativamente fácil implementar merge sort de manera que sólo requiera O(1) espacio extra, y el mal rendimiento de las listas enlazadas ante el [[acceso aleatori]]o hace que otros algoritmos como [[quicksort]] den un bajo [[rendimiento]], y para otros como [[heapsort]]  sea algo imposible.El algoritmo de MergeSort es un [[algortimo]] de sort que presenta algunas propiedades interesantes. En primer lugar, el orden del algorimo es en el caso  (n log n), y esto ocurre tanto en el peor caso, como en el mejor caso, como medio ya que el tiempo que insume el [[algoritmo]] no depende de la [[disposición]] inicial de los elementos del [[vector]]. En segundo lugar es un [[algoritmo]] que requiere de un espacio extra de [[almacenanimiento]] para poder funcionar.
+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]]: en esta situación es relativamente fácil implementar merge sort de manera que sólo requiera O(1) espacio extra, y el mal rendimiento de las listas enlazadas ante el [[acceso aleatori]]o hace que otros algoritmos como [[quicksort]] den un bajo [[rendimiento]], y para otros como [[heapsort]]  sea algo imposible. El algoritmo de MergeSort es un [[algortimo]] de sort que presenta algunas propiedades interesantes. En primer lugar, el orden del algorimo es en el caso  (n log n), y esto ocurre tanto en el peor caso, como en el mejor caso, como medio ya que el tiempo que insume el [[algoritmo]] no depende de la [[disposición]] inicial de los elementos del [[vector]]. En segundo lugar es un [[algoritmo]] que requiere de un espacio extra de [[almacenanimiento]] para poder funcionar.
 ==Implementación==
 A continuación se muestra el Ordenamiento Merge sort en el [[lenguaje]] de [[programación]] de alto nivel [[C++]]:

@@ Línea 1: / Línea 1: @@
-{{Definición|Nombre=Algoritmo de ordenamiento. Merge sort|imagen=Ams.JPG|concepto=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.
+{{Normalizar}}
 }}
-==Ordenamiento==
+'''Merge sort'''. Algoritmo de ordenamiento, donde primero ocurre el ordenamiento de los elementos por separado y luego se mezclan.
-===DEFINICIÓN===
 '''Entrada:''' Una secuencia de n números <a1 , a2 , …, an>, usualmente en la forma de un arreglo de n elementos. <br>
 '''Salida:''' Una permutación <a’1 , a’2, …, a’n> de la secuencia de entrada tal que a’1  = a’2 = … = a’n.
-===CONSIDERACIONES===
 Cada número es normalmente una  [[clave]] que forma parte de un  [[registro]]; cada [[registro]] contiene además  datos [[satélites]] que se mueven junto con la [[clave]]; si cada [[registro]] incluye muchos datos [[satélites]],entonces movemos [[punteros]] a los registros  y no los registros.
-−
 Un [[método]] de [[ordenación]] se denomina  estable si el orden relativo de los elementos no se altera por el [[proceso]] de ordenamiento. Importante cuanto se ordena por  varias claves.
-'''Hay dos categorías importantes y disjuntas de algoritmos de ordenación:'''
+Hay dos categorías importantes y disjuntas de algoritmos de ordenación:
-*[[Ordenación]] [[interna]]: La cantidad de registros es suficientemente pequeña y el [[proceso]] puede llevarse a cabo en [[memoria]].
+*Ordenación interna: La cantidad de registros es suficientemente pequeña y el [[proceso]] puede llevarse a cabo en [[memoria]].
 *[[Ordenación externa]]: Hay demasiados registros para permitir ordenación interna; deben almacenarse en [[disco]].
-==Ordenamiento por Mezclas Sucesivas (Merge sort)==
+==Mezclas Sucesivas (Merge sort)==
 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]]: en esta situación es relativamente fácil implementar merge sort de manera que sólo requiera O(1) espacio extra, y el mal rendimiento de las listas enlazadas ante el [[acceso aleatori]]o hace que otros algoritmos como [[quicksort]] den un bajo [[rendimiento]], y para otros como [[heapsort]]  sea algo imposible.El algoritmo de MergeSort es un [[algortimo]] de sort que presenta algunas propiedades interesantes. En primer lugar, el orden del algorimo es en el caso  (n log n), y esto ocurre tanto en el peor caso, como en el mejor caso, como medio ya que el tiempo que insume el [[algoritmo]] no depende de la [[disposición]] inicial de los elementos del [[vector]]. En segundo lugar es un [[algoritmo]] que requiere de un espacio extra de [[almacenanimiento]] para poder funcionar.
-== Implementación==
+==Implementación==
 A continuación se muestra el Ordenamiento Merge sort en el [[lenguaje]] de [[programación]] de alto nivel [[C++]]:
@@ Línea 72: / Línea 82: @@
     };
 ==Fuente==
-*PEÑA M., Ricardo.  Diseño de programas. Formalismo y abstracción.
+*PEÑA M., Ricardo.  Diseño de programas. Formalismo y abstracción. Prentice-Hall, 1998.
-Prentice-Hall, 1998.
+*WEISS, M. A., Estructuras de datos y algoritmos. Addison-Wesley Iberoamericana, 1995.
 *WIRTH, Niklaus. Algoritmos y Estructuras de Datos. Pentice Hall, 1987.
 [[Category:Algoritmos]]