ALGORITMOS PYTHON-páginas-15

Vista previa del material en texto

[61]
determinado que los algoritmos del orden de O(log n) son mucho más eficientes que los del orden 
de O(n) y esta eficiencia mejora significativamente a medida que aumenta el tamaño de la entrada.
Tamaño de entrada Búsqueda
Secuencial
 O(n)
Binaria
 O(log n)
10 10 4
100 100 7
1 000 1 000 10
10 000 10 000 14
100 000 100 000 17
1 000 000 1 000 000 20
10 000 000 10 000 000 24
100 000 000 100 000 000 27
1 000 000 000 1 000 000 000 30
Figura 23. Comparación comportamiento de algoritmos de búsqueda
[62]
Guía de ejercicios prácticos
A continuación se plantean una serie de actividades que nos permitirán comparar el rendimiento y 
eficiencia de los algoritmos de ordenamiento y búsqueda.
1. Desarrollar el algoritmo de ordenamiento por casilleros (bucket sort).
2. Desarrollar el algoritmo de ordenamiento Shell (shell sort). Tiene este nombre debido a su in-
ventor Donald Shell.
3. Desarrollar el algoritmo de ordenamiento Radix (radix sort).
4. Explicar brevemente el funcionamiento del algoritmo de ordenamiento Timsort y su orden de 
complejidad, –el cual fue desarrollado por Tim Peters en lenguaje Python – este algoritmo es de 
tipo híbrido utilizado de forma nativa para ordenar los elementos de una colección en Python.
5. Generar una lista de elementos aleatorios de distintos tamaños (100 000, 1 000 000, 10 000 
000), para probar los distintos algoritmos de ordenamiento vistos. Además agregar las instruc-
ciones necesarias para medir su tiempo de ejecución y poder compararlos.
6. Generar también otra lista de elementos aleatorios de distintos tamaños (100 000, 1 000 000, 10 
000 000), para probar los distintos algoritmos de búsqueda vistos. Además agregar las instruc-
ciones necesarias para medir su tiempo de ejecución para poder compararlos.
7. Dada una lista de personajes de la saga de Star Wars de las que se conoce su nombre, resolver 
la siguientes tareas:
a. listar los personajes ordenados alfabéticamente de manera ascendente;
b. determinar si el personaje Darth Maul está cargado y en qué posición se encuentra;
c. mostrar la información de los personajes que se encuentran antes y después de Hera Syndulla;
d. listar todos los personajes que comienzan con la letra L;
e. utilizar los métodos de ordenamiento y búsqueda más eficiente de acuerdo al tipo de dato.
8. Se dispone de las lista de superhéroes y villanos de la saga de Marvel Cinematic Universe 
(MCU) de los que contamos con la información de nombre del personaje y año de la primera 
película en la que apareció; a partir de estos resolver las siguientes actividades:
a. realizar un listado ascendente de los personajes ordenados por su nombre;
b. indicar quien fue el primer y el último personaje en aparecer en una película sin realizar 
un recorrido de la lista (podrían ser más de uno tanto el primero como el último);
c. realizar un listado de los personajes ordenados de manera descendente por año de aparición;
[63]
d. calcular el rango de años entre el primer personaje en aparecer y el último;
e. determinar si los personajes Capitan America y Rocket Raccoon están en la lista y en qué 
año aparecieron.
9. Se cuenta con una lista de Pokémons, de cada uno de estos se sabe su nombre, número y tipo 
(solo considerar uno el principal), con los cuales deberá resolver las siguientes tareas:
a. mostrar un listado de los Pokémons ordenados por números usando el método de ordena-
miento por conteo;
b. realizar un listado ordenado por nombre utilizando el método de ordenamiento rápido;
c. mostrar toda la información de pokémon número 640;
d. listar todos los Pokémons que comienzan con la letra T;
e. determinar si existe el Pokémon Cobalion y mostrar toda su información;
f. realizar un listado de todos los Pokémon de tipo eléctrico y calcular cuántos son.
10. Un vendedor de “Fuko Pop”, tiene la lista de todos los funko que tiene disponibles en su tienda 
con la siguiente información: número, nombre, colección y precio; para lo cual nos solicita le 
desarrollemos un algoritmo que contemple los siguiente requerimientos:
a. realizar un listado ordenado por número;
b. realizar un listado de los funko pop de una colección;
c. determinar si tiene disponible el funko pop 130 de la colección de Star Wars y mostrar toda 
la información;
d. mostrar todos los funko pop disponible número 295;
e. listar todos los modelos de Darth Vader y Capitana Marvel;
f. determinar si existen funko pop de Red Skull, Thanos y Galactus, además mostrar la infor-
mación de estos;
g. calcular el costo de todos los modelos de Tony Stark e Iron Man disponibles;
h. calcular el promedio de costo de todos los funko pop y el costo total de las colecciones de 
Rocks y Harry Potter.
11. A partir de una lista con todos los caballeros Jedi y los lores Sith, de los que conocemos su nom-
bre y el de su maestro (considere solo uno), resuelva las siguientes actividades:
a. realizar un listado ordenado por nombre;
[64]
b. listar todos los Jedi ordenados por nombre;
c. listar todos los Sith ordenados por nombre;
d. mostrar los aprendices de Palpatine y de Obi-Wan kenobi, además contar cuantos apren-
dices tuvo cada uno;
e. determinar si Dath Malak está en la lista y mostrar su información;
f. mostrar la posición en la que se encuentra Yoda.
12. Dada una lista de dioses griegos a partir de la cual debemos desarrollar las funciones necesa-
rias para resolver los siguientes ítems:
a. emitir un listado de todos los dioses ordenados;
b. determinar si Atenea está en la lista;
c. indicar en qué posición se encuentra Deméter;
d. listar todos los dioses que comienzan con la letra H y además determinar cuántos son;
e. agregar al dios Helios y volver a listar los dioses ordenados alfabéticamente.
13. Se dispone de una lista de películas con la siguiente información: título, año de estreno, re-
caudación y valoración del público (de 1 a 5), los cuales debemos procesar contemplando las 
siguiente tareas:
a. realizar un listado ordenado por título, año de lanzamiento y por recaudación este ultimo 
de manera descendente;
b. mostrar toda la información de la película que mas recaudo;
c. listar todas las películas que tenga valoración 5;
d. determinar si la película “Avengers: Infinity War” está en la lista y mostrar 
toda su información;
e. indicar en qué posición se encuentra la película “Star Wars: The Return of Jedi”;
f. calcular el total recaudado por las películas que en su título incluyen la palabra “Avengers”;
g. mostrar todas las películas que se estrenaron en el año 2017;
h. listar todas las películas que comienzan con la palabra “Iron”.
14. La empresa Netflix nos pone a nuestra disposición los datos de todas las series cargadas en esta 
plataforma con los siguientes datos: nombre, cantidad de temporadas y cantidad de capítulos 
[65]
totales de la serie. Los cuales debemos procesar desarrollando las funciones necesarias para 
dar solución a las siguientes ítems:
a. listar las series ordenadas a cuerdo a los siguientes criterios: por nombre, por cantidad de 
temporadas, por cantidad de capítulos;
b. mostrar toda la información de la serie “Los 100“;
c. determinar cuál es la serie con mayor cantidad de temporadas y mayor cantidad de capítulos;
d. calcular cuantas series dispone la plataforma y el promedio de temporadas;
e. determinar el promedio de capítulos por temporada de la serie “Star Wars: Rebels”;
f. listar el TOP 5 de series con mayor cantidad de capítulos y el top 10 de las series con mayor 
cantidad de temporadas;
g. mostrar todas las series con tres o menos temporadas.
15. Se cuenta con una lista de canciones, de cada una de estas conocemos su nombre, nombre de la 
bandas o artista, y el año de lanzamiento del álbum; desarrollar las funciones necesarias para 
dar solución a las siguientes tareas:
a. realizar un listado ordenado por canción, por banda o artista y por año de lanzamiento, 
utilizando el método que sea más optimo para cada tipo de dato;
b. determinar si en la lista existe alguna canción de Audioslavey Rolling Stone;
c. mostrar todas las canciones de Nirvana;
d. agregar una nueva canción a la lista, y volver a realizar un listado ordenado por nombre 
de canción;
e. determinar cuantas canciones de los Red Hot Chili Peppers hay en la lista;
f. mostrar toda la información de las canciones “Fake tales of San Francisco” y 
“Black hole sun”.
16. Dada una lista de las naves (y vehículos) de Star Wars –consideraremos a todos como naves– de 
las que conocemos su nombre, largo, tripulación y cantidad de pasajeros, desarrollar los algo-
ritmos necesarios para resolver las actividades detalladas a continuación:
a. realizar un listado ordenado por nombre de las naves de manera ascendente y por largo de 
las mismas de manera descendente;
b. mostrar toda la información del “Halcón Milenario” y la “Estrella de la Muerte”;
c. determinar cuáles son las cinco naves con mayor cantidad de pasajeros;
[66]
d. indicar cuál es la nave que requiere mayor cantidad de tripulación;
e. mostrar todas las naves que comienzan con AT;
f. listar todas las naves que pueden llevar seis o más pasajeros;
g. mostrar toda la información de la nave más pequeña y la más grande.