1 - Introducción a los algoritmos de ordenamiento

En esta primera lección definimos qué significa ordenar una colección de datos, por qué los algoritmos de ordenamiento son esenciales y cómo evaluaremos su eficiencia. Todos los ejemplos están pensados para compilar en C, con un estilo simple que facilita el depurado en cualquier IDE.

1.1 ¿Qué significa ordenar una colección?

Ordenar es reorganizar los elementos de una colección según un criterio definido, ya sea ascendente o descendente. El criterio puede basarse en números, texto o incluso combinaciones (por ejemplo, primero por apellido y luego por nombre).

En la práctica, ordenar implica:

• Elegir una clave de comparación consistente para todos los elementos.
• Aplicar el criterio de forma repetible, garantizando que para cualquier par de elementos podamos decidir si uno va antes que el otro.
• Mantener, cuando haga falta, la estabilidad: si dos elementos son equivalentes, el orden relativo inicial puede conservarse o no según el algoritmo.

1.2 Importancia del ordenamiento en la computación

El ordenamiento aparece en casi todos los sistemas: mejora la búsqueda, simplifica la generación de reportes y permite agrupar datos antes de otros procesos. Algunas razones clave:

• Búsquedas más rápidas: colecciones ordenadas habilitan búsqueda binaria y reducen la cantidad de comparaciones.
• Integración con otras etapas: muchos algoritmos de deduplicación, compresión o agregación asumen datos previamente ordenados.
• Claridad para el usuario: interfaces que muestran resultados ordenados (por fecha, nombre o puntaje) son más predecibles.

1.3 Comparación, intercambio (swap) y recorridos

Todos los algoritmos de este tutorial se basan en tres operaciones básicas:

• Comparar: decidir si un elemento debe ir antes o después de otro.
• Intercambiar (swap): mover dos elementos de posición cuando el orden esperado no se cumple.
• Recorrer: iterar la colección en una o varias pasadas para aplicar comparaciones e intercambios.

La función swap es tan frecuente que conviene tenerla lista desde el inicio:

void swap(int *a, int *b) {
  int temp = *a;
  *a = *b;
  *b = temp;
}

Con esta utilidad reducimos errores y facilitamos la lectura de los algoritmos que vendrán.

1.4 Cómo se mide la eficiencia (nociones básicas de Big-O)

Usaremos la notación Big-O para describir cómo crece el tiempo de ejecución respecto al tamaño de la lista. Los algoritmos clásicos que veremos tienen complejidad O(n^2) en el peor caso porque realizan comparaciones dobles: una pasada externa y otra interna.

Al comparar algoritmos, nos fijaremos en:

• Tiempo: cantidad de comparaciones e intercambios necesarios.
• Memoria: si necesitan espacio adicional o trabajan in-place.
• Estabilidad: si preservan el orden de elementos equivalentes.

1.5 Cuándo NO conviene estos algoritmos (listas grandes)

Bubble, Insertion y Selection Sort son ideales para listas pequeñas o casi ordenadas, pero no escalan bien. Con colecciones grandes, el costo de O(n^2) se vuelve prohibitivo y conviene pasar a algoritmos de O(n log n), como merge sort o quick sort, o directamente usar las funciones de librería estándar.

En escenarios de producción siempre debemos preguntarnos: ¿el tamaño esperado de la lista justifica un algoritmo cuadrático? Si la respuesta es no, estos métodos pueden servir solo para prototipos o para entender los fundamentos antes de implementar alternativas más eficientes.