CAPÍTULO 5: ALGORITMOS DE SORTEO AVANZADOS

MergeSort

MergeSort es un algoritmo que también hace uso de la estrategia de Divide&Conquer, dividiendo el problema de sorteo en 2 subproblemas para cada llamado, hasta que el problema se vuelve tan simple como para ser resuelto, ahora todas las soluciones a los subproblemas son combinados para generar una solución al completa al problema.

El principio de MergeSort lo resumimos de la siguiente manera:

• Si en la lista solo hay un elemento, entonces ya está sorteado, se abandona la función con un return.

• Si hay más de un elemento, el array se divide en dos, hasta que no se pueda dividir más.

• Combinar la lista más pequeña en una nueva lista en orden sorteado.

Implementación de MergeSort

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

namespace MergeSort {
		void merge(int a[], int f, int l, int m) {
			int i, n = l - f + 1;
			int a1f = f, a1l = m - 1;
			int a2f = m, a2l = l;
			int*anew = new int[n];
			for (i = 0; i < n; i++) {
				if (a1f <= a1l) {
					if (a2f <= a2l) {
						if (a[a1f] <= a[a2f])
							anew[i] = a[a1f++];
						else anew[i] = a[a2f++];
					}
					else anew[i] = a[a1f++];
				}
				else anew[i] = a[a2f++];
			}
			for (i = 0; i<n; i++)
				a[f + i] = anew[i];
			delete[] anew;
		}

		void mergesort(int a[], int f, int l) {
			if (f < l) {
				int m = (f + l + 1) / 2;
				mergesort(a, f, m - 1);
				mergesort(a, m, l);
				merge(a, f, l, m);
			}
		}
	}

Entendiendo la función Merge(...)

El proceder de la función merge la podemos analizar con ayuda de la Ilustración 2 en el siguiente ejemplo:

• myArray = 2, 3, 8, 1, 4, 6 está compuesta por las sub-listas de elementos ya sorteadas: mySubArray1 = 2, 3, 8 y mySubArray2 = 1, 4, 6.

• Creamos un array temporal el cual una copia exacta del input array será:  temp = 2, 3, 5, 1, 4, 6.

• Luego basta con recorrer las dos sub-listas de izquierda a derecha y buscar el menor número de los dos primeros y sobrescribirlo en el lugar correcto de nuestro array original

Ejemplo: Animación sorteando con MergeSort

Aquí vemos claramente como mergesort() divide el problema hasta tener solo dos elementos (en realidad hasta uno, pero un elemento solo ya está sorteado) , luego así determina fácilmente cuál de los dos es mayor, después de ello, regresa a el llamado anterior y combina las soluciones para cada llamado de la recursión

Análisis de la complejidad de Mergesort

Para mesclar dos sublistas vemos que es necesario recorrer las dos, en general para un array de largo n, necesitaremos exactamente n comparaciones. Ahora podriamos establecer una ecuacion recursiva para el numero de comparaciones que se veria de la siguiente manera.

Pues para sortear un array/lista de largo n, se debe primero sortear las 2 sub listas de aproximadamente el mismo largo y luego mezclarlas, lo cual nos cuesta n. La solucion de esta funcion recursiva nos lleva tanto en best case como en worst case a una complejidad de Θ(n log n).

Continua en la parte 3 siguiendo este enlace:

https://thewhitecode.com/blog/5688

El Manual de los algoritmos y las estructuras de datos.

Este capítulo ha sido solo uno de 9 capítulos en total del libro.

Descarga el manual directamente desde este enlace:

https://leanpub.com/elmanualdelosalgoritmosylasestructurasdedatos

¿Te ha gustado?, quisieras acceder a más contenido?

Deja tu comentario!