La técnica divide y conquista separa un problema en subproblemas que se parecen al problema original, de manera recursiva resuelve los subproblemas y, por último, combina las soluciones de los subproblemas para resolver el problema original. Como divide y conquista resuelve subproblemas de manera recursiva, cada subproblema debe ser más pequeño que el problema original, y debe haber un caso base para los subproblemas.
Los algoritmos de divide y vencerás tienen tres partes:
-
Divide el problema en un número de subproblemas que son instancias más pequeñas del mismo problema.
-
Conquista los subproblemas al resolverlos de manera recursiva. Si son los suficientemente pequeños, resuelve los subproblemas como casos base.
-
Combina las soluciones de los subproblemas en la solución para el problema original.
Por lo general los algoritmos basados en divide y conquista tienen una estructura recursiva que de manera general puede verse como la estructura presentada en la siguiente imagen:
Su relación con la programación modular
Programación modular es uno de los métodos más conocidos para resolver un problema, es dividirlo en problemas más pequeños, llamados subproblemas y combinar las respuestas de estos subproblemas. Esta técnica se usa mucho en programación ya que programar no es más que resolver problemas, y se le suele llamar diseño descendente, metodología del divide y vencerás o programación top-down.
Merge Sort
El merge sort (ordenamiento por mezcla), es un algoritmo de ordenamiento para arreglos que utiliza la técnica de divide y conquista.
Conceptualmente, el ordenamiento por mezcla funciona de la siguiente manera:
-
Si la longitud de la lista es 0 o 1, entonces ya está ordenada. En otro caso:
-
Dividir la lista desordenada en dos sublistas de aproximadamente la mitad del tamaño.
-
Ordenar cada sublista recursivamente aplicando el ordenamiento por mezcla.
-
Mezclar las dos sublistas en una sola lista ordenada.
Podemos definir un algoritmo concreto, en este caso vamos a utilizar Python para desarrollar el algoritmo, esto debido a su simplicidad.
Función principal
Como se observa en la imagen del algoritmo, este mismo inicia con el arreglo desordenado y ejecuta la validación del paso 1, si no se cumple se saca la mitad del numero de elementos del arreglo y se procede a dividir el arreglo en 2 a partir de esa mitad.
Seguido de esto, se vuelve a aplicar el mismo proceso hasta que cada elemento del arreglo esté por si solo, luego se procede a mezclar estos elementos en listas nuevamente, seleccionando los elementos en orden para cumplir el objetivo.
Función de mezcla
La función de mezcla recibe de 2 listas, estas pueden tener 1 o más elementos, al inicio de la función se inicializan las variables de utilidad, estamos hablando de los 2 índices inicializados en 0 y el arreglo resultado que la inicializamos como vacío, seguido de esto en el ciclo while iteramos comparando los elementos de los 2 arreglos para ir escogiendo el menor en cada iteración, el ciclo termina si ya se tomó en cuenta todos los elementos de uno de los arreglos, cuando termina el ciclo se agrega el sobrante de los arreglos.
Visualización del algoritmo
El algoritmo tiene el siguiente comportamiento:
Referencias
Cormen, T. Algoritmos de divide y vencerás (artículo) | Khan Academy. Recuperado 17 Julio 2020, de https://es.khanacademy.org/computing/computer-science/algorithms/merge-sort/a/divide-and-conquer-algorithms
Programación Modular - EcuRed. Retrieved 17 Julio 2020, de https://www.ecured.cu/Programaci%C3%B3n_Modular#:~:text=Objetivos%20de%20la%20Programaci%C3%B3n%20Modular,-Al%20aplicar%20la&text=Esta%20t%C3%A9cnica%20se%20llama%20refinamiento,divide%20el%20problema%20complejo%20original.