# 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$$ ```c 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$$ ```c 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$$ ```c 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]\ 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]

```c 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.

```c 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 --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://nahuels-organization.gitbook.io/algoritmia/algoritmia/tema-3-divide-y-venceras/ejemplos.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.