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”.-
Potencia n-esima de a según Divide y Vencerás
¿POTENCIA_DyV (a, n)?
Resolvemos cada subproblema de forma independiente
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:
“Dividir” el vector V por la mitad ( m = (1+n) div 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]
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:
“Dividir” el vector V por la mitad ( m = (1+n) div 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.
Combinar (mezclar) en tiempo lineal las dos secciones del vector ya ordenadas para generar la ordenación del vector V[1..n]
donde la llamada inicial a la función es: MergeSort(V, 1, 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.
donde la llamada inicial a la función es: QuickSort(V, 1, n)
Ejemplo del funcionamiento de Partir
V[inicio] será el pivote elegido.
A continuación se procede a recolocar los elementos del vector.
donde la llamada inicial a la función es: QuickSort(V, 1, n)
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
Last updated