Divide y Conquistarás

En las ciencias de la computación, el término divide y vencerás (DYV) hace referencia a uno de los más importantes paradigmas de diseño algorítmico. El método está basado en la resolución recursiva de un problema dividiéndolo en dos o más subproblemas de igual tipo o similar. El proceso continúa hasta que éstos llegan a ser lo suficientemente sencillos como para que se resuelvan directamente. Al final, las soluciones a cada uno de los subproblemas se combinan para dar una solución al problema original. 

Esta técnica es la base de los algoritmos eficientes para casi cualquier tipo de problema como, por ejemplo, algoritmos de ordenamiento (quicksort, mergesort, entre muchos otros), multiplicar números grandes (Karatsuba), análisis sintácticos (análisis sintáctico top-down) y la transformada discreta de Fourier. 

Por otra parte, analizar y diseñar algoritmos de DyV son tareas que lleva tiempo dominar. Al igual que en la inducción, a veces es necesario sustituir el problema original por uno más complejo para conseguir realizar la recursión, y no hay un método sistemático de generalización. 

El nombre divide y vencerás también se aplica a veces a algoritmos que reducen cada problema a un único subproblema, como la búsqueda binaria para encontrar un elemento en una lista ordenada (o su equivalente en computación numérica, el algoritmo de bisección para búsqueda de raíces). Estos algoritmos pueden ser implementados más eficientemente que los algoritmos generales de “divide y vencerás”; en particular, si es usando una serie de recursiones que lo convierten en simples bucles. Bajo esta amplia definición, sin embargo, cada algoritmo que usa recursión o bucles puede ser tomado como un algoritmo de “divide y vencerás”. 

La búsqueda binaria, un algoritmo de divide y vencerás en el que el problema original es partido sucesivamente en subproblemas simples de más o menos la mitad del tamaño, tiene una larga historia. La idea de usar una lista ordenada de objetos para facilitar su búsqueda data de la antigua Babilonia en el 200 a. C., mientras que una descripción del algoritmo en ordenadores apareció en 1946 en un artículo de John Mauchly. Otro algoritmo de “divide y vencerás” con un único subproblema es el algoritmo de Euclides para computar el máximo común divisor de dos números (mediante reducción de números a problemas equivalentes cada vez más pequeños), que data de muchos siglos antes de Cristo. 

Un ejemplo antiguo de algoritmo de “divide y vencerás” con múltiples subproblemas es la descripción realizada por Gauss en 1805 de lo que se le llama ahora algoritmo de la rápida transformación de Fourier Cooley-Tukey (FFT), aunque él no analizó su conjunto de operaciones cuantitativamente y los FFT no se difundieron hasta que se redescubrieron casi un siglo después. 

Un ejemplo de estos es el QuickSort (en inglés, ordenamiento rápido). Es un algoritmo basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n. 

El algoritmo consta de los siguientes pasos: 

Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote. 

Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la implementación deseada. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada. 

La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha. 

Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados. 

La eficiencia del algoritmo depende de la posición en la que termine el pivote elegido. En el mejor caso, el pivote termina en el centro de la lista, dividiéndola en dos sublistas de igual tamaño. En este caso, el orden de complejidad del algoritmo es O (n•log n). En el peor caso, el pivote termina en un extremo de la lista. El orden de complejidad del algoritmo es entonces de O(n²). El peor caso dependerá de la implementación del algoritmo, aunque habitualmente ocurre en listas que se encuentran ordenadas, o casi ordenadas. Pero principalmente depende del pivote, si por ejemplo el algoritmo implementado toma como pivote siempre el primer elemento del array, y el array que le pasamos está ordenado, siempre va a generar a su izquierda un array vacío, lo que es ineficiente. En el caso promedio, el orden es O(n•log n). Y no es extraño, pues, que la mayoría de optimizaciones que se aplican al algoritmo se centren en la elección del pivote. 

Para este caso hagamos una demostración; Suponiendo que el número total de elementos a ordenar es potencia de dos, es decir, n = 2k. De aquí podemos ver que k = log2(n), donde k es el número de divisiones que realizará el algoritmo. 

En la primera fase del algoritmo habrá n comparaciones, en la segunda fase el algoritmo creará dos sublistas aproximadamente de tamaño n/2. El número total de comparaciones de estas dos sublistas es: 2(n/2) = n. En la tercera fase el algoritmo procesará 4 sublistas más, por tanto, el número total de comparaciones en esta fase es 4(n/4) = n. 

En conclusión, el número total de comparaciones que hace el algoritmo es: 

n + n + n + …. + n = kn, donde k = log2(n), por tanto, el tiempo de ejecución del algoritmo en el mejor caso es O(n.log2n) 

optimizando el algoritmo cabe destacar que de usarse en su versión recursiva las siguientes optimizaciones y sus desventajas no se ven vistas en el tiempo de ejecución del mismo manteniéndose, así el tiempo de ejecución planteado en un principio. 

El algoritmo básico del método Quicksort consiste en tomar cualquier elemento de la lista al cual denominaremos como pivote, dependiendo de la partición en que se elija, el algoritmo será más o menos eficiente. 
Tomar un elemento cualquiera como pivote tiene la ventaja de no requerir ningún cálculo adicional, lo cual lo hace bastante rápido. Sin embargo, esta elección «a ciegas» siempre provoca que el algoritmo tenga un orden de O(n²) para ciertas permutaciones de los elementos en la lista. 

 
Otra opción puede ser recorrer la lista para saber de antemano qué elemento ocupará la posición central de la lista, para elegirlo como pivote. Esto puede hacerse en O(n) y asegura que hasta en el peor de los casos, el algoritmo sea O(n•log n). No obstante, el cálculo adicional rebaja bastante la eficiencia del algoritmo en el caso promedio. La opción a medio camino es tomar tres elementos de la lista - por ejemplo, el primero, el segundo, y el último - y compararlos, eligiendo el valor del medio como pivote. 

Una idea preliminar para ubicar el pivote en su posición final sería contar la cantidad de elementos menores que él, y colocarlo un lugar más arriba, moviendo luego todos esos elementos menores que él a su izquierda, para que pueda aplicarse la recursividad. 

Existe, no obstante, un procedimiento mucho más efectivo. Se utilizan dos índices: i, al que llamaremos índice izquierdo, y j, al que llamaremos índice derecho. El algoritmo es el siguiente: 

Recorrer la lista simultáneamente con i y j: por la izquierda con i (desde el primer elemento), y por la derecha con j (desde el último elemento). Cuando lista[i] sea mayor que el pivote y lista[j] sea menor, se intercambian los elementos en esas posiciones. 

Repetir esto hasta que se crucen los índices. El punto en que se cruzan los índices es la posición adecuada para colocar el pivote, porque sabemos que a un lado los elementos son todos menores y al otro son todos mayores (o habrían sido intercambiados). 

El funcionamiento se realiza por medio de llamar a la función Quicksort desde donde quiera ejecutarse, ésta llamará a colocar pivote para encontrar el valor del mismo, y por último, se ejecutará el algoritmo Quicksort de forma recursiva a ambos lados del pivote. 

La implementación de este algoritmo sería de la siguiente manera: 

int colocar(int *v, int b, int t){ 

 int i;

 int pivote, valor_pivote;

 int temp;

 pivote = b;

 valor_pivote = v[pivote];

 for (i=b+1; i<=t; i++){ 

  if (v[i] < valor_pivote){

  pivote++; 

  temp=v[i]; 

  v[i]=v[pivote];

  v[pivote]=temp;

  }

 }

 temp=v[b];

 v[b]=v[pivote];

 v[pivote]=temp;

return pivote;

} 

void Quicksort(int* v, int b, int t){

 int pivote;

 if(b < t){

 pivote=colocar(v, b, t);

 Quicksort(v, b, pivote-1);

 Quicksort(v, pivote+1, t);

 }  

}