Ejemplos

Existen una serie de ejemplos considerados como representantes clásicos de este diseño, muy especialmente los algoritmos de ordenación: ordenación por fusión (Mergesort) y ordenación rápida (Quicksort).

Otros, como la búsqueda binaria, probablemente se trate de la aplicación más sencilla de Divide y Vencerás.

Antes, vamos a mostrar la solución según Divide y Vencerás, de un problema que vimos en el tema anterior:

Calcular la potencia n-esima de a, siendo n≥0 y a≥0

Potencia n-esima de a

Algoritmo visto en el tema II, “Diseño de Algoritmos Recursivos”.-

$a \geq0 \wedge n \geq0$

Funcion POTENCIA (a:entero, n:entero) retorna (p:entero) 
    caso
        n = 0 -> 1
        n > 0  -> POTENCIA(a, n-1) * a
    fcaso 
ffunción

{$p = a^{n}$}

Potencia n-esima de a según Divide y Vencerás

$a \geq0 \wedge n \geq0$

Funcion POTENCIA_DyV (a:entero, n:entero) retorna (p:entero) 
    ...

{$p = a^{n}$}

¿POTENCIA_DyV (a, n)?

Resolvemos cada subproblema de forma independiente

Y, ya sólo nos queda combinar las soluciones parciales. En este punto hay que tener en cuenta si n es par o no, con objeto de construir de forma correcta la solución original, esto es, $a^{n}$.

Si n es par entonces $a^{n} = a^{n/2}*a^{n/2}$

mientras que si n es impar entonces $a^{n} = a^{n/2}*a^{n/2}*a$

$a \geq0 \wedge n \geq0$

Funcion POTENCIA_DyV (a:entero, n:entero) retorna (p:entero) 
    var p:entero fvar
    si n = 0 entonces retorna 1
        sino 
	    p = POTENCIA_DyV (a, n/2) 
	si n es par entonces retorna p*p
	    sino  retorna p*p*a
	fsi
    fsi
ffunción

{$p = a^{n}$}

$T(n) \in \theta(log_{2}n)$

Búsqueda Binaria

Dado un vector V[1..n] de n números enteros, siendo n≥0, se trata de diseñar una función recursiva que retorne la posición que ocupa un valor x, si está en el vector, o la que debería ocupar si no está. El vector se encuentra ordenado en sentido creciente.

Estrategia:

1. “Dividir” el vector V por la mitad ( m = (1+n) div 2 )

2. Comprobar si x está en la posición central, esto es, en V[m]. Pueden ocurrir tres cosas:

   2.1) Que sí que esté (x=V[m]), por tanto el problema está resuelto y la función retornará el valor m

2.2) Que no esté y x < V[m], entonces continúa la búsqueda en la primera mitad de V, esto es,

en V[1..m-1]

2.3) Que no esté y x > V[m], entonces continúa la búsqueda en la segunda mitad de V, esto es,

en V[m+1..n]

$Q \equiv {1 \leq inicio \leq fin+1 \leq n+1 \wedge (\forall)(V[i]<V[i+1]:inicio\leq i \leq fin-1)}$

función Busqueda_binaria (V[1..n]:vector de enteros; x, inicio, fin:entero) retorna (e:entero, b:booleano)
        var m : entero fvar
        si inicio > fin entonces retorna ( inicio, falso )
        sino 
	    m = (inicio + fin) div 2
	    si x = V[m] entonces retorna (m, verdadero)
            sino  si x < V[m] entonces retorna Busqueda_binaria (V, x, inicio, m-1)
	          sino retorna Busqueda_binaria (V, x, m+1, fin)
		  fsi
	    fsi
        fsi
ffunción

donde la llamada inicial a la función es: Busqueda_binaria(V, x, 1, n)

Mergesort (Ordenación por fusión)

Dado un vector V[1..n] de números enteros, siendo n≥0, el problema consiste en ordenar el vector en sentido creciente.

Estrategia:

1. “Dividir” el vector V por la mitad ( m = (1+n) div 2 )

2. Resolver los dos subproblemas, esto es, V[1..m] y V[m+1..n]

Los casos bases se alcanzan cuando haya que ordenar una sección de vector de tamaño 0 o 1. En este último caso, la única componente del vector ya está ordenada, por lo que no hay nada que hacer, al igual que en el caso de tamaño 0.

3. Combinar (mezclar) en tiempo lineal las dos secciones del vector ya ordenadas para generar la ordenación del vector V[1..n]

Procedimiento MergeSort ( V[1..n] : vector de enteros; inicio, fin : entero) 
       si inicio < fin  entonces
              mitad = (inicio+fin)/2		/* dividir */
              MergeSort (V, inicio, mitad)      /* resolver */
              MergeSort (V, mitad+ 1, fin)      /* resolver */
              Mezcla (V, inicio, mitad, fin)    /* combinar */
      fsi
fprocedimiento

donde la llamada inicial a la función es: MergeSort(V, 1, n)

$T(n) \in \theta(log_{2}n)$

Mezcla

La función mezcla permite obtener un vector ordenado a partir de dos secciones del vector ya ordenadas, con un coste lineal con la suma de los tamaños de las dos secciones del vector.

Para ello se precisa la creación de un vector auxiliar en el que almacenar el resultado de la mezcla.

Vamos a verlo a través de un ejemplo:

Quicksort (ordenación rápida)

Dado un vector V[1..n] de números enteros, siendo n≥0, el problema consiste en ordenar el vector en sentido creciente.

Estrategia DyV.-

• Seleccionar un elemento pivote y dividir el vector de tal modo que los elementos menores que el pivote queden a un lado y los mayores al otro. El pivote se situará en el medio.

• Resolver los dos subproblemas que corresponden a las dos secciones del vector: donde están los menores que el pivote y donde están los mayores que el pivote.

• Combinar: No habría que hacer nada.

Procedimiento QuickSort ( V[1..n] : vector de enteros; inicio, fin : entero) 
	si  inicio < fin entonces
		indice_pivote=Partir( V, inicio, fin )              /* dividir */
        	QuickSort ( V, inicio, indice_pivote-1 )    /* resolver */
        	QuickSort ( V, indice_pivote+1, fin )       /* resolver */
        fsi
fprocedimiento

donde la llamada inicial a la función es: QuickSort(V, 1, n)

$T(n) \in \Omega(nlog_{2}n)$ y $T(n) \in O(n^{2})$

Ejemplo del funcionamiento de Partir

V[inicio] será el pivote elegido.

A continuación se procede a recolocar los elementos del vector.

Procedimiento QuickSort ( V[1..n] : vector de enteros; inicio, fin : entero) 
	si  inicio < fin entonces
		indice_pivote=Partir( V, inicio, fin )           /* dividir */
        	QuickSort ( V, inicio, indice_pivote-1 )         /* resolver */
        	QuickSort ( V, indice_pivote+1, fin )            /* resolver */
        fsi
fprocedimiento

donde la llamada inicial a la función es: QuickSort(V, 1, n)

$T(n) \in \Omega(nlog_{2}n)$ y $T(n) \in O(n^{2})$

La selección del pivote debe minimizar la posibilidad de obtener una partición desequilibrada.

Diferentes estrategias de elección del pivote:

• Seleccionar el primer elemento del vector:

  Mala elección si el vector está ordenado (pivote = minimo(vector))

• Elegir el elemento central:

  Perfecto si el vector ya está ordenado. Más que elegir un buen pivote, evita elegir uno malo.

• Partición con la mediana del vector.

  Mediana de un grupo N de elementos: El N/2-ésimo menor elemento. Esta es la elección perfecta para cualquier vector de entrada

Mergesort vs Quicksort

Tanto QuickSort como MergeSort resuelven de manera recursiva dos subproblemas.

QuickSort NO garantiza que el tamaño de los subproblemas sea el mismo (MergeSort sí).

QuickSort es más rápido porque el paso de partir puede hacerse más rápido que el paso de fusión en MergeSort.

QuickSort no requiere un vector auxiliar.

QuickSort es el mejor algoritmo para la ordenación de vectores de gran dimensión.

En el campus virtual se encuentra disponible un fichero comprimido con las implementaciones en Python de los siguientes algoritmos:

• Búsqueda binaria

• Mergesort

• Quicksort