UNIVERSIDAD NACIONAL DE ENTRE RÍOS
Facultad de Ingeniería
ALGORITMOS Y ESTRUCTURAS DE DATOS
Guía de Práctica Nº 4
Búsqueda y Ordenamiento
Versión 01
Objetivos
● Implementar algoritmos de búsqueda y ordenamiento.
● Validar algoritmos de búsqueda y ordenamiento mediante pruebas unitarias.
● Aplicar algoritmos de ordenamiento y estudiar sus órdenes de complejidad.
Material de apoyo
● Recurso de visualización: enlace a “Comparison Sorting Algorithms”
Ejercicios
Ejercicios de búsqueda
1. Búsqueda lineal en lista desordenada
Implementar el algoritmo de búsqueda lineal en sus dos versiones: sin retornar la posición
del elemento encontrado y retornando la posición del elemento encontrado.
2. Búsqueda lineal en lista ordenada
Extender la implementación de la búsqueda lineal para considerar el caso de listas
ordenadas de menor a mayor. En este caso, el algoritmo debe detener la búsqueda si el
elemento analizado es mayor al elemento buscado.
3. Búsqueda binaria
Implementar el algoritmo de búsqueda binaria en forma iterativa. En este caso, el algoritmo
debe retornar, además del valor de verdad (booleano), la posición del elemento buscado y
el número de iteraciones realizadas.
Se sugiere retornar el resultado en una tupla del tipo “(encontrado, posicion, iteraciones)”.
Ejercicios de ordenamiento básicos
4. Ordenamientos burbuja, selección e inserción
Crear un módulo donde implemente los algoritmos de ordenamiento por burbuja, selección
e inserción.
Luego, dada una lista de N elementos desordenados, escribir un programa que grafique el
tiempo requerido para cada ordenamiento para valores crecientes de N.
Ejercicios de ordenamiento avanzados no recursivos
5. Ordenamiento de Shell
Implementar el algoritmo de ordenamiento de Shell. Luego, escribir un programa que
verifique el funcionamiento del algoritmo.
Añadir al algoritmo la posibilidad de modificar la expresión para el salto o brecha con la cual
se generan las sublistas a ordenar según la tabla siguiente.
Modo Salto
1 2k - 1 (k: log2(n), …,3, 2, 1)
2 n/2k (n: cantidad de elementos, k: 1, 2, 3, ...)
3 Los números primos menores a mil
Se debe programar la prueba unitaria del algoritmo.
Ejercicios de ordenamiento avanzados recursivos
6. Mezcla binaria (Merge Sort)
Implementa el algoritmo de mezcla binaria (merge sort). Luego, escribir un programa que
verifique (test) que el algoritmo funciona correctamente.
Sugerencia: Antes de implementar el algoritmo de mezcla binaria, es conveniente
implementar un algoritmo auxiliar “mezclar” capaz de generar una lista ordenada a partir de
dos listas previamente ordenadas.
Se debe programar la prueba unitaria del algoritmo.
7. Ordenamiento rápido (Quick Sort)
Implementa el algoritmo de ordenamiento rápido (quick sort). Luego, escribir un programa
que verifique (test) que el algoritmo funciona correctamente.
Sugerencia: Antes de implementar el algoritmo de ordenamiento rápido, es conveniente
implementar un algoritmo auxiliar “particionar” capaz de recibir un elemento pivote y
reposicionar a un lado y otro de dicho elemento los restantes elementos de la lista.
Se debe programar la prueba unitaria del algoritmo.
Aplicaciones
1. Ordenar registros en un archivo
Considerar el archivo CSV con datos de “Visitas de residentes y no residentes por región”
([Link]). Este archivo cuenta con 2880 registros
que informan para cada provincia Argentina la cantidad de visitantes en cada región o
provincia. A su vez, para cada región o provincia los datos se subdividen en tres grupos:
residentes, no residentes y total.
Se solicita escribir un programa que realice dos tareas:
a) Preprocesar los datos originales para cada región o provincia generando un nuevo
archivo de datos. En este nuevo archivo deben figurar cada región y/o provincia
junto a dos nuevas columnas donde figuran los porcentajes de residentes y no
residentes. Ejemplo, si los datos fueran:
indice_tiempo,region_de_destino,origen_visitantes,visitas,observaciones
2008-01,buenos aires,residentes,885,""
2008-01,buenos aires,no residentes,0,""
2008-01,buenos aires,total,885,""
2008-01,cordoba,residentes,717,""
2008-01,cordoba,no residentes,145,""
2008-01,cordoba,total,862,""
2008-01,cuyo,residentes,4965,""
2008-01,cuyo,no residentes,179,""
2008-01,cuyo,total,5144,""
Entonces, los datos preprocesados deberían ser similares a:
indice_tiempo,region_de_destino,visitas_porcentaje_residentes,visitas_porcentaje
_no_residentes,observaciones
2008-01,buenos aires,1,0,""
2008-01,cordoba,"0,831786542923434","0,168213457076566",""
2008-01,cuyo,"0,965202177293935","0,034797822706065",""
b) Una vez preprocesados los datos, utilizar un algoritmo de ordenamiento avanzado
(shell, mergesort o quicksort) para ordenar los datos por un criterio dado por el
usuario que puede ser por: porcentaje de visitas de residentes, visitas de no
residentes, por provincia o por período (año-mes).
Una vez ordenados los registros, generar un archivo que los contenga. El nombre
del archivo debe indicar el criterio de ordenamiento utilizado.
2. Ordenar una lista simplemente enlazada
A partir del TAD Lista simplemente enlazada desarrollado previamente, implementar el
algoritmo de ordenamiento por inserción como una operación adicional dentro de la
estructura.
3. Ordenar una cola circular
A partir del TAD Cola circular de la Guía Nº 3, implementar un algoritmo de ordenamiento
como una operación adicional dentro de la estructura.
4. Comparación de algoritmos
Escribir un programa que permita comparar el desempeño de diferentes algoritmos de
ordenamiento. En este caso, se busca comparar el ordenamiento por inserción con los
algoritmos de ordenamiento shell, merge y quick. La salida del programa debe ser para tres
situaciones diferentes: ordenar una lista con los elementos dispuestos en orden inverso,
ordenar una lista ordenada y ordenar una lista con un ordenamiento aleatorio.
La salida del programa está compuesta por dos archivos. El primer archivo es un informe
con una tabla que indica, para cada algoritmo evaluado, la cantidad de comparaciones
realizadas y la cantidad de intercambios. El segundo archivo es una imagen con tres
gráficas log-log, una para cada tipo de entrada (lista invertida, lista ordenada y lista
aleatoria). En cada gráfica se deben ver los tiempos que demora en correr cada algoritmo
para cada valor de N.
