AnalysisOfSortAlgorithms

1. Definición y procedimiento

Como parte de un ejercicio típico de algoritmia en la universidad, hice un pequeño análisis comparativo de los algoritmos de ordenamiento más populares, buscando estudiar la complejidad de cada uno de ellos y como las diferentes formas de resolver un mismo problema pueden afectar los tiempos de ejecución. Quiero aclarar que este es solo un análisis academíco muy simple que quiero documentar, el cual tal vez sirva a futuro para otros estudiantes de ciencias de la computación.

Comence desarrollando un pequeño script en Java que permite generar numeros aleatorios de cinco digitos y almacenarlos en un archivo de texto, esto con el fin de poder analizar el mismo conjunto de datos entre los diferentes algoritmos; el script correspondiente lo pueden hallar en este respositorio y ejecutar de la siguiente forma:

# Ruta del archivo
> algorithms/java/RandomNumbers.java

# Ejecutar script en Java
$ javac RandomNumbers.java && java RandomNumbers

Lo anterior generará el archivo de texto numbers/numbers.txt con n numeros aleatorios que se especifican dentro del script de Java. Dentro de mis experimentos el archivo que generé fue de 1.000.000.000 millones de datos, el cual no adjunto en el repositorio debido a que termino pesando cerca de 5 GB.

En un paso siguiente procedí a implementar los algoritmos de ordenamiento:

• Burbuja (Bubble Sort): Complejidad O(n^2)
• Conteo (Counting Sort): Complejidad O(n+k)
• Montones (Heapsort): Complejidad O(n log n )
• Inserción (Insertion Sort): Complejidad O(n^2)
• Mezclas (Merge Sort): Complejidad O(n log n).
• Rápido (Quicksort): Complejidad O(n log n).
• Selección (Selection Sort): Complejidad O(n^2).

Para esta tarea seleccione el lenguaje C y los scripts obtenidos los pueden encontrar en algorithms/c/sortAlgorithms

Por último, dado que para hacer un buen análisis se deben correr muchas pruebas, cree un par de scripts que me permitieran automatizarlas de forma tal que se pudieran correr de forma continua sin intervención, estos son:

# Archivo desde el cual se puede correr cualquiera de los algoritmos implementados y permite crear arreglos de forma dinámica con base a la cantidad de elementos a ordenar. Este script además genera dos archivos de salida en el folder "results" con logs sobre los tiempos de ejecución del algoritmo
> algorithms/c/benchmark.c

# Correr prueba
# arg1, arg2 => Son el tipo (nombre) del algoritmo y la cantidad de elementos a probar
$ gcc benchmark.c -o benchmark.out && ./benchmark.out arg1 arg2

---

# El script runtTest.c permite correr multiples pruebas para los diferentes algoritimos y diferentes cantidades de datos haciendo uso del script anterior
> algorithms/c/runTest.c

# Correr pruebas
$ gcc runTest.c -o runTest.out && ./runTest.out

En este punto ya tenemos todo listo para hacer las pruebas, solo necesitamos poner a correr nuestro archivo runtTest.c en alguna maquina, y dado que esto es un simple ejercicio académico no requiere de mucho rigor científico, pero procure crear un pequeño ambiente controlado en un par de servidores donde no estuvieran ejecutandose en paralelo otras tareas, dado que los tiempos de ejecución de cada prueba puede verse afectado al estar compartiendo recursos con otros procesos.

Dicho lo anterior cree dos droplets (término para llamar a servidores en la nube) en Digital Ocean, los cuales corresponden a:

Como se puede observar en la imagen anterior, el segundo servidor posee el doble de capacidades de procesamiento, con lo cual se espera obtener un mejor rendimiento en las pruebas.

Finalmente procedo a configurar el servidor asegurandome de tener los compiladores tanto de Java y C; pueden encontrar el archivo de aprovisionamiento que corri en cada uno de los servidores en ServerConfig/provision.sh.

# Base installation
sudo apt-get update -y
sudo apt-get upgrade -y
sudo apt-get install -y build-essential gcc python-dev python-pip python-setuptools

# Git
sudo apt-get install -y git

# Install Java
sudo apt-get install default-jre -y
sudo apt-get install default-jdk -y
sudo apt-get install openjdk-7-jre -y
sudo apt-get install openjdk-7-jdk -y

2. Resultados

En cada maquina se corrieron las pruebas con el mismo archivo de numeros aleatorios a ordenar, en intervalos inicialmente de 10 en 10, luego 100 en 100, luego 1.000, luego 10.000 etc, hasta 1.000.000.000 de datos; estos resultados se pueden visualizar en el archivo results/analysis.ods.

En este punto hago un parentesis para documentar el truco que utilice para poder correr los el archivo de pruebas en background y de esa forma no depender de una sesion activa en la terminal para correr las mismas:

# Correr pruebas
$ gcc runTest.c -o runTest.out && ./runTest.out

# Detenemos el proceso usando Ctrl + z
# Una vez hecho esto ejecutamos lo siguiente
disown -h %1
bg 1

# Lo anterior básicamente hace que el último proceso que se habia ejecutado corra en background, algo muy similar a lo que hace el &, solo que en este caso si cierro la sesion en la terminal no se detendra el programa.

Al cabo de 3 o 4 días de haber lanzado el archivo runTest.c, revise que los procesos y apenas iban en 1.600.000 de datos, me parecio que era suficiente para sacar conclusiones así que decidí parar el experimento en ambos servidores, y ahora procedo a mostrar los resultados obtenidos comparando los tiempos de respuesta de cada algoritmo en cada maquina:

M1 = Maquina 1 (1 nucleo, 1GB de RAM) M2 = Maquina 2 (2 nucleos, 2GB de RAM)

2.1. Burbuja (Bubble Sort): O(n^2)

2.2. Conteo (Counting Sort): O(n+k)

2.3. Montones (Heapsort): O(n log n)

2.4. Inserción (Insertion Sort): O(n^2)

2.5. Mezclas (Merge Sort): O(n log n)

2.6. Rápido (Quicksort): O(n log n)

2.7. Selección (Selection Sort): O(n^2)

Como se puede observar en cada imagen se muestra la gráfica de cada algoritmo, primero en la maquina 1, luego en la maquina 2 y por último una tercera gráfica comparando ambas, donde la curva azul representa la máquina 1 y la linea naranja la maquina 2; como resultado de la simple observación, se puede concluir que la maquina 1 fue superior a la maquina 2, al menos menos por un pequeño margen en algunos casos. Pero porque es esto posible? acaso la maquina 2 no tenia el doble de recuersos que la maquina 1? dejaré esta incognita para un poco más adelante, primero determinemos cual de los algoritmos, fue el ganador, cosa que de antemano deberíamos ya s