Divide y vencerás es una técnica para diseñar algoritmos que consiste en descomponer el
caso que haya que resolver en un cierto número de subcasos más pequeños del mismo
problema,resolver sucesiva e independientemente todos estos subcasos, y combinar
después las soluciones obtenidas de esta manera para obtener la solución del caso
original.
El paradigma de diseño de algoritmos denominado divide y vencerás normalmente no se
reducen a bucles triviales. En general, los algoritmos de este tipo incluyen algún
tratamiento para dividir los datos de entrada en dos partes, o para mezclar los resultados
del proceso de la resolución de dos partes independientes de datos de entrada. Es decir, se
pueden encontrar instrucciones antes, después o entre las llamadas recursivas.
En otras palabras, los algoritmos de división reducen repetidamente el problema en
subproblemas, a menudo en forma recursiva, hasta que el subproblema es lo
suficientemente pequeño para ser resuelto. Un ejemplo práctico es el algoritmo de
ordenación. Una variante de esta metodología es la reducción y conquista, que resuelve un
subproblema y utiliza la solución para resolver un problema más grande. Un ejemplo
práctico es el algoritmo de búsqueda binaria.
Búsqueda Binaria
La búsqueda binaria precedió a las computadoras. En esencia, es el algoritmo que se
emplea para buscar una palabra en un diccionario, o un nombre en un directorio
telefónico. Probablemente se trate de la aplicación más sencilla de divide y conquistarás,
tan sencilla que hablando con propiedad esto es una aplicación de reducción
(simplificación) más que de divide y conquistarás: la solución de todo caso suficientemente
grande se reduce a un caso más pequeño, en este caso de tamaño mitad. Sea T[1..n] una matriz ordenada por orden no decreciente; esto es T[i]≤T[j] siempre que sea
1≤i≤j≤n. Sea x un elemento. El problema consiste en buscar x en la matriz T, si es que
está. Formalmente, deseamos encontrar un índice i tal que 1≤i≤n+1 y T[i-1]<x≤T[i], con la
convención lógica consistente en que T[0]=-∞ y T[n+1]=+∞(al decir convenio lógico se quiere indicar que estos valores no están realmente presentes en la matriz). La aproximación
evidente para este problema consiste en examinar secuencialmente todos los elementos T,
hasta que bien se llegue al final de la matriz o bien un elemento que no sea menor que x.
Ordenación por fusión
El enfoque evidente de divide y vencerás para este problema consiste en descomponer la
matriz T en dos partes cuyos tamaños sean tan parecidos como sea posible, ordenar estas
partes mediante llamadas recursivas, y después fusionar las soluciones de cada parte,
teniendo buen cuidado en mantener el orden. Para hacer esto, se necesita un algoritmo
eficiente para fusionar dos matrices ordenadas U y V. Esto se puede lograr de forma más
eficiente y más sencilla, si se dispone de espacio adicional el final de las matrices U y V,
para utilizarla como centinela(esto solo funciona si se da al centinela un valor acordado
previamente y que se esté confiado que sea mayor que cualquier elemento de las matrices
U y V.
Ordenación Quicksort
Está basado en el principio de divide y conquistarás. A diferencia de ordenar por fusión, la
mayor parte del trabajo no recursivo que hay que hacer se invierte en construir subcasos, y
no en combinar sus soluciones. Como primer paso, el algoritmo selecciona como pivote
uno de los elementos de la matriz que haya que ordenar. A continuación, la matriz se
parte a ambos lados del pivote: se desplazan los elementos de tal manera que los que
sean mayores que el pivote queden a su derecha, mientras que los demás quedan a su
izquierda. Si ahora las partes de la matriz que quedan a ambos lados del pivote se ordenan
independientemente mediante llamadas recursivas al algoritmo, el resultado final es una
matriz completamente ordenada ; no hace falta un paso subsiguiente de fusión. Para
equilibrar los tamaños de los dos subcasos que hay que ordenar. no se utilizara una
mediana como pivote ya que encontrar la mediana requiere de un tiempo excesivo. Por
esa razón se usará como pivote un arbitrario de la matriz.
El diseño de un algoritmo de partición con tiempo lineal no es tarea fácil. Sin embargo, en
la práctica resulta crucial que la constante oculta sea pequeña, para que quicksort sea
competitivo con otras técnicas de ordenación tales como ordenación por montículo.
Suponiendo que es preciso descomponer la submatriz T[i..j] empleando como pivote p=T[i].
Una buena forma de hacer la descomposición consiste en explorar la submatriz una sola
vez, pero empezando por los dos extremos. Los punteros k y l se inician en i y j+1
respectivamente. A continuación, se incrementa el puntero k hasta que T[k]>p, y se
decrementa el puntero l hasta que T[l]≤p. Ahora se intercambian T[k] y T[l].Este proceso
continúa mientras k<l. Finalmente, se intercambian T[i] y T[l] para poner el pivote en
posición correcta
Referencias
Gonzalo, F. E., Arias, A., & Academy, C. I. (2016). Curso de Programación con
iOS: Apps iPhone. 2a Edición (2.a
ed.). Createspace Independent Publishing
Platform.
Brassard, G., & Bratley, P. (2000). Fundamentos de Algoritmia. Prentice Hall.
Sedgewick, R. (1995). Algoritmos En C++. Addison-Wesley.