Sesión 09_Mg Orleans Gálvez Tapia

Vista previa del material en texto

ANÁLISIS DE ALGORITMOS Y 
ESTRATEGIAS DE PROGRAMACIÓN
Docente: 
Mg. Gálvez Tapia Orleans Moisés
CIP. 171497
UNIDAD 1:
LA COMPLEJIDAD ALGORÍTMICA Y 
PRINCIPALES ESTRATEGIAS DE 
PROGRAMACIÓN
SEMANA 09: Divide y vencerás
¿Qué algoritmos de 
ordenamiento 
conoce?
SABERES PREVIOS
AGENDA:
1. Características de los algoritmos Divide y Vencerás (Divide y Conquista)
2. Algoritmo de ordenamiento por Selección en Python y Java
3. Algoritmo de ordenamiento Quicksort en Python y Java
4. Algoritmo de ordenamiento Shell en Python y Java
5. Algoritmo de Búsqueda Binaria en Python y Java
6. Conclusiones
7. Referencias Bibliográficas
LOGRO DE LA SESIÓN
Al término de la clase, el estudiante implementa algoritmos 
de ordenamiento y búsqueda en Python mostrando dominio 
técnico del lenguaje y una lógica coherente.
ALGORITMOS DIVIDE Y VENCERÁS
Un algoritmo Divide y Vencerás resuelve un problema en 3 pasos:
1. Divide el problema en un número de subproblemas que son
instancias más pequeñas del mismo problema.
2. Vence los subproblemas al resolverlos de manera recursiva. Si
son los suficientemente pequeños, resuelve los subproblemas como
casos base.
3. Combina las soluciones de los subproblemas en la solución para el
problema original.
ALGORITMOS DIVIDE Y VENCERÁS
Si expandimos la cantidad de pasos recursivos, se ve así:
APLICACIÓN DEL PARADIGMA DIVIDE Y VENCERÁS
ORDENAMIENTO QUICKSORT
QuickSort ordena recursivamente un arreglo dividiéndolo en dos
subarreglos.
o Si el subarreglo tiene tamaño 0 o 1, entonces ya está
ordenado, y no tiene que hacerse nada.
o De lo contrario, QuickSort utiliza divide y vencerás para
ordenar al subarreglo.
El paso de dividir debe hacer una partición del arreglo (pivote), el
paso de vencer debe hacer ordenamiento rápido recursivamente
en los subarreglos divididos y el paso de combinar no debe hacer
nada.
El método de ordenación por selección consiste en repetir los siguientes pasos:
1. Se busca el elemento más pequeño del array y se coloca en la primera posición.
2. Entre los restantes, se busca el elemento más pequeño y se coloca en la segunda posición.
3. Entre los restantes se busca el elemento más pequeño y se coloca en la tercera posición.
Este proceso se repite hasta colocar el último elemento.
50 26 7 9 15 27
7
De forma gráfica el proceso sería el siguiente:
5026 9 15 27
9 2650 15 27
5015 26 27
27 50
5026 27
Array original
Se coloca el 7 en la primera posición. Se intercambian 7 y 50.
Se coloca el 9 en la segunda posición. Se intercambian 9 y 26.
Se coloca el 15 en la tercera posición. Se intercambian 15 y 50.
El menor de los que queda es 26. Se deja en su posición.
Se coloca el 27 en la quinta posición. Se intercambian 27 y 50.
ALGORITMO DE ORDENAMIENTO POR SELECCIÓN
//método java de ordenación por selección
public static void seleccion(int A[]) {
int i, j, menor, pos, tmp;
for (i = 0; i < A.length - 1; i++) {
menor = A[i];
pos = i;
for (j = i + 1; j < A.length; j++){
if (A[j] < menor) {
menor = A[j];
pos = j;
}
}
if (pos != i){
tmp = A[i];
A[i] = A[pos];
A[pos] = tmp;
}
}
}
50 26 7 9 15 27
26 9 15 27
26
5015 26 27
27 26
7 50
i = 0; i < A.length - 1; i++
j = i + 1; j < A.length; j++
5026 27
50 15 279
Tomamos como menor el primero de los elementos 
que quedan por ordenar y guardamos su posición
Buscamos en el resto del array algún
elemento menor que el actual
Si hay alguno menor se intercambia
ALGORITMO DE ORDENAMIENTO POR SELECCIÓN
ALGORITMO DE ORDENAMIENTO POR SELECCIÓN EN PYTHON
[0] [1] [2] [3] [4] [5]
10 40 7 9 15 27
10 40 7 9 15 27
10 40 7 9 15 27
i j
10 9 7 40 15 27
10 9 7 40 15 27
j i
7 9 10 40 15 27
Subarray 1 Subarray 2
Array original a ordenar
Se toma como pivote el primer elemento
Se intercambian
La búsqueda de izquierda a derecha encuentra el 40,
mayor que el pivote y la búsqueda de derecha a
izquierda encuentra el 9, menor que el pivote
Continua la búsqueda, se encuentra el valor 40
mayor que el pivote y el valor 7 menor que el pivote,
pero ya se han cruzado. PARAMOS
Finalmente colocamos el pivote en su lugar (posición
j). Quedando el array dividido en dos subarrays a los
que se aplicará el mismo proceso.
ALGORITMO DE ORDENAMIENTO QUICKSORT
[0] [1] [2] [3] [4] [5]
7 9 10 40 15 27
[ izq] [ j -1] [ j ] [ j+1 ] [ der]
Subarray 1 Subarray 2
ALGORITMO DE ORDENAMIENTO QUICKSORT
ALGORITMO DE ORDENAMIENTO QUICKSORT EN PYTHON
public void quicksort(int izq, int der) { 
int pivote=vector[izq], i=izq, j=der, aux; 
while(i<j){ 
while(vector[i]<=pivote && i<j) i++; 
while(vector[j]>pivote) j--; 
if (i<j) { 
aux= vector[i]; 
vector[i]=vector[j]; 
vector[j]=aux; 
} 
} 
vector[izq]=vector[j]; 
vector[j]=pivote; 
if(izq<j-1)
quicksort(izq,j-1); 
if(j+1 <der)
quicksort(j+1,der); 
}
// Mientras no se crucen los índices
// Busca elemento mayor que pivote
// Busca elemento menor que pivote
// Si no se han cruzado i y j
/* Intercambio los elementos de las
posiciones i y j */
// Colocamos al pivote a su lugar [j]
/* Si el sub vector izquierdo tiene por lo
menos dos elementos */
/* Si el sub vector derecho tiene por lo
menos dos elementos*/
ALGORITMO DE ORDENAMIENTO QUICKSORT EN JAVA
[0] [1] [2] [3] [4] [5]
50 26 7 9 15 27
26
269 15 277 50
i = salto; i < v.length; i++
salto = t/2; salto !=0; salto/2
5015 279
t = tamaño() = 6
Intercambio = F
Intercambio = V
7
Intercambio = V
Intercambio = F
Intercambio = V
salto = t/2 = 3
Mientras (Intercambio = V)
ALGORITMO DE ORDENAMIENTO SHELL
9 26 277 5015
[0] [1] [2] [3] [4] [5]
26
9 26 277 50
507 279
Intercambio = F
… Continuo otra iteración con el mismo valor del salto (salto = 1)
15
Intercambio = V
Intercambio = F
i = salto; i < v.length; i++
15
26507 279 15
50267 279 15
Intercambio = F
Intercambio = V
27267 509 15
Intercambio = V
Mientras (Intercambio = V)
salto = 3/2 = 1
ALGORITMO DE ORDENAMIENTO SHELL
[0] [1] [2] [3] [4] [5]
9 7 15 26 27 50
27
7 27 5015 26
269 507
Intercambio = F
salto = 1/2; salto =0; salto/2
Como el salto ya es igual a CERO el algoritmo termina
15
Intercambio = V
Intercambio = F
i = salto; i < v.length; i++
9
27269 507 15
27269 507 15
Intercambio = F
Mientras (Intercambio = V)
Intercambio = F
Intercambio = F
salto = 1
ALGORITMO DE ORDENAMIENTO SHELL
ALGORITMO DE ORDENAMIENTO SHELL EN PYTHON
public void shell(){
int salto,aux; 
int t=tamaño(); 
boolean intercambio;
for(salto=t/2; salto!=0; salto=salto/2){
intercambio=true;
while(intercambio){ 
intercambio=false;
for(int i=salto; i<vector.length;i++){ 
if(vector[i-salto]>vector[i]){ 
aux=vector[i]; 
vector[i]=vector[i-salto];
vector[i-salto]=aux;
intercambio=true; 
}
} 
}
}
}
// Se da una pasada con el mismo SALTO
// y si están desordenados
// se intercambian
// y se marca como cambio.
// Mientras se intercambie algún elemento
ALGORITMO DE ORDENAMIENTO SHELL EN JAVA
BÚSQUEDA BINARIA
BÚSQUEDA BINARIA
Elemento buscado: 23
Retornar [5]
BÚSQUEDA BINARIA EN PYTHON
BÚSQUEDA BINARIA
public int busquedaBinaria(){ 
int n=tamaño(), 
int inferior = 0, superior = n-1;
while(inferior <= superior){ 
int centro = (superior + inferior) / 2; 
if (elemento == vector[centro]){
return centro;
} 
else { 
if (elemento < vector[centro]){
superior = centro - 1;
} 
else {
inferior = centro + 1;
} 
} 
} 
return -1; 
}
// mientras exista 
por lo menos un 
elemento en el 
arreglo
CONCLUSIONES
1. Un algoritmo Divide y Vencerás resuelve un problema siguiendo estos 3 pasos.
o Dividir: Descomponer el problema en sub-problemas.
o Vencer: Resolver los sub-problemas recursivamente.
o Combinar las soluciones de los subproblemas en la solución para el problema original.
2. Este enfoque algorítmico trabaja recursivamente y los pasos de Vencer y Combinar trabajan tan a la
par que parece un sólo paso.
REFERENCIAS BIBLIOGRÁFICAS
REFERENCIA ENLACEUna introducción a las matemáticas para el 
análisis y diseño de algoritmos 
https://elibro.bibliotecaupn.elogim.com/es/lc/upnort
e/titulos/35059
Manual de algorítmica: recursividad, complejidad y 
diseño de algoritmos 
https://elibro.bibliotecaupn.elogim.com/es/lc/upnort
e/titulos/56561
Introducción práctica a la programación con 
Python 
https://elibro.bibliotecaupn.elogim.com/es/lc/upnort
e/titulos/124259
Criptografía sin secretos con Python https://elibro.bibliotecaupn.elogim.com/es/lc/upnort
e/titulos/106497
ACM UVA Online http://uva.onlinejudge.org/
ACM ICPC Competition https://icpc.global/compete/preparation
https://elibro.bibliotecaupn.elogim.com/es/lc/upnorte/titulos/35059
https://elibro.bibliotecaupn.elogim.com/es/lc/upnorte/titulos/35059
https://elibro.bibliotecaupn.elogim.com/es/lc/upnorte/titulos/56561
https://elibro.bibliotecaupn.elogim.com/es/lc/upnorte/titulos/56561
https://elibro.bibliotecaupn.elogim.com/es/lc/upnorte/titulos/124259
https://elibro.bibliotecaupn.elogim.com/es/lc/upnorte/titulos/124259
https://elibro.bibliotecaupn.elogim.com/es/lc/upnorte/titulos/106497
https://elibro.bibliotecaupn.elogim.com/es/lc/upnorte/titulos/106497
http://uva.onlinejudge.org/
https://icpc.global/compete/preparation
	Diapositiva 1
	Diapositiva 2
	Diapositiva 3: UNIDAD 1: LA COMPLEJIDAD ALGORÍTMICA Y PRINCIPALES ESTRATEGIAS DE PROGRAMACIÓN
	Diapositiva 4
	Diapositiva 5
	Diapositiva 6
	Diapositiva 7
	Diapositiva 8
	Diapositiva 9
	Diapositiva 10
	Diapositiva 11
	Diapositiva 12
	Diapositiva 13
	Diapositiva 14
	Diapositiva 15
	Diapositiva 16
	Diapositiva 17
	Diapositiva 18
	Diapositiva 19
	Diapositiva 20
	Diapositiva 21
	Diapositiva 22
	Diapositiva 23
	Diapositiva 24
	Diapositiva 25
	Diapositiva 26
	Diapositiva 27
	Diapositiva 28