Mergesort
En esta tercera lectura, se presenta otra alternativa en los temas de métodos de
ordenamiento, conocida como Mergesort u ordenamiento por mezcla. Este método
avanzado y recursivo consiste en una mejor opción al ordenamiento de Shell y
permite un algoritmo de la forma O(nlogn), lo cual ofrece una mayor efectividad. La
ordenación por mezcla utiliza el menor número de comparaciones de todos los
algoritmos de ordenación más populares.
Mergesort
De nición de términos básicos
Referencias
Lección 1 de 3
Mergesort
El método de Mergesort, también denominado ordenamiento por mezcla, es
un método indirecto o avanzado que se caracteriza por la aplicación del
«divide y vencerás». Este es un algoritmo de ordenación recursivo con una
complejidad de O (n log n), el cual permite una corta mejora respecto al
ordenamiento Shell. Este método puede ser aplicado según se indica en la
figura 1.
Figura 1: Aplicación del método Mergesort
public static void mergesort(int A[],int izq, int der){
if (izq < der){
int m=(izq+der)/2;
mergesort(A,izq, m);
mergesort(A,m+1, der);
merge(A,izq, m, der);
Fuente: elaboración propia.
Figura 2: Etapas de la ordenación por mezcla
Fuente: Allen Weiss, 2013, p. 350.
El método ordena un array A de enteros desde la posición izquierda (izq)
hasta la posición derecha (der). En la primera llamada al método, recibirá los
valores izq = 0, der = ELEMENTOS-1. En un primer paso, se determina el que
será el elemento central «m». Seguidamente, la primera parte del array,
desde izq hasta m y la segunda parte del array, desde m+1 hasta der, se
mezclan mediante llamadas recursivas al método Mergesort. Por su parte, la
recursión termina cuando izq == der, es decir, cuando un subarray contiene
solamente un elemento. Por último, se puede decir que la operación
principal de la aplicación del método Merge puede ser aplicada de varias
formas: la más frecuente puede observarse en la figura 3.
Figura 3: Algoritmo Mergesort
public static void merge(int A[],int izq, int m, int der){
int i, j, k;
int [] B = new int[[Link]]; //array auxiliar
for (i=izq; i<=der; i++) //copia ambas mitades en el array auxiliar
B[i]=A[i];
i=izq; j=m+1; k=izq;
while (i<=m && j<=der) //copia el siguiente elemento más grande
if (B[i]<=B[j])
A[k++]=B[i++];
else
A[k++]=B[j++];
while (i<=m) //copia los elementos que quedan de la
A[k++]=B[i++]; //primera mitad (si los hay)
Fuente: elaboración propia.
Según lo establece Allen Weiss (2013):
Ahora bien, es importante acotar que, aunque el tiempo de
ejecución de la ordenación por mezcla es O (n log n), presenta el
significativo problema de que mezclar dos listas ordenadas
utiliza una memoria adicional lineal. El trabajo adicional
implicado en crear la matriz temporal de nuevo sobre la matriz
original a lo largo de todo el algoritmo ralentiza la operación
considerablemente. Este proceso de copia puede conmutarse
juiciosamente los papeles de a y tmpArray en niveles
alternativos de la recursión. (pp. 352-353).
C O NT I NU A R
Lección 2 de 3
Definición de términos básicos
Mergesort
–
“La ordenación por mezcla utiliza la técnica de «divide y vencerás», para obtener
un tiempo de ejecución O( n log n )” (Allen Weiss, 2013, p. 350).
Recursividad
–
“Un método recursivo es un método que hace directa o indirectamente, una
llamada a sí mismo.” (Allen Weiss, 2013, p. 287).
Con el fin de complementar esta tercera lectura del módulo 4, se recomienda
ampliar la perspectiva con la revisión de la siguiente publicación:
Técnicas para capturar los cambios en los datos y mantener
actualizado un almacén de datos..pdf
763 6 KB
763.6 KB
Fuente: Díaz de la Paz, L. et al. (2015). Técnicas para capturar los cambios en los datos y mantener
actualizado un almacén de datos. En Revista cubana de ciencias informáticas (4)9, pp. 89-103.
Recuperado de [Link]
18992015000400007&lng=es&nrm=iso.
La ordenación por mezcla utiliza el menor número de comparaciones de
todos los algoritmos de ordenación más populares.
Verdadero.
Falso.
SUBMIT
Pueden evitarse las copias excesivas, pero no puede prescindirse de la
cantidad adicional de memoria adicional lineal requerida sin un excesivo
coste de tiempo adicional de ejecución.
Verdadero.
Falso.
SUBMIT
C O NT I NU A R
Lección 3 de 3
Referencias
Allen Weiss, M. (2013). Estructuras de datos en Java (4ta edición). Editorial
Pearson Educación.
Díaz de la Paz, L. et al. (2015). Técnicas para capturar los cambios en los
datos y mantener actualizado un almacén de datos. En Revista cubana de
ciencias informáticas (4)9, pp. 89-103. Recuperado de
[Link]
18992015000400007&lng=es&nrm=iso.
Senger de Souza, S. R., Paiva Prado, M., Barbosa, E. F. y Maldonado, J. C.
(2012). An Experimental Study to Evaluate the Impact of the Programming
Paradigm in the Testing Activity. En CLEI Electronic Journal (1)15, pp. 4-4.
Recuperado de [Link]
script=sci_arttext&pid=S0717-50002012000100004.
