Análisis comparativo de algoritmos de ordenamiento

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 y cómo las diferentes formas de resolver un mismo problema pueden afectar los tiempos de ejecución.

Quiero aclarar que este es solo un análisis académico muy simple que quise documentar, y que tal vez sirva a futuro para otros estudiantes de ciencias de la computación.

Comencé desarrollando un pequeño script en Java que genera números aleatorios de cinco dígitos y los almacena en un archivo de texto, para poder analizar el mismo conjunto de datos entre diferentes algoritmos. El script lo puedes encontrar en este repositorio y ejecutar de la siguiente forma:

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

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

Lo anterior genera el archivo numbers/numbers.txt con n números aleatorios definidos dentro del script. En mis experimentos llegué a generar un archivo de 1.000.000.000 de datos (cerca de 5 GB), por eso no lo adjunté en el repositorio.

Algoritmos evaluados

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

Para esta tarea seleccioné C y los scripts se encuentran en algorithms/c/sortAlgorithms.

Automatización de pruebas

Dado que para hacer un buen análisis se deben correr muchas pruebas, creé un par de scripts para automatizarlas:

# Script base para ejecutar cualquier algoritmo y generar logs de tiempos
> algorithms/c/benchmark.c

# Correr prueba
# arg1, arg2 => nombre del algoritmo y cantidad de elementos
$ gcc benchmark.c -o benchmark.out && ./benchmark.out arg1 arg2

# Script para correr múltiples pruebas
> algorithms/c/runTest.c

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

Con esto ya estaba todo listo. Solo faltaba dejar corriendo runTest.c en una máquina. Aunque era un ejercicio académico sin gran rigor científico, procuré usar un pequeño ambiente controlado para evitar ruido por otros procesos.

Para eso creé dos droplets en Digital Ocean:

Digital Ocean droplets — Los dos droplets de DigitalOcean usados como máquinas de benchmark — M1 (1 núcleo, 1 GB RAM) y M2 (2 núcleos, 2 GB RAM).

El segundo servidor tenía el doble de recursos, así que en teoría debía rendir mejor.

También configuré Java y C en ambos servidores con este script de aprovisionamiento: 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

Resultados

En cada máquina se corrieron pruebas con el mismo archivo de números aleatorios, aumentando el tamaño en diferentes intervalos (10, 100, 1.000, 10.000, etc.). Los resultados detallados están en results/analysis.ods.

Como pausa útil, este fue el truco para dejar el proceso en background sin depender de la sesión:

$ gcc runTest.c -o runTest.out && ./runTest.out
# Ctrl + z
disown -h %1
bg 1

Después de varios días, los experimentos apenas iban por 1.600.000 de datos en los algoritmos O(n^2), así que detuve la ejecución en ambos servidores y empecé el análisis.

M1 = Máquina 1 (1 núcleo, 1GB RAM)
M2 = Máquina 2 (2 núcleos, 2GB RAM)

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

Bubble Sort M1 — Bubble Sort en Máquina 1 — el tiempo de ejecución crece rápidamente al superar el millón de elementos.

Bubble Sort M2 — Bubble Sort en Máquina 2 — la frecuencia por núcleo más baja (1,8 GHz vs 2,4 GHz) resulta en peor rendimiento a pesar de tener más RAM.

Bubble Sort M1 vs M2 — el crecimiento cuadrático O(n²) es claramente visible; M1 supera a M2 gracias a su mayor frecuencia de CPU.

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

Counting Sort M1 — Counting Sort en Máquina 1 — curva casi plana O(n+k), terminando en milisegundos incluso con 1,6 M de elementos.

Counting Sort M2 — Counting Sort en Máquina 2 — crecimiento igualmente plano; la ventaja O(n+k) se mantiene sin importar el nivel de hardware.

Counting Sort M1 vs M2 — ambas máquinas muestran tiempos casi idénticos por debajo del milisegundo, confirmando la cota O(n+k).

Montones (Heapsort): O(n log n)

Heap Sort M1 — Heap Sort en Máquina 1 — crecimiento O(n log n), manteniéndose bien por debajo de 2 segundos con 1,6 M de elementos.

Heap Sort M2 — Heap Sort en Máquina 2 — rendimiento O(n log n) consistente; ligeramente más lento que M1 por la menor frecuencia de reloj.

Heap Sort M1 vs M2 — las curvas superpuestas confirman que en tareas de un solo hilo la frecuencia de CPU es la variable decisiva.

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

Insertion Sort M1 — Insertion Sort en Máquina 1 — curva O(n²) más pronunciada que Selection Sort, pero muy por debajo de Bubble Sort.

Insertion Sort M2 — Insertion Sort en Máquina 2 — la menor velocidad por núcleo hace más evidente la penalización O(n²) con entradas grandes.

Insertion Sort M1 vs M2 — M1 lidera en todo momento, reforzando que la frecuencia de reloj domina en algoritmos secuenciales.

Mezcla (Merge Sort): O(n log n)

Merge Sort M1 — Merge Sort en Máquina 1 — curva O(n log n) estable, competitiva con Heap Sort y Quicksort.

Merge Sort M2 — Merge Sort en Máquina 2 — rendimiento consistente; la RAM adicional puede ayudar con las asignaciones de memoria que requiere este algoritmo.

Merge Sort M1 vs M2 — los resultados son cercanos, mostrando que el uso de memoria del algoritmo puede compensar parcialmente la diferencia de frecuencia de CPU.

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

Quick Sort M1 — Quicksort en Máquina 1 — segundo más rápido en general, manteniéndose consistentemente por debajo de 0,5 segundos hasta 1,6 M de elementos.

Quick Sort M2 — Quicksort en Máquina 2 — ligeramente más lento que M1, pero sigue dentro del grupo rápido O(n log n).

Quick Sort M1 vs M2 — Quicksort M1 vs M2 — ambas máquinas se comportan de forma similar, confirmando la eficiencia práctica de Quicksort con datos aleatorios.

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

Selection Sort M1 — Selection Sort en Máquina 1 — crecimiento O(n²), más rápido que Bubble Sort pero muy por detrás del grupo O(n log n).

Selection Sort M2 — Selection Sort en Máquina 2 — escalado cuadrático similar; menos intercambios que Bubble Sort pero la misma cota asintótica.

Selection Sort M1 vs M2 — M1 consistentemente más rápido; la ventaja de frecuencia de reloj es el factor decisivo en trabajo O(n²) de un solo hilo.

Gráfica comparativa de todos los algoritmos

All algorithms M1 — Los siete algoritmos en Máquina 1 — el grupo O(n²) domina la escala; el grupo rápido se agrupa cerca del eje x.

All algorithms M2 — Los siete algoritmos en Máquina 2 — el mismo patrón que M1; la curva de Bubble Sort eclipsa a todo lo demás.

All algorithms M1 vs M2 — Todos los algoritmos en ambas máquinas — la mayor frecuencia de reloj de M1 la mantiene más rápida a pesar del mayor número de núcleos y RAM de M2.

En esa comparativa, los cuatro algoritmos rápidos (quickSort, mergeSort, heapSort, countingSort) se solapan por escala. El perdedor claro fue bubbleSort, seguido por insertionSort y selectionSort.

Esto refleja un reto clásico en computación: para un mismo problema hay muchas soluciones, pero cada una funciona mejor bajo condiciones concretas.

Tiempos de respuesta (últimos 7 puntos)

Máquina 1 (M1)

Size	BubbleSort	CountingSort	HeapSort	InsertionSort	MergeSort	QuickSort	SelectionSort
1,000,000	5584.254499	0.016609	0.747395	2592.498977	0.704281	0.291499	1935.487457
1,100,000	6637.222252	0.019187	0.925764	3171.445715	0.653455	0.471039	2269.966268
1,200,000	8045.953682	0.023652	0.913537	3722.638885	0.513099	0.239454	2783.279525
1,300,000	10169.383378	0.045208	0.713308	4824.250285	0.575149	0.261289	3514.914589
1,400,000	12053.658798	0.034613	1.489084	5658.739951	0.676112	0.279478	4066.729922
1,500,000	13798.854123	0.027525	1.094257	6555.365499	0.743651	0.315602	4839.340426
1,600,000	15205.680544	0.028478	0.996648	6794.512119	0.725347	0.325990	5056.213092

Máquina 2 (M2)

Size	BubbleSort	CountingSort	HeapSort	InsertionSort	MergeSort	QuickSort	SelectionSort
1,000,000	7069.317038	0.032415	0.752168	3178.694237	0.558200	0.315689	2454.531144
1,100,000	8458.150387	0.024157	0.842038	3666.359787	0.557481	0.284579	2804.449695
1,200,000	9495.898708	0.026530	0.882819	4084.581924	0.616636	0.358502	3081.748250
1,300,000	10626.023771	0.027309	0.913814	4933.201883	0.753890	0.401456	3912.714921
1,400,000	13439.250082	0.030009	1.061221	5790.797804	0.633180	0.442449	4066.729922
1,500,000	15102.736592	0.031826	1.064744	6565.630358	0.788551	0.400238	5114.565289
1,600,000	16483.694808	0.039298	1.365129	7311.347004	0.760618	0.449284	5676.768371