Introducción al Práctico - Estructura de Datos y Algoritmos 2

Sobre este repositorio

Este repositorio es el punto de partida del práctico de Estructura de Datos y Algoritmos 2 de la Universidad ORT Uruguay.

Aquí van a encontrar:

• Instrucciones para configurar su ambiente de trabajo
• Ejemplos de programas en C++ y Java
• Casos de prueba para verificar que todo funciona correctamente

El objetivo es que al terminar esta guía puedan compilar un programa, ejecutarlo con datos de entrada, y verificar que la salida es correcta. Esta es la mecánica que van a usar durante todo el curso: en los prácticos, en el obligatorio y en los parciales.

---

Elegir un lenguaje

Lo primero es elegir con qué lenguaje van a trabajar: C++ o Java.

• C++ (estándar C++11) es el lenguaje recomendado. Los ejemplos de clase, las explicaciones y el material de apoyo están en C++.
• Java (JDK 8) es una alternativa válida. Tanto el obligatorio como los parciales se pueden resolver en Java sin ninguna restricción.

Una vez elegido, todo lo que necesitan es poder compilar y ejecutar programas en ese lenguaje desde una terminal.

---

Configurar el ambiente de trabajo

Las instrucciones dependen de su sistema operativo:

• Windows: Guía de instalación con WSL
• Mac: Guía de instalación para Mac
• Linux: Guía de instalación para Linux

Una vez configurado el ambiente, los comandos para compilar, ejecutar y correr pruebas son los mismos en todos los sistemas operativos (ya que en Windows también van a usar una terminal Linux a través de WSL).

---

Compilar

C++

g++ -std=c++11 -o ejemplo ejemplo.cpp

Donde:

• g++ es el compilador de C++
• -std=c++11 indica que usamos el estándar C++11 (esto es obligatorio en el curso)
• -o ejemplo define el nombre del archivo ejecutable de salida
• ejemplo.cpp es el archivo de código fuente a compilar

Java

javac Ejemplo.java

Donde:

• javac es el compilador de Java
• Ejemplo.java es el archivo de código fuente a compilar

Esto genera un archivo Ejemplo.class que luego se ejecuta con el comando java.

---

Ejecutar

Nuestros programas leen datos de la entrada estándar (cin en C++, Scanner en Java) y escriben resultados a la salida estándar (cout en C++, System.out.println en Java).

En lugar de tipear los datos a mano, usamos redirección para que el programa lea desde un archivo.

La redirección usa dos operadores:

• < (redirección de entrada): el programa lee del archivo en vez del teclado
• > (redirección de salida): el programa escribe a un archivo en vez de la pantalla

C++

# Ver la salida en pantalla
./ejemplo < casos/1000.in.txt

# Guardar la salida en un archivo
./ejemplo < casos/1000.in.txt > casos/1000.own.txt

./ejemplo ejecuta el programa compilado. El ./ indica que el archivo está en la carpeta actual.

Java

# Ver la salida en pantalla
java Ejemplo < casos/1000.in.txt

# Guardar la salida en un archivo
java Ejemplo < casos/1000.in.txt > casos/1000.own.txt

java Ejemplo ejecuta la clase Ejemplo compilada previamente con javac.

---

Correr pruebas

Esta es la mecánica central del curso. Así es como se corrigen los prácticos y el obligatorio:

1. Se ejecuta el programa con un archivo de entrada (.in.txt)
2. Se guarda la salida generada (.own.txt)
3. Se compara la salida generada contra la salida esperada (.out.txt)

Si los archivos son iguales, el programa es correcto para ese caso de prueba.

Comparar archivos con diff

Recomendamos usar el comando diff para comparar archivos. Pueden usar cualquier otra herramienta que prefieran, pero diff viene instalado en todos los sistemas y es el más práctico.

diff --strip-trailing-cr casos/1000.own.txt casos/1000.out.txt

• Si diff no muestra nada: los archivos son iguales, la solución es correcta para ese caso.
• Si diff muestra líneas: hay diferencias entre la salida generada y la esperada.

La opción --strip-trailing-cr evita falsos positivos por diferencias de fin de línea entre Windows y Linux.

Ejemplo completo paso a paso (C++)

# 1. Compilar
g++ -std=c++11 -o ejemplo ejemplo.cpp

# 2. Ejecutar con un caso de prueba y guardar la salida
./ejemplo < casos/1000.in.txt > casos/1000.own.txt

# 3. Comparar con la salida esperada
diff --strip-trailing-cr casos/1000.own.txt casos/1000.out.txt

Ejemplo completo paso a paso (Java)

# 1. Compilar
javac Ejemplo.java

# 2. Ejecutar con un caso de prueba y guardar la salida
java Ejemplo < casos/1000.in.txt > casos/1000.own.txt

# 3. Comparar con la salida esperada
diff --strip-trailing-cr casos/1000.own.txt casos/1000.out.txt

Correr todos los casos de prueba de una vez

for input in $(printf '%s\n' casos/*.in.txt | sort -t/ -k2 -n); do
    expected="${input%.in.txt}.out.txt"
    ./ejemplo < "$input" > /tmp/salida.txt
    if diff --strip-trailing-cr /tmp/salida.txt "$expected" > /dev/null 2>&1; then
        echo "OK: $input"
    else
        echo "FALLO: $input"
    fi
done

Tip: Cambiar ./ejemplo por java Ejemplo si usan Java, o por el nombre de otro ejecutable si quieren probar otro algoritmo (ej: ./mergesort).

---

Archivos en este repositorio

Archivo	Descripción
ejemplo.cpp	Ordenamiento burbuja en C++
ejemplo2.cpp	Merge sort en C++
Ejemplo.java	Ordenamiento burbuja en Java
casos/*.in.txt	Archivos de entrada (casos de prueba)
casos/*.out.txt	Archivos de salida esperada

---

Siguiente paso: medir tiempos de ejecución

Una vez que logren compilar, ejecutar y comparar correctamente, el siguiente paso es medir cuánto tarda cada algoritmo según el tamaño de la entrada. Esto les va a permitir ver empíricamente la diferencia entre un algoritmo O(N²) (burbuja) y uno O(N log N) (merge sort).

Comando time

El comando time mide cuánto tarda en ejecutarse un programa:

time ./ejemplo < casos/1000.in.txt > /dev/null

La salida muestra tres valores:

• real — tiempo total transcurrido (este es el que nos interesa)
• user — tiempo de CPU en modo usuario
• sys — tiempo de CPU en modo sistema

El > /dev/null descarta la salida del programa porque solo nos interesa medir el tiempo, no ver el resultado.

Comparar los dos algoritmos

Compilar ambos programas:

g++ -std=c++11 -o burbuja ejemplo.cpp
g++ -std=c++11 -o mergesort ejemplo2.cpp

Medir el tiempo de cada uno con un caso de prueba:

time ./burbuja < casos/1000.in.txt > /dev/null
time ./mergesort < casos/1000.in.txt > /dev/null

Repetir cambiando el archivo de entrada (5000.in.txt, 10000.in.txt, etc.) y anotar el tiempo de cada ejecución.

Si eligieron Java, el proceso es el mismo:

javac Ejemplo.java
time java Ejemplo < casos/1000.in.txt > /dev/null

Graficar los resultados

Anotar los tiempos en una tabla como esta y graficarla (pueden usar Excel, Google Sheets, o la herramienta que prefieran):

N	Burbuja (seg)	Merge Sort (seg)
1000	...	...
5000	...	...
10000	...	...
20000	...	...
50000	...	...
100000	...	...
120000	...	...

Van a notar que burbuja crece mucho más rápido que merge sort a medida que aumenta N. Esa diferencia es la que vamos a estudiar durante el curso.

Nota: Para valores de N pequeños (ej: 1000) los tiempos pueden ser muy bajos y variar bastante entre ejecuciones. Esto es normal — con tiempos tan chicos, factores externos (otros procesos del sistema, cache del procesador, etc.) generan mucha varianza. La diferencia entre algoritmos se hace evidente con entradas más grandes.