8 _Ruby_03 PB

Vista previa del material en texto

Programación Básica
1
Eugenio Alvarado Pérez
Of. 28-B, Edificio 80
eugenio.alvarado@udep.pe
Programación Básica
Unidad 3
Tema 8: Ordenamiento y búsqueda
E1 E2
19853037 OTERO SAAVEDRA, LUIS FELIPE 5 7
20003156 FLORES LIZANA, ESTHER ALEJANDRA 6 10
20013706 VASQUEZ CASTILLO, ALBERTO JUAN 16 13
20023091 GAYOSO DIAZ, MILAGROS CECILIA 10 6
20023110 VILLA BARRIOS, ALONSO PATRICIO 10 10
20023229 MINCHEZ LOPEZ, ANTONIO PEDRO 12 19
20023320 CORDOVA ROMAN, MIGUEL MARTIN 3 12
20023390 CHICOMA CAMPOS, PEDRO MIGUEL 4 7
20023457 MONCADA HORNOS, ALBERTO MANUEL 10 13
20033006 MILLA ARAGON, LUCIA ANA 9 6
20033019 CAMPOS BARBA, ALBERTO JOSE 7 9
20033027 LINAREZ ATARAMA, MARTIN JAVIER 16 14
20033081 CARRION VILCHEZ, FIORELLA PATRICIA 14 16
20033100 LABRIN PEREZ, PATRICIA MERCEDES 14 11
20033112 FARIAS CABREDO, LILIANA MARIA 6 5
20033136 DILLON RODRIGUEZ, ALEJANDRO LUIS 6 12
20033138 RAMOS PAZ, MIGUEL MANUEL 9 10
20033143 BENITES VALCARCEL, ROBERTO MANUEL 7 12
20033172 ORTEGA JUAREZ, ALEJANDRO MIGUEL 0 11
20033189 RODRIGUEZ SEMINARIO, ALEJANDRO PEDRO 8 10
20033234 REATEGUI COLAN, EDUARDO ROBERTO 11 8
20033258 ZAPATA AGUILA, ANDRES MANUEL 8 8
20033270 VERA GUEVARA, EDUARDO MARTIN 11 6
20033324 LEON ALVARADO, ALFREDO MANUEL 11 9
20033338 FERNANDEZ RUIZ, ALFONSO MANUEL 10 10
20033422 AMAYO PALACIOS, MARIA MABEL 14 10
20033444 CARBAJAL VALERA, FRANCO DAVID 11 9
¿Cuánto obtuvo de nota en el E2 el 
alumno Alfredo León?
2/38
E1 E2
20033422 AMAYO PALACIOS, MARIA MABEL 14 10
20033143 BENITES VALCARCEL, ROBERTO MANUEL 7 12
20033019 CAMPOS BARBA, ALBERTO JOSE 7 9
20033444 CARBAJAL VALERA, FRANCO DAVID 11 9
20033081 CARRION VILCHEZ, FIORELLA PATRICIA 14 16
20023390 CHICOMA CAMPOS, PEDRO MIGUEL 4 7
20023320 CORDOVA ROMAN, MIGUEL MARTIN 3 12
20033136 DILLON RODRIGUEZ, ALEJANDRO LUIS 6 12
20033112 FARIAS CABREDO, LILIANA MARIA 6 5
20033338 FERNANDEZ RUIZ, ALFONSO MANUEL 10 10
20003156 FLORES LIZANA, ESTHER ALEJANDRA 6 10
20023091 GAYOSO DIAZ, MILAGROS CECILIA 10 6
20033100 LABRIN PEREZ, PATRICIA MERCEDES 14 11
20033324 LEON ALVARADO, ALFREDO MANUEL 11 9
20033027 LINAREZ ATARAMA, MARTIN JAVIER 16 14
20033006 MILLA ARAGON, LUCIA ANA 9 6
20023229 MINCHEZ LOPEZ, ANTONIO PEDRO 12 19
20023457 MONCADA HORNOS, ALBERTO MANUEL 10 13
20033172 ORTEGA JUAREZ, ALEJANDRO MIGUEL 0 11
19853037 OTERO SAAVEDRA, LUIS FELIPE 5 7
20033138 RAMOS PAZ, MIGUEL MANUEL 9 10
20033234 REATEGUI COLAN, EDUARDO ROBERTO 11 8
20033189 RODRIGUEZ SEMINARIO, ALEJANDRO PEDRO 8 10
20013706 VASQUEZ CASTILLO, ALBERTO JUAN 16 13
20033270 VERA GUEVARA, EDUARDO MARTIN 11 6
20023110 VILLA BARRIOS, ALONSO PATRICIO 10 10
20033258 ZAPATA AGUILA, ANDRES MANUEL 8 8
¿Cuánto obtuvo de nota en el E1 el 
alumno Eduardo Vera?
3/38
Ordenar
4/38
Ordenar
5/38
Ordenamiento (sort)
55 86 48 16 82
Orden ascendente
16 48 55 82 86
6/38
Programación Básica
2
Ordenamiento (sort)
55 86 48 16 82
Orden ascendente
Comparar
Intercambiar
Iterar
7/38
Algoritmos de ordenamiento
Sorting refers to arranging data in a particular format. Sorting algorithm
specifies the way to arrange data in a particular order. Most common
orders are numerical or lexicographical order.
Importance of sorting lies in the fact that data searching can be
optimized to a very high level if data is stored in a sorted manner. Sorting
is also used to represent data in more readable formats. Some of the
examples of sorting in real life scenarios are following.
• Telephone Directory − Telephone directory keeps telephone no. of
people sorted on their names. So that names can be searched.
• Dictionary − Dictionary keeps words in alphabetical order so that
searching of any work becomes easy.
Fuente: www.tutorialspoint.com/data_structures_algorithms/sorting_algorithms.htm
8/38
Algoritmos de ordenamiento
• Insertion sort
• Selection sort
• Bubble sort
• Shell sort
• Merge sort
• Heap sort
• Quick sort
• Quick3 sort
http://www.sorting-algorithms.com/
https://es.wikipedia.org/wiki/Algoritmo_de_ordenamiento
https://es.wikipedia.org/wiki/Ordenamiento_de_burbuja
https://es.wikipedia.org/wiki/Ordenamiento_por_selecci%C3%B3n
http://www.tutorialspoint.com/data_structures_algorithms/bubble_sort_algorithm.htm
http://www.tutorialspoint.com/data_structures_algorithms/selection_sort_algorithm.htm
https://www.youtube.com/watch?v=8Kp-8OGwphY
https://www.youtube.com/watch?v=f8hXR_Hvybo
9/38
Ordenamiento de burbuja
El ordenamiento de burbuja (bubble sort) es un algoritmo
sencillo de ordenamiento. Funciona revisando cada elemento
de la lista con el siguiente, intercambiándolos si están en el
orden equivocado. Es necesario revisar varias veces toda la
lista hasta que no se necesiten más intercambios, lo cual
significa que la lista está ordenada. Este algoritmo obtiene su
nombre de la forma con la que suben por la lista los
elementos durante los intercambios, como si fueran pequeñas
"burbujas“…
Fuente: WIKIPEDIA
10/38
Ordenamiento de burbuja
55 86 48 16 82
Ascendente
Si el elemento siguiente 
es menor, entonces se 
intercambian
11/38
Ordenamiento de burbuja
55 48 16 82 86
Ascendente

Luego de comparar todos los 
elementes, el mayor se ubica 
último y se comienza nuevamente
12/38
http://www.sorting-algorithms.com/
https://es.wikipedia.org/wiki/Algoritmo_de_ordenamiento
http://www.tutorialspoint.com/data_structures_algorithms/bubble_sort_algorithm.htm
http://www.tutorialspoint.com/data_structures_algorithms/bubble_sort_algorithm.htm
http://www.tutorialspoint.com/data_structures_algorithms/bubble_sort_algorithm.htm
http://www.sorting-algorithms.com/
https://www.youtube.com/watch?v=f8hXR_Hvybo
https://www.youtube.com/watch?v=f8hXR_Hvybo
Programación Básica
3
Ordenamiento por selección
#Ordenamiento de burbuja
a = [55,86,48,16,82]
n = a.size
puts a.to_s
for i in 1..n
for j in 0..n-1-i
if a[j] > a[j+1]
x = a[j+1]
a[j+1] = a[j]
a[j] = x
end
end
end
puts a.to_s
13/38
Ordenamiento por selección
#Ordenamiento de burbuja
a = [55,86,48,16,82]
n = a.size
puts a.to_s
for i in 1..n
for j in 0..n-1-i
if a[j] > a[j+1]
x = a[j+1]
a[j+1] = a[j]
a[j] = x
end
end
end
puts a.to_s
Comparar
Intercambiar
Iterarx = a[j+1]
a[j+1] = a[j]
a[j] = x
14/38
Ordenamiento por selección
55 86 48 16 82
Ascendente
Se compara el primer elemento 
con cada uno del resto, si alguno 
de éstos es menor que, entonces 
se intercambian
15/38
Ordenamiento por selección
16 86 55 48 82
Ascendente

Luego de comparar todos los elementes, 
el menor se ubica primero y se repite la 
operación con el segundo…
16/38
Ordenamiento por selección#Ordenamiento por selección
a = [55,86,48,16,82]
n = a.size
for i in 0..n-2
for j in i+1..n-1
if a[i] > a[j]
x = a[i]
a[i] = a[j]
a[j] = x
end
end
end
puts a.to_s
Comparar
Intercambiar
Iterar
17/38 18/38
Programación Básica
4
Ejercicio 1
La empresa XYZ tiene un registro de todos los pedidos
(ventas) realizados el año 2015 por sus clientes. El gerente
general de XYZ desea saber, qué vendedores realizaron los 5
pedidos de mayor importe. Escriba el programa que procese
los datos (BD02.txt) y muestre en pantalla una lista que
contenga: Id. del pedido, vendedor y el importe del pedido.
BD02.txt PRG01
19/38
Ejercicio 2
Una empresa muy importante ha solicitado al director del PA
de IIS una lista de los alumnos de su PA que están en ciclos 9
o 10 y que sean del tercio superior. La empresa desea
contratar a dichos alumnos como practicantes. Escriba el
programa que procese los datos (BD01.txt) y muestre en
pantalla una lista que contenga: carné, nombre, IA, según el
perfil requerido.
BD01.txt PRG02
20/38
Ejercicio 3
La empresa XYZ tiene un registro de todos los pedidos
(ventas) realizados el año 2015 por sus clientes. El gerente
general de XYZ desea saber, qué vendedor vendió más (por
importe) dicho año. Escriba el programa que procese los
datos (BD02.txt) y muestre en pantalla el vendedor, la
cantidad de pedidos atendidos y su importe.
BD02.txtPRG03
21/38
Hasta la próxima clase…
22/38
Algoritmo de búsqueda
Aquel que está diseñado para localizar un elemento con
ciertas propiedades dentro de una estructura de datos; por
ejemplo, ubicar el registro correspondiente a cierta persona
en una base de datos. Un ejemplo simple sería la
búsqueda de un dato en un array.
Búsqueda secuencial
Consiste en buscar un elemento comparándolo secuencial-
mente (de ahí su nombre) con cada elemento del vector
hasta encontrarlo, o hasta que se llegue al final. La
existencia se puede asegurar cuando el elemento es
localizado, pero no podemos asegurar la no existencia
hasta no haber analizado todos los elementos del array.
23/38
Algoritmo de búsqueda
Búsqueda secuencial ¿dónde está 
la “M”?
24/38
Programación Básica
5
Algoritmo de búsqueda
Búsqueda binaria
El array debe estar ordenado de manera ascendente. Se
compara el elemento a buscar con el elemento central; si
el valor de éste es mayor que el del elemento buscado se
repite el procedimiento en la parte del vector que va desde
el inicio de éste hasta el elemento central, caso contrario
se toma la parte del vector que va desde el elemento
central hasta el final. De esta manera obtenemos intervalos
cada vez más pequeños, hasta que se obtenga un
intervalo indivisible. Si el elemento no se encuentra dentro
de este último entonces se deduce que el elemento
buscado no se encuentra en todo el vector.
25/38
Algoritmo de búsqueda
Búsqueda binaria
¿dónde está 
el “22”?
26/38
Algoritmo de búsqueda
Búsqueda binaria
¿dónde está 
el “22”?
27/38
Algoritmo de búsqueda
Búsqueda binaria
¿dónde está 
el “22”?
28/38
Búsqueda binaria
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 4 7 8 11 15 18 21 24 25 26 27 30 33 35 40
¿En qué ubicación está el 15?
29/38
Búsqueda binaria
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 4 7 8 11 15 18 21 24 25 26 27 30 33 35 40
  
¿En qué ubicación está el 15?
30/38
Programación Básica
6
Búsqueda binaria
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 4 7 8 11 15 18 21 24 25 26 27 30 33 35 40
1 4 7 8 11 15 18 21 24 25 26 27 30 33 35 40
¿En qué ubicación está el 15?
31/38
Búsqueda binaria
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 4 7 8 11 15 18 21 24 25 26 27 30 33 35 40
1 4 7 8 11 15 18 21 24 25 26 27 30 33 35 40
  
¿En qué ubicación está el 15?
32/38
Búsqueda binaria
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 4 7 8 11 15 18 21 24 25 26 27 30 33 35 40
1 4 7 8 11 15 18 21 24 25 26 27 30 33 35 40
1 4 7 8 11 15 18 21 24 25 26 27 30 33 35 40
¿En qué ubicación está el 15?
33/38
Búsqueda binaria
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 4 7 8 11 15 18 21 24 25 26 27 30 33 35 40
1 4 7 8 11 15 18 21 24 25 26 27 30 33 35 40
1 4 7 8 11 15 18 21 24 25 26 27 30 33 35 40
  
¿En qué ubicación está el 15?
34/38
Búsqueda binaria
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 4 7 8 11 15 18 21 24 25 26 27 30 33 35 40
1 4 7 8 11 15 18 21 24 25 26 27 30 33 35 40
1 4 7 8 11 15 18 21 24 25 26 27 30 33 35 40
1 4 7 8 11 15 18 21 24 25 26 27 30 33 35 40
  
¿En qué ubicación está el 15?
35/38
Búsqueda binaria
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 4 7 8 11 15 18 21 24 25 26 27 30 33 35 40
1 4 7 8 11 15 18 21 24 25 26 27 30 33 35 40
1 4 7 8 11 15 18 21 24 25 26 27 30 33 35 40
1 4 7 8 11 15 18 21 24 25 26 27 30 33 35 40
1 4 7 8 11 15 18 21 24 25 26 27 30 33 35 40
¿En qué ubicación está el 15?
36/38
Programación Básica
7
Ejercicio 4
Se requiere un programa que busque en la base de datos de
alumnos, a partir del número de carné; el programa debe
permitir búsquedas múltiples. Escriba el programa que
procese los datos (BD05.txt), busque (binaria) y muestre en
pantalla una lista que contenga: carné, nombre, PA, de los
alumnos buscados.
BD05.txt PRG04
37/38
Hasta la próxima clase…
38/38