cap1.2 tutor recursividad vectores

Programación II

Recursión con Vectores

Ing. Mary López

Universidad Autónoma Gabriel Rene MorenoFICCT

Semestre II/2015

Ejercicio 1Búsqueda Binaria

bool BusBin(int *vec,int inicio,int final,int clave) { bool flag,res; if(inicio > final) flag=false; else {

int m = (inicio + final)/2;int x=vec[m];if(clave < x) flag = BusBin(vec, inicio, m-1, clave);else if(clave > x) flag = BusBin(vec, m+1, final, clave); else flag = true;

} return flag;

}

AlgoritmosDe

Ordenación

Algoritmos de Ordenación

La ordenación de elementos según un orden ascendente o descendente influye en la velocidad y simplicidad de los algoritmos que los manipulan.

En general, un conjunto de elementos se almacenan en forma ordenada con el fin de simplificar la recuperación de información manualmente, o facilitar el acceso mecanizado a los datos de una manera más eficiente.

Cada algoritmo ordenación estará compuesto de las siguientes operaciones básicas: COMPARACIONES que prueban si A i< A j ó A i < B

(donde B es una variable auxiliar) INTERCAMBIOS: permutar los contenidos de A i y A j

ASIGNACIONES de la forma B = Ai Ai = Aj Aj= B

Ejercicio 2: MergeSort (Ver 2)

Prerrequisito : Comprender la Recursión

El MERGESORT consiste en : Dividir los elementos en dos grupos de la misma

longitud aproximadamente. Ordenar de forma independiente cada sub-grupo. Mezclar los dos subgrupos ordenados para producir

la secuencia final ordenada.

Algoritmo de fácil división y difícil unión

Ejercicio 2: MergeSort

Una ejecución de merge-sort esta representado por un árbol binario :

La raíz es la primera llamada Cada nodo representa una llamada recursiva de merge-sort

• La secuencia esta sin ordenar antes de la ejecución y después de su partición

• La Secuencia se ordenada al final de la ejecución. Cada hoja es llamada hasta obtener secuencia de longitud

cero o un solo elemento.

6 2 9 4 3 8 6 1

Particion del conjunto en 2 partes

7 2 9 4 2 4 7 9 3 8 6 1 1 3 8 6

7 2 2 7 9 4 4 9 3 8 3 8 6 1 1 6

7 7 2 2 9 9 4 4 3 3 8 8 6 6 1 1

6 2 9 4 3 8 6 1 1 2 3 4 6 7 8 9

Ejercicio 2: MergeSort

Llamada recursiva partición

6 2 9 4 2 4 7 9 3 8 6 1 1 3 8 6

7 2 2 7 9 4 4 9 3 8 3 8 6 1 1 6

7 7 2 2 9 9 4 4 3 3 8 8 6 6 1 1

6 2 9 4 3 8 6 1 1 2 3 4 6 7 8 9

mergeSort

Ejercicio 2: MergeSort

6 2 9 4 2 4 7 9 3 8 6 1 1 3 8 6

6 2 2 7 9 4 4 9 3 8 3 8 6 1 1 6

7 7 2 2 9 9 4 4 3 3 8 8 6 6 1 1

6 2 9 4 3 8 6 1 1 2 3 4 6 7 8 9

Llamada recursiva Particion

mergeSort

Ejercicio 2: MergeSort

6 2 9 4 2 4 7 9 3 8 6 1 1 3 8 6

6 2 2 7 9 4 4 9 3 8 3 8 6 1 1 6

6 6 2 2 9 9 4 4 3 3 8 8 6 6 1 1

6 2 9 4 3 8 6 1 1 2 3 4 6 7 8 9

Llamada recursiva Caso Base

mergeSort

Ejercicio 2: MergeSort

6 2 9 4 2 4 7 9 3 8 6 1 1 3 8 6

6 2 2 7 9 4 4 9 3 8 3 8 6 1 1 6

6 6 2 2 9 9 4 4 3 3 8 8 6 6 1 1

6 2 9 4 3 8 6 1 1 2 3 4 6 7 8 9

Llamada recursiva Caso Base

mergeSort

Ejercicio 2: MergeSort

6 2 9 4 2 4 7 9 3 8 6 1 1 3 8 6

6 2 2 6 9 4 4 9 3 8 3 8 6 1 1 6

6 6 2 2 9 9 4 4 3 3 8 8 6 6 1 1

6 2 9 4 3 8 6 1 1 2 3 4 6 7 8 9

Mezcla Merge

merge

Ejercicio 2: MergeSort

6 2 9 4 2 4 7 9 3 8 6 1 1 3 8 6

6 2 2 6 9 4 3 8 3 8 6 1 1 6

6 6 2 2 9 9 4 4 3 3 8 8 6 6 1 1

6 2 9 4 3 8 6 1 1 2 3 4 6 7 8 9

Llamada recursiva partición

mergeSort

Ejercicio 2: MergeSort

6 2 9 4 2 4 7 9 3 8 6 1 1 3 8 6

6 2 2 6 9 4 3 8 3 8 6 1 1 6

6 6 2 2 9 9 4 4 3 3 8 8 6 6 1 1

6 2 9 4 3 8 6 1 1 2 3 4 6 7 8 9

Llamada recursiva Caso Base

mergeSort

Ejercicio 2: MergeSort

6 2 9 4 2 4 7 9 3 8 6 1 1 3 8 6

6 2 2 6 9 4 3 8 3 8 6 1 1 6

6 6 2 2 9 9 4 4 3 3 8 8 6 6 1 1

6 2 9 4 3 8 6 1 1 2 3 4 6 7 8 9

Llamada recursiva Caso Base

mergeSort

Ejercicio 2: MergeSort

6 2 9 4 2 4 7 9 3 8 6 1 1 3 8 6

6 2 2 6 9 4 4 9 3 8 3 8 6 1 1 6

6 6 2 2 3 3 8 8 6 6 1 1

6 2 9 4 3 8 6 1 1 2 3 4 6 7 8 9

9 9 4 4

Mezcla Merge

merge

Ejercicio 2: MergeSort

Mezcla Merge

6 2 9 4 2 4 6 9

6 2 2 6 9 4 4 9 3 8 6 1 1 6

6 6 2 2 9 9 4 4 3 8 8 6 6 1 1

6 2 9 4 3 8 6 1 1 2 3 4 6 7 8 9

merge

Ejercicio 2: MergeSort

Llamada recursiva Particion

6 2 9 4 2 4 6 9 3 8 6 1

6 2 2 6 9 4 4 9 3 8 6 1 1 6

6 6 2 2 9 9 4 4 3 8 8 6 6 1 1

6 2 9 4 3 8 6 1 1 2 3 4 6 7 8 9

mergeSort

Ejercicio 2: MergeSort

Llamada recursiva Particion

6 2 9 4 2 4 6 9 3 8 6 1

6 2 2 6 9 4 4 9 3 8 3 8 6 1 1 6

6 6 2 2 9 9 4 4 8 8 6 6 1 1

6 2 9 4 3 8 6 1 1 2 3 4 6 7 8 9

mergeSort

Ejercicio 2: MergeSort

Llamada recursiva Caso Base

6 2 9 4 2 4 6 9 3 8 6 1

6 2 2 6 9 4 4 9 3 8 3 8 6 1 1 6

6 6 2 2 9 9 4 4 3 3 8 8 6 6 1 1

6 2 9 4 3 8 6 1 1 2 3 4 6 7 8 9

mergeSort

Ejercicio 2: MergeSort

Llamada recursiva Caso Base

6 2 9 4 2 4 6 9 3 8 6 1

6 2 2 6 9 4 4 9 3 8 3 8 6 1 1 6

6 6 2 2 9 9 4 4 3 3 8 8 6 6 1 1

6 2 9 4 3 8 6 1 1 2 3 4 6 7 8 9

mergeSort

Ejercicio 2: MergeSort

Mezcla Merge

6 2 9 4 2 4 6 9 3 8 6 1

6 2 2 6 9 4 4 9 3 8 3 8 6 1 1 6

6 6 2 2 9 9 4 4 3 3 8 8 6 6 1 1

6 2 9 4 3 8 6 1 1 2 3 4 6 7 8 9

merge

Ejercicio 2: MergeSort

Llamada recursiva partición

6 2 9 4 2 4 6 9 3 8 6 1

6 2 2 6 9 4 4 9 3 8 3 8 6 1 6

6 6 2 2 9 9 4 4 3 3 8 8 6 6 1 1

6 2 9 4 3 8 6 1 1 2 3 4 6 7 8 9

mergeSort

Ejercicio 2: MergeSort

Llamada recursiva Caso Base

6 2 9 4 2 4 6 9 3 8 6 1

6 2 2 6 9 4 4 9 3 8 3 8 6 1 6

6 6 2 2 9 9 4 4 3 3 8 8 6 6

6 2 9 4 3 8 6 1 1 2 3 4 6 7 8 9

mergeSort

Ejercicio 2: MergeSort

Llamada recursiva Caso Base

6 2 9 4 2 4 6 9 3 8 6 1

6 2 2 6 9 4 4 9 3 8 3 8 6 1 6

6 6 2 2 9 9 4 4 3 3 8 8 6 6 1 1

6 2 9 4 3 8 6 1 1 2 3 4 6 7 8 9

mergeSort

Ejercicio 2: MergeSort

Mezcla Merge

6 2 9 4 2 4 6 9 3 8 6 1 |

6 2 2 6 9 4 4 9 3 8 3 8 6 1 1 6

6 6 2 2 9 9 4 4 3 3 8 8 6 6 1 1

6 2 9 4 3 8 6 1 1 2 3 4 6 7 8 9

merge

Ejercicio 2: MergeSort

Mezcla Merge

6 2 9 4 2 4 6 9 3 8 6 1 1 3 6 8

6 2 2 6 9 4 4 9 3 8 3 8 6 1 1 6

6 6 2 2 9 9 4 4 3 3 8 8 6 6 1 1

6 2 9 4 3 8 6 1 1 2 3 4 6 7 8 9

merge

Ejercicio 2: MergeSort

6 2 9 4 2 4 6 9 3 8 6 1 1 3 6 8

6 2 2 6 9 4 4 9 3 8 3 8 6 1 1 6

6 6 2 2 9 9 4 4 3 3 8 8 6 6 1 1

6 2 9 4 3 8 6 1 1 2 3 4 6 6 8 9

Mezcla Merge

merge

Ejercicio 2: MergeSort

Ejercicio 2: MergeSort

void mergeSort (int *A, unsigned int bajo, unsigned int alto, unsigned int n) {

if (bajo < alto) { //Si hay más de un elemento

int medio = (alto + bajo)/2;

mergeSort (A, bajo, medio,n);

mergeSort (A, medio+1, alto,n); //Proceso que mezcla el resultado de las dos llamadas anteriores

merge (A, bajo, medio+1, alto,n);

}

}

Ejercicio 2: MergeSort

void merge (int *A, unsigned int bajo, unsigned int medio, unsigned int alto,unsigned int n){unsigned int ini_1 = bajo; //Variable de primer elemento de la primera subsecunsigned int fin_1 = medio -1; //Variable del último elemento de la primera subsecunsigned int ini_2 = medio; //Variable del primer elemento de la segunda subsecunsigned int i = bajo; //Variable para controlar posiciones del vector resultanteint *Temp=new int[n];/* Temp es un array ya definido*/while (( ini_1 <= fin_1) && (ini_2<= alto)) { if (A[ini_1] <= A[ini_2]) Temp[i++] = A[ini_1++]; else Temp[i++] = A[ini_2++]; }

Ejercicio 2: MergeSort

while (ini_1 <= fin_1) //Si se agotaron los elementos de la segunda subsecuencia Temp[i++] = A[ini_1++];while (ini_2 <= alto) //Si se agotaron los de la primera subsecuencia Temp[i++] = A[ini_2++];//Paso todos los elementos del Temporal al arrayfor (i = bajo; i <= alto; i++) A[i] = Temp[i];}

Ejercicio 3QuickSort

En la ordenación rápida, la secuencia inicial de elementos se divide en dos sub-secuencias de diferente tamaño.

La obtención de las dos sub-secuenciases el proceso que acarrea más tiempo mientras que la combinación de las sub-secuencias ordenadas para obtener la secuencia final consume muy poco tiempo.

Para dividir en dos la secuencia de elementos, se selecciona un elemento sobre el cual efectuar la división, el PIVOTE.

Se dividen los elementos en dos grupos, los elementos menores que el pivote y aquellos mayores o igual al pivote.

Algoritmo de difícil división y fácil unión,

Ejercicio 3QuickSort

La elección del elemento Pivote se puede seleccionar de diferentes formas: El mayor de los dos primeros elementos distintos encontrados. Otros criterios (1ro, Ultimo, el del centro, etc).

Para ordenar los elementos comprendidos entre Ai y Aj

1. Si desde Ai hasta Aj hay al menos dos elementos distintos

entonces comenzar la aplicación del algoritmo.2. Seleccionar el PIVOTE como el elemento mayor de los dos

primeros elementos distintos encontrados.3. Insertar PIVOTE en la última posición.

Ejercicio 3QuickSort

4. Permutar los elementos desde Ai hasta Aj de modo que, para algún i <= k <= j :

Ai, ..., Ak-1< PIVOTE

Ak, ..., Aj>= PIVOTE

Es decir, en las (k-1) primeras posiciones queden los elementos menores que pivote, mientras que en la posición k hacia delante queden los elementos mayores o iguales que el pivote.

5. Invocar a:

QUICKSORT desde i hasta (k –1)QUICKSORT desde k hasta j

Ejercicio 3QuickSort

35

1) Elegir Pivote: Tomar un elemento

2) Dividir: Reordenar los elementos tal que x va a su posición final E

3) Recursión y Vencer: Ordenar recursivamente

Ejercicio 3 - QuickSortInicia

Ejercicio 3 - QuickSortÍndicePivotei ini Fin

0 1 2 3 4 5 6 77 6 2 10 4 5 9 8 Pivote

Como 10 es mayor que 8 este no esta en una posición correcta. Luego debemos continuar avanzando con i hasta encontrar uno menor que el pivote 8.

ÍndicePivoteini i Fin

0 1 2 3 4 5 6 77 6 2 10 4 5 9 8 Pivote

Como 10 es mayor que 8 este no esta en una posición correcta. Luego debemos continuar avanzando con i hasta encontrar uno menor que el pivote 8.

ÍndicePivoteini i Fin

0 1 2 3 4 5 6 77 6 2 10 4 5 9 8 Pivote

Encontramos el 4. Luego este lo intercambiamos por el 10

Partir (1)

Ejercicio 3 - QuickSort

ÍndicePivoteini i Fin

0 1 2 3 4 5 6 77 6 2 4 10 5 9 8 Pivote

Como 10 es mayor que 8 este no esta en una posición correcta. Luego debemos continuar avanzando con i hasta encontrar uno menor que el pivote 8.

ÍndicePivoteini i Fin

0 1 2 3 4 5 6 77 6 2 4 10 5 9 8 Pivote

Encontramos el 4. Luego este lo intercambiamos por el 10

ÍndicePivoteini i Fin

0 1 2 3 4 5 6 77 6 2 4 5 10 9 8 Pivote

Encontramos el 5. Luego este lo intercambiamos por el 10

Ejercicio 3 - QuickSort

ÍndicePivoteini i Fin

0 1 2 3 4 5 6 77 6 2 4 5 10 9 8 Pivote

Como 10 es mayor que 8 este no esta en una posición correcta. Luego debemos continuar avanzando con i hasta encontrar uno menor que el pivote 8.

El apuntador i llego a su posición máxima. Finalmente hay que mover el pivote 8 a la posición donde quedo el apuntador indicepivote ya que este es mayor y debe ir a la derecha.

ÍndicePivoteini   Fin

0 1 2 3 4 5 6 77 6 2 4 5 10 9 8 Pivote

ÍndicePivoteini   Fin

0 1 2 3 4 5 6 77 6 2 4 5 8 9 10

PivoteEl algoritmo termina poniendo el Pivote en su posición de ordenación correcta y al mismo tiempo divide al conjunto en 2 para continuar ordenando

Ejercicio 3 - QuickSort

partición

Ejercicio 3 - QuickSort

quickSort (I)

Ejercicio 3 - QuickSort

0 1 2 3 47 6 2 4 5 ip piv ini fin i

0 5 0 4 01 1

0 1 2 3 4 2 22 6 7 4 5 3

4

0 1 2 3 42 4 7 6 5

0 1 2 3 42 4 5 6 7

Partir (2)

partición

Ejercicio 3 - QuickSort

0 12 4 ip piv ini fin i

0 4 0 1 01 1

0 12 4

0 12 4

Partir (3)

Ejercicio 3 - QuickSort

quickSort (I)

Ejercicio 3 - QuickSort

partición

Ejercicio 3 - QuickSort

partición

Ejercicio 3 - QuickSort

partición

Ejercicio 3 - QuickSort

partición

Ejercicio 3 - QuickSort

partición

Ejercicio 3 - QuickSort

Ejercicio 3 - QuickSort

Ejercicio 3 - QuickSort

quickSort (D)

Ejercicio 3 - QuickSort

partición

Ejercicio 3 - QuickSort

partición

Ejercicio 3 - QuickSort

partición

Ejercicio 3 - QuickSort

partición

Ejercicio 3 - QuickSort

partición

Ejercicio 3 - QuickSort

Ejercicio 3 - QuickSort

Ejercicio 3 - QuickSort

Ejercicio 3 - QuickSort

quickSort (D)

Ejercicio 3 - QuickSort

partición

Ejercicio 3 - QuickSort

partición

Ejercicio 3 - QuickSort

partición

Ejercicio 3 - QuickSort

partición

Ejercicio 3 - QuickSort

partición

Ejercicio 3 - QuickSort

Ejercicio 3 - QuickSort

Ejercicio 3 - QuickSort

Ejercicio 3: QuickSort

void quickSort( int *A, int ini, int fin ){

if (ini < fin){

int indicepivote = particion(A,ini, fin); //El pivote ya esta en su posición correcta //Por eso no se lo toma encuenta en la union

quickSort(A, ini, indicepivote – 1 );quickSort(A, indicepivote+1, fin);

}

}

Ejercicio 3: QuickSort

int particion(int *A,int ini, int fin){int pivote = A[fin];int indicepivote = ini;for ( int i=indicepivote; i< fin ; i++) { if (A[i] < pivote) { //Intercambiar solo si i es distinto de indicepivote

intercambiar(A, i ,indicepivote); indicepivote=indicepivote+1; } } intercambiar(A, indicepivote,fin); return indicepivote;}

Ejercicio 3: QuickSort

void intercambiar( int *A, int ptr1, int ptr2 ){ int temp; temp = A[ptr1]; A[ptr1] = A[ptr2]; A[ptr2] = temp;}