Asignatura Datos del alumno Fecha
Apellidos:
Algoritmia y Complejidad
Nombre:
Laboratorio #1: Algoritmos de ordenación
Preparación para el laboratorio
Antes de acudir al laboratorio deberás haber instalado en tu computador el IDE del
lenguaje de programación seleccionado:
ANACONDA o cualquier otro que soporte programar en Python.
Visual Studio Community o cualquier otro que soporte cómo mínimo el estándar
C++11 - ISO/IEC TR 19768:2007
También puede trabajar en línea creando una cuenta en [Link] u otro
servicio de programación en línea
Descripción del laboratorio
En el laboratorio vamos a realizar el análisis empírico de algunos algoritmos de
ordenación. Para medir el tiempo de ejecución y número de operaciones básicas de los
algoritmos tenemos que analizar el código y hacer los ajustes que correspondan.
Recibirás los siguientes archivos:
«[Link]», «[Link]» y «[Link]» con los datos de entrada
para cada caso de análisis. Para leer estos datos debe utilizar una función de lectura
de archivos en su programa.
Si trabaja con Python «[Link]» con la implementación parcial de las funciones.
Si trabaja con C++: «Solución.h» con la declaración de las funciones y «Solució[Link]» con
la implementación parcial de las funciones.
Entrega del laboratorio
Una vez acabado el trabajo, deberás adjuntar el código fuente con el nombre de
archivo «Solucion_SuNombre» y la extensión que corresponda al lenguaje de
programación utilizado. En el código fuente debe implementar completamente las
funciones
© Universidad Internacional de La Riojade ordenación y las demás que requiera el programa para su correcto
(UNIR)
funcionamiento. Las funciones escritas deben recibir el arreglo a ordenar como un
parámetro.
Nota: en C++ deben implementarse completamente las funciones de «Solution.h». Se
recomienda no modificar el prototipo de las funciones escritas en «Solución.h»
Adicional al código fuente, debe entregar un informe denominado «[Link]»,
donde de respuesta a las siguientes preguntas incluyendo las tablas de análisis
empírico y análisis matemático que se presentan a continuación:
1. ¿Funciona bien tu programa? ¿Qué fallos existen? ¿Cuál fue la mayor dificultad en el
desarrollo de las funciones?
Tema 5. Actividades
Asignatura Datos del alumno Fecha
Apellidos:
Algoritmia y Complejidad
Nombre:
2. Seleccione una de las funciones de algoritmos de ordenación y comente explicando la
funcionalidad desarrollada.
3. Rellena la siguiente tabla con los tiempos empíricos obtenidos de ejecutar los distintos
algoritmos con las entradas. Y estime empíricamente el número de operaciones básicas que
ejecuta cada algoritmo según el número de entradas que se analiza para cada caso (n=800,
n=8000 y n=80000)
ANÁLISIS EMPÍRICO
Tiempo de ejecución Número de operaciones
Algoritmo n (seg) básicas
Burbuja 800
Burbuja 8000
Burbuja 80000
Selección 800
Selección 8000
Selección 80000
Inserción 800
Inserción 8000
Inserción 80000
Mergesort 800
Mergesort 8000
Mergesort 80000
Quicksort 800
Quicksort 8000
Quicksort 80000
4. Investigue y/o realice los cálculos que le permitan diligenciar la siguiente tabla con las
fórmulas que estiman el número de intercambios y operaciones básicas de cada uno de
los tipos de algoritmos de ordenación. A partir de la fórmula de cada algoritmo haga el
cálculo del número de operaciones básicas según el número de entradas que se analiza
para cada caso (n=800, n=8000 y n=80000)
ANÁLISIS MATEMÁTICO
© Universidad Internacional de La Rioja (UNIR) Número estimado de operaciones
Fórmula cerrada básicas para n=800, n=8000 y
Algoritmo número medio de intercambios n=80000
Burbuja
Selección
Inserción
Mergesort
Quicksort
5. Analice las diferencias entre el número de operaciones básicas calculadas
empíricamente con la ejecución de los programas (valores experimentales) y los valores
Tema 5. Actividades
Asignatura Datos del alumno Fecha
Apellidos:
Algoritmia y Complejidad
Nombre:
teóricos calculados a partir de las fórmulas. Indique cuáles son esas diferencias y a qué
crees que se deben.
© Universidad Internacional de La Rioja (UNIR)
Tema 5. Actividades
