Práctica #4: Algoritmos de ordenamiento

Objetivo

Durante esta actividad, los alumnos serán capaces de:

Codificar varios algoritmos de ordenamiento en C++. Medir y contrastar sus respectivos desempeños bajo diferentes condiciones iniciales.

Descripción

Esta actividad se debe realizar en los equipos ya conformados.

Traduce a lenguaje C++ los siguientes algoritmos de ordenamiento a partir del pseudocódigo presentado en el capítulo 6 del libro de [STEPHENS]:

Insertionsort (p. 132)
Selectionsort (p. 134)
Bubblesort (p. 135)
Quicksort (pp. 150-151)
Mergesort (pp. 153-154)
Countingsort (p. 156)

Escribe un reporte con los resultados de correr cada algoritmo como se explica a continuación.

Consideraciones generales

Los ordenamientos se deben efectuar sobre vectores de valores enteros (std::vector<int>). Dichos valores enteros pueden estar entre 0 y 999, inclusive.
Despues de invocar a cada algoritmo de ordenamiento es indispensable verificar que el vector haya quedado correctamente ordenado. Esto se debe realizar a través de la función std::is_sorted.
Se deben probar los algoritmos con vectores de los siguientes tamaños:
- 100 (cien) elementos
- 1 000 (mil) elementos
- 10 000 (diez mil) elementos
- 100 000 (cien mil) elementos
- 1 000 000 (un millón) de elementos
- 10 000 000 (diez millones) de elementos
La ejecución de cada algoritmo usando un vector de cada tamaño se debe cronometrar bajo tres condiciones iniciales:
- El vector original contiene elementos calculados pseudo-aleatoriamente y por lo tanto está, para fines prácticos, en total desorden.
- Todos los elementos del vector original se encuentran en orden ascendente. En otras palabras, el vector se encuentra inicialmente ordenado.
- Todos los elementos del vector original se encuentran en orden descendente. En otras palabras, el vector se encuentra inicialmente ordenado pero de manera inversa.
Asegúrate de correr todo tu código en la misma computadora (o ambiente de AWS Cloud9) para que las mediciones de tiempo sean significativas.
IMPORTANTE: Algunos algoritmos, especialmente aquellos con una complejidad $\textrm{O}(N^2)$, pueden ser extremadamente lentos para valores grandes de $N$. Si el programa tarda más de tres minutos en ejecutarse para una cierta combinación de algoritmo/tamaño/condición-vector-inicial es válido detenerlo y simplemente reportar ese caso como “demasiado lento”.
Además de los seis algoritmos solicitados, debes correr y cronometrar la función predefinida std::sort utilizando vectores de los mismos tamaños y con las mismas condiciones iniciales a las ya descritas arriba.

Código de apoyo

Inicializar los valores de un vector

El siguiente código inicializa todos los elementos del vector values con enteros aleatorios entre 0 y max_value - 1, inclusive.

#include <cstdlib>

void fill_random(std::vector<int>& values, int max_value)
{
    std::srand(0);
    for (int i = 0; i < values.size(); ++i) {
        values.at(i) = std::rand() % max_value;
    }
}

El siguiente código inicializa todos los elementos del vector values con enteros que van de forma progresivamente ascendente desde 0 y hasta algún valor menor a max_value.

void fill_incremental(std::vector<int>& values, int max_value)
{
    double section = max_value / static_cast<double>(values.size());
    double current = 0.0;
    for (int i = 0; i < values.size(); ++i) {
        values.at(i) = static_cast<int>(current);
        current += section;
    }
}

El siguiente código inicializa todos los elementos del vector values con enteros que van de forma progresivamente descendente desde algún valor menor a max_value y hasta llegar a 0.

void fill_decremental(std::vector<int>& values, int max_value)
{
    double section = max_value / static_cast<double>(values.size());
    double current = 0.0;
    for (int i = values.size() - 1; i >= 0; --i) {
        values.at(i) = static_cast<int>(current);
        current += section;
    }
}

Cronometrar tiempos de ejecución

El siguiente fragmento permite cronometrar el tiempo de ejecución de una porción de nuestro programa. Lo que se quiera medir se debe sustituir en lugar del comentario correspondiente. Al final la variable total_time contiene un número real con la cantidad de segundos que tardó en correr dicho código.

#include <chrono>

    .
    .
    .

    auto start = std::chrono::high_resolution_clock::now();
    // Place here the code to time
    auto stop = std::chrono::high_resolution_clock::now();
    auto duration =
        std::chrono::duration_cast<std::chrono::microseconds>(
            stop - start);
    double total_time = duration.count() / 1000000.0;

¿Qué se debe entregar?

Usando el procesador de palabras de tu preferencia, escribe un reporte que contenga lo siguiente:

Portada: Incluye el título de la práctica, así como el número de equipo, las matrículas, nombres y correos electrónicos de los autores del reporte.
Introducción: Establece el propósito y la metodología de esta práctica. Debe tener una extension de al menos 100 palabras.
Recursos computacionales: Incluye la información sobre el hardware y software utilizado para desarrollar la práctica.

Si estás utilizando AWS Cloud9 con Ubuntu, puedes determinar los elementos de hardware y software corriendo los siguientes comando desde la terminal:
- Modelo de CPU:
```
grep "model name" /proc/cpuinfo
```
- Número de núcleos en el CPU:
```
grep "cpu cores" /proc/cpuinfo
```
- Total de memoria RAM (el número en el renglón Mem:, columna total):
```
free -mh
```
- Total de memoria de almacenamiento secundario (el número en la columna Size):
```
df -h | egrep '/$|Size'
```
- Versión del sistema operativo:
```
lsb_release -ds
```
- Versión del compilador de C++:
```
g++ --version
```

Resultados: Por cada algoritmo (incluyendo también la función std::sort), indica su complejidad e incluye una tabla llenada con los respectivos tiempos de ejecución. Algo así:

Nombre del algoritmo. Complejidad: O(N²)

Número de elementos	Condición inicial del vector
Número de elementos	Desordenado	Ordenado ascendente	Ordenado descendente
100
1 000
10 000
100 000
1 000 000
10 000 000

Conclusiones: Resume lo que los autores aprendieron durante el proceso de elaboración de la práctica. Debe tener una extension de al menos 100 palabras.
Agradecimientos: (Opcional) Incluye el nombre de cualquier persona que haya contribuido o ayudado a desarrollar la práctica.
Referencias: Incluye los datos de cualquier documento consultado (electrónico o en papel) en formato APA.
Apéndice: Incluye el listado de todos los archivos fuentes utilizados para elaborar la práctica (archivos *.cpp, *.h, Makefile, etc.).

Descarga el reporte como documento PDF con el siguiente nombre: reporte_ordenamientos.pdf.

Upload Instructions

To deliver the reporte_ordenamientos.pdf file, please provide the following information:

Request PIN

Solo es necesario que lo entregue un miembro del equipo.

La fecha límite es el viernes 15 de octubre.