¿No sabes por dónde empezar? Ayúdanos normalizando artículos.
¿Tienes experiencia? Crea alguno de estos artículos de actualidad.

Diferencia entre revisiones de «MergeSort»

m (Merge sort trasladada a MergeSort)
Línea 1: Línea 1:
{{Normalizar}}
 
{{Mejorar}}
 
 
{{Definición
 
{{Definición
|Nombre=Merge sort
+
|Nombre=MergeSort
 
|imagen=Ams.JPG
 
|imagen=Ams.JPG
 
|concepto=
 
|concepto=
 
}}
 
}}
'''Merge sort'''. Algoritmo de ordenamiento, donde primero ocurre el ordenamiento de los elementos por separado y luego se mezclan.
+
<div align="justify">
 +
'''Merge sort'''. Algoritmo basado en la técnica de diseño de algoritmos Divide y Vencerás.  
  
'''Ejemplo:''' Se tiene un arreglo de 8 elementos, se ordenan los 4 elementos de cada  arreglo y luego se mezclan. En 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===
 +
 
 +
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===
  
===Definición===
+
#Ordenar una secuencia S de elementos:
'''Entrada:''' Una secuencia de n números <a1 , a2 , , an>, usualmente en la forma de un arreglo de n elementos. <br>
+
##Si S tiene uno o ningún elemento, está ordenada
'''Salida:''' Una permutación <a’1 , a’2, …, a’n> de la secuencia de entrada tal que a’1  = a’2 = … = a’n.
+
##Si S tiene al menos dos elementos se divide en dos secuencias S1 y S2, S1 conteniendo los primeros n/2, y S2 los restantes.
 +
##Ordenar S1 y S2, aplicando recursivamente este procedimiento. 
 +
##Mezclar S1 y S2 ordenadamente en S
 +
#Mezclar dos secuencias ordenadas S1 y S2 en S:
 +
##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 posición.  
  
===Consideraciones===  
+
===Seudocódigo===
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.
+
MergeSort (T [ ] a,  entero n)
 +
  {
 +
  si ( n>1) entonces
 +
  {
 +
  a1= a[0...n/2 -1] ; // Primera mitad
 +
  a2= a[n/2...n-1] ; // Segunda mitad
 +
  MergeSort(a1, n/2);
 +
  MergeSort(a2, n – n/2);
 +
  Merge(a1,a2,a, n);
 +
  }
 +
  }
  
Hay dos categorías importantes y disjuntas de algoritmos de ordenación:
+
Merge(T [ ] a1,T [ ] a2, T [ ] a, entero n)
   
+
  {
*Ordenación interna: La cantidad de registros es suficientemente pequeña y el [[proceso]] puede llevarse a cabo en [[memoria]].
+
  entero i, j, k;
*[[Ordenación externa]]: Hay demasiados registros para permitir ordenación interna; deben almacenarse en [[disco]].
+
  i = j = k =0;
 +
  mientras(i < n/2 && j < n - n/2)
 +
  {
 +
  si(a1[i] < a2[j]) entonces
 +
  {
 +
  b[k] = a1 [i];
 +
  i++; k++;
 +
  } 
 +
  sino
 +
  {
 +
  b[k] = a2[j];
 +
  j++; k++;
 +
  }
 +
  }
 +
  mientras(i < n/2)
 +
  {
 +
  b[k] = a1 [i];  
 +
  i++; k++;
 +
  } 
 +
  mientras(j < n-n/2)
 +
  {
 +
  b[k] = a2 [j];
 +
  j++; k++;
 +
  } 
 +
  
==Mezclas Sucesivas (Merge sort)==
+
===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)
  
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.
+
===Propiedades===
  
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.
+
*Es Estable.
 +
*Memoria Auxiliar O(n).
 +
*No ordena en el lugar.
 +
*Es O(n log n).
  
==Implementación==
+
==Mezclas Sucesivas (MergeSort)==  
A continuación se muestra el Ordenamiento Merge sort en el [[lenguaje]] de [[programación]] de alto nivel [[C++]]:
+
 
 +
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.
 +
 
 +
MergeSort es un ordenamiento estable, paraleliza mejor, y es más eficiente manejando medios secuenciales de [[acceso]] lento. MergeSort es a menudo la mejor opción para ordenar una [[lista enlazada]]: en esta situación es relativamente fácil implementar MergeSort 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.
  
  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==
 
==Fuente==
 +
 +
*Curso de [[programación]] II, [[Universidad de Ciencias Informáticas]].
 
*PEÑA M., Ricardo.  Diseño de programas. Formalismo y abstracción. Prentice-Hall, 1998.   
 
*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.  
 
*WEISS, M. A., Estructuras de datos y algoritmos. Addison-Wesley Iberoamericana, 1995.  
 
*WIRTH, Niklaus. Algoritmos y Estructuras de Datos. Pentice Hall, 1987.  
 
*WIRTH, Niklaus. Algoritmos y Estructuras de Datos. Pentice Hall, 1987.  
 +
</div>
 
[[Category:Algoritmos]]
 
[[Category:Algoritmos]]

Revisión del 19:54 18 feb 2012

MergeSort
Información sobre la plantilla
Ams.JPG

Merge sort. Algoritmo basado en la técnica de diseño de algoritmos Divide y Vencerás.

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

  1. Ordenar una secuencia S de elementos:
    1. Si S tiene uno o ningún elemento, está ordenada
    2. Si S tiene al menos dos elementos se divide en dos secuencias S1 y S2, S1 conteniendo los primeros n/2, y S2 los restantes.
    3. Ordenar S1 y S2, aplicando recursivamente este procedimiento.
    4. Mezclar S1 y S2 ordenadamente en S
  2. Mezclar dos secuencias ordenadas S1 y S2 en S:
    1. Se tienen referencias al principio de cada una de las secuencias a mezclar (S1 y S2).
    2. 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

MergeSort (T [ ] a,  entero n) 
{ 
 si ( n>1) entonces 
 { 
  a1= a[0...n/2 -1] ; // Primera mitad 
  a2= a[n/2...n-1] ; // Segunda mitad 
  MergeSort(a1, n/2);
  MergeSort(a2, n – n/2); 
  Merge(a1,a2,a, n); 
 }
} 
Merge(T [ ] a1,T [ ] a2, T [ ] a, entero n)
{ 
 entero i, j, k; 
 i = j = k =0; 
 mientras(i < n/2 && j < n - n/2)
 { 
  si(a1[i] < a2[j]) entonces
  { 
  b[k] = a1 [i]; 
  i++; k++;
  }  
  sino
  { 
  b[k] = a2[j]; 
  j++; k++;
  } 
 }
 mientras(i < n/2)
 { 
  b[k] = a1 [i]; 
  i++; k++;
 }  
 mientras(j < n-n/2)
 { 
  b[k] = a2 [j]; 
  j++; k++;
 }  
}  

Complejidad del algoritmo

Mergesort.png
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

  • Es Estable.
  • Memoria Auxiliar O(n).
  • No ordena en el lugar.
  • Es O(n log n).

Mezclas Sucesivas (MergeSort)

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.

MergeSort es un ordenamiento estable, paraleliza mejor, y es más eficiente manejando medios secuenciales de acceso lento. MergeSort es a menudo la mejor opción para ordenar una lista enlazada: en esta situación es relativamente fácil implementar MergeSort de manera que sólo requiera O(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. 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.

Fuente

  • Curso de programación II, Universidad de Ciencias Informáticas.
  • 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.