El ordenamiento de datos es una operación fundamental en informática, esencial para optimizar la búsqueda, la gestión y el procesamiento de información. Este proceso implica organizar un conjunto de registros de acuerdo con el valor de una o varias claves, ya sea en orden ascendente o descendente. A continuación, exploramos los conceptos esenciales del ordenamiento y una serie de algoritmos clásicos, destacando sus principios, implementaciones y características de rendimiento.
Conceptos Fundamentales en Ordenación
Definición de Ordenamiento
La ordenación es el proceso de organizar una secuencia de elementos para que sus claves sigan una secuencia específica (generalmente numérica o alfabética) y un orden determinado (ascendente o descendente).
Estabilidad de un Algoritmo de Ordenación
Un algoritmo de ordenación se considera estable si, para elementos con claves idénticas, su orden relativo original se mantiene después de la ordenación. Es decir, si el elemento A y el elemento B tienen la misma clave y A aparece antes que B en la secuencia original, A debe seguir apareciendo antes que B en la secuencia ordenada.
Ordenamiento Interno y Externo
- Ordenamiento Interno: Se realiza cuando todos los elementos a ordenar caben en la memoria principal (RAM).
- Ordenamiento Externo: Se aplica a conjuntos de datos tan grandes que no pueden residir completamente en la memoria principal. Requiere el uso de dispositivos de almacenamiento secundario (como discos duros) y un manejo cuidadoso del movimiento de datos entre memoria y almacenamiento.
Aplicaciones del Ordenamiento
Los algoritmos de ordenamiento son omnipresentes en la vida digital, desde la organización de resultados de búsqueda por relevancia o precio en plataformas de comercio electrónico hasta la clasificación de listas de reproducción de música o la gestión de tablas de clasificación en videojuegos. Su eficiencia es clave para la reactividad y funcionalidad de numerosas aplicaciones.
Algoritmos de Ordenación
A continuación, detallamos algunos de los algoritmos de ordenación más conocidos, utilizando ejemplos de código en C para ilustrar su funcionamiento.
1. Ordenamiento de Burbuja (Bubble Sort)
El ordenamiento de burbuja es un algoritmo simple que recorre repetidamente la lista, compara elementos adyacentes y los intercambia si están en el orden incorrecto. El paso a través de la lista se repite hasta que no se necesiten más intercambios, lo que indica que la lista está ordenada.
Implementación en C:
// Función auxiliar para intercambiar dos valores enteros
void intercambiar(int* val1, int* val2) {
int temp = *val1;
*val1 = *val2;
*val2 = temp;
}
// Implementación del Ordenamiento de Burbuja
// Complejidad temporal: O(N^2) en el peor y caso promedio, O(N) en el mejor (lista ya ordenada).
// Complejidad espacial: O(1)
// Estabilidad: Estable
void ordenarBurbuja(int* array, int tamano) {
for (int i = 0; i < tamano - 1; i++) {
int intercambiosRealizados = 0; // Flag para optimización
for (int j = 0; j < tamano - 1 - i; j++) {
if (array[j] > array[j + 1]) {
intercambiar(&array[j], &array[j + 1]);
intercambiosRealizados = 1;
}
}
// Si no hubo intercambios en esta pasada, el array ya está ordenado
if (intercambiosRealizados == 0) {
break;
}
}
}
La complejidad temporal del ordenamiento de burbuja es típicamente O(N2) debido a los dos bucles anidados. Aunque puede reducirse a O(N) si el arreglo ya está ordenado gracias a la optimización con la bandera de intercambiosRealizados.
2. Ordenamiento por Selección (Selection Sort)
Este algoritmo divide la lista en dos partes: una sublista de elementos ya ordenados (al principio de la lista) y una sublista de elementos restantes sin ordenar. En cada paso, el elemento más pequeño (o más grande) de la sublista no ordenada se selecciona y se mueve al final de la sublista ordenada.
- Identificar el elemento con la clave mínima en la sección no ordenada del arreglo.
- Si este elemento no es el primero de la sección no ordenada, intercambiarlo con el primer elemento.
- Repetir el proceso para la sección restante del arreglo hasta que solo quede un elemento.
Implementación en C (mejorada para buscar min y max simultáneamente):
// Implementación del Ordenamiento por Selección (min y max simultáneos)
// Complejidad temporal: O(N^2)
// Complejidad espacial: O(1)
// Estabilidad: Inestable
void ordenarSeleccion(int* array, int tamano) {
int inicio = 0;
int fin = tamano - 1;
while (inicio < fin) {
int indiceMin = inicio;
int indiceMax = inicio;
for (int i = inicio + 1; i <= fin; i++) {
if (array[i] < array[indiceMin]) {
indiceMin = i;
}
if (array[i] > array[indiceMax]) {
indiceMax = i;
}
}
// Mover el mínimo al principio del segmento actual
intercambiar(&array[inicio], &array[indiceMin]);
// Si el elemento máximo estaba en la posición original de 'inicio'
// después del primer intercambio, su nuevo índice es 'indiceMin'.
if (inicio == indiceMax) {
indiceMax = indiceMin;
}
// Mover el máximo al final del segmento actual
intercambiar(&array[fin], &array[indiceMax]);
inicio++;
fin--;
}
}
Aunque la búsqueda de mínimo y máximo simultáneamente reduce el número de pases del bucle externo a la mitad, la complejidad temporal sigue siendo O(N2).
3. Ordenamiento por Inserción Directa (Direct Insertion Sort)
Este algoritmo es análogo a ordenar una mano de cartas. Se toma un elemento de la lista no ordenada y se inserta en su posición correcta dentro de la sublista ya ordenada. Este proceso se repite hasta que todos los elementos se han insertado.
Al insertar el i-ésimo elemento, la sección array\[0\] a array\[i-1\] ya está ordenada. El elemento array\[i\] se compara secuencialmente con los elementos anteriores (array\[i-1\], array\[i-2\], etc.) hasta encontrar su posición correcta. Los elementos mayores se desplazan hacia la derecha para hacer espacio.
Implementación en C:
// Implementación del Ordenamiento por Inserción Directa
// Complejidad temporal: O(N^2) en el peor caso (inverso), O(N) en el mejor (ordenado).
// Complejidad espacial: O(1)
// Estabilidad: Estable
void ordenarInsercion(int* array, int tamano) {
for (int i = 1; i < tamano; i++) {
int indiceAnterior = i - 1;
int valorActual = array[i]; // El elemento a insertar
// Desplazar elementos mayores hacia la derecha
while (indiceAnterior >= 0 && array[indiceAnterior] > valorActual) {
array[indiceAnterior + 1] = array[indiceAnterior];
indiceAnterior--;
}
// Insertar el elemento en su posición correcta
array[indiceAnterior + 1] = valorActual;
}
}
A pesar de su complejidad O(N2) en el peor caso, el ordenamiento por inserción es eficiente para arreglos pequeños o casi ordenados, superando a otros algoritmos de complejidad cuadrática en estas condiciones.
4. Ordenamiento de Shell (Shell Sort)
El ordenamiento de Shell es una mejora del ordenamiento por inserción. Permite el intercambio de elementos que están muy separados, lo que ayuda a mover elementos pequeños hacia el principio y elementos grandes hacia el final más rápidamente. Esto se logra ordenando sublistas de elementos con un "salto" o "brecha" (gap) determinado, que se reduce en cada paso hasta llegar a gap = 1 (lo que se convierte en un ordenamiento por inserción directo final).
Implementación en C:
// Implementación del Ordenamiento de Shell
// Complejidad temporal: Varía, típicamente O(N^(3/2)) o O(N log^2 N), se estima O(N^1.3)
// Complejidad espacial: O(1)
// Estabilidad: Inestable
void ordenarShell(int* array, int tamano) {
int brecha = tamano;
while (brecha > 1) {
// Reducción de la brecha, la secuencia de Knuth (h = h * 3 + 1)
brecha = brecha / 3 + 1;
// Realizar ordenamiento por inserción para la brecha actual
// El bucle empieza desde 'brecha' para que los elementos
// con los que se compara estén dentro de la misma sublista
for (int i = brecha; i < tamano; i++) {
int valorActual = array[i];
int j = i;
// Ordenamiento por inserción en esta sublista (con 'brecha' como paso)
while (j >= brecha && array[j - brecha] > valorActual) {
array[j] = array[j - brecha];
j -= brecha;
}
array[j] = valorActual;
}
}
}
La elección de la secuencia de gap es crucial para la eficiencia del algoritmo. La secuencia gap = gap / 3 + 1 (similar a la secuencia de Knuth) es una de las más eficientes en la práctica, logrando una complejidad temporal cercana a O(N1.3).
5. Ordenamiento por Montículos (Heap Sort)
El ordenamiento por montículos (heap sort) es un algoritmo de ordenamiento basado en comparaciones que utiliza la estructura de datos de un montículo binario (heap). En esencia, convierte el arreglo en un montículo máximo (max-heap), donde el elemento más grande está en la raíz. Luego, extrae repetidamente el elemento raíz (el más grande) y lo coloca al final del arreglo, reconstruyendo el montículo con los elementos restantes.
Implementación en C:
// Ajusta un subárbol enraizado en 'padre' para que sea un montículo máximo.
// 'tamano' es el tamaño del arreglo (considerando solo la parte del montículo).
void ajustarHaciaAbajo(int* array, int tamano, int padre) {
int hijoIzquierdo = 2 * padre + 1;
while (hijoIzquierdo < tamano) {
int hijoMayor = hijoIzquierdo; // Asumimos que el hijo izquierdo es el mayor
int hijoDerecho = 2 * padre + 2;
if (hijoDerecho < tamano && array[hijoDerecho] > array[hijoIzquierdo]) {
hijoMayor = hijoDerecho; // El hijo derecho es mayor
}
if (array[padre] >= array[hijoMayor]) {
break; // El padre ya es mayor que sus hijos
} else {
intercambiar(&array[padre], &array[hijoMayor]);
padre = hijoMayor; // Mover al hijo para seguir ajustando hacia abajo
hijoIzquierdo = 2 * padre + 1;
}
}
}
// Implementación del Ordenamiento por Montículos
// Complejidad temporal: O(N log N)
// Complejidad espacial: O(1)
// Estabilidad: Inestable
void ordenarMonticulos(int* array, int tamano) {
// 1. Construir un montículo máximo (max-heap)
// Empezamos desde el último nodo no hoja (padre del último elemento)
for (int i = (tamano / 2) - 1; i >= 0; i--) {
ajustarHaciaAbajo(array, tamano, i);
}
// 2. Extraer elementos uno por uno del montículo
// Mover la raíz (elemento más grande) al final del arreglo
for (int i = tamano - 1; i > 0; i--) {
intercambiar(&array[0], &array[i]); // Mover la raíz al final
ajustarHaciaAbajo(array, i, 0); // Reajustar el montículo reducido
}
}
El proceso de construcción del montículo tiene una complejidad de O(N), y cada extracción y reajuste toma O(log N). Dado que hay N extracciones, la complejidad total es O(N log N), lo que lo convierte en un algoritmo eficiente para grandes volúmenes de datos.
6. Ordenamiento Rápido (Quick Sort)
El ordenamiento rápido es un algoritmo de ordenamiento por "divide y vencerás". Selecciona un elemento como "pivote" y particiona el resto del arreglo en dos subarreglos: elementos menores que el pivote y elementos mayores que el pivote. Luego, aplica recursivamente este proceso a los subarreglos. Fue propuesto por C.A.R. Hoare en 1962.
(1) Versión Hoare
La partición de Hoare utiliza dos punteros que se mueven desde los extremos hacia el centro. El puntero de la izquierda busca un elemento mayor que el pivote y el de la derecha busca uno menor. Cuando los encuentran, los intercambian. Este proceso continúa hasta que los punteros se cruzan.
Implementación en C (Hoare con optimizaciones):
// Función para encontrar el pivote usando la "mediana de tres"
// Ayuda a evitar el peor caso de O(N^2) cuando el array está casi ordenado
int obtenerPivoteMedianaDeTres(int* array, int inicio, int fin) {
int medio = inicio + (fin - inicio) / 2;
// Asegurarse de que array[medio] es el valor intermedio entre array[inicio], array[medio], array[fin]
if (array[inicio] > array[medio]) intercambiar(&array[inicio], &array[medio]);
if (array[inicio] > array[fin]) intercambiar(&array[inicio], &array[fin]);
if (array[medio] > array[fin]) intercambiar(&array[medio], &array[fin]);
return medio; // Devolver el índice del valor intermedio (ahora en la posición 'medio')
}
// Partición de Hoare
int particionarHoare(int* array, int inicio, int fin) {
// Usar mediana de tres y colocarla en 'inicio' como pivote
int indicePivote = obtenerPivoteMedianaDeTres(array, inicio, fin);
intercambiar(&array[inicio], &array[indicePivote]); // Colocar el pivote al inicio
int valorPivote = array[inicio];
int izq = inicio;
int der = fin;
while (izq < der) {
// Buscar un elemento menor que el pivote desde la derecha
while (izq < der && array[der] >= valorPivote) {
der--;
}
// Buscar un elemento mayor que el pivote desde la izquierda
while (izq < der && array[izq] <= valorPivote) {
izq++;
}
// Intercambiar si los punteros no se han cruzado
if (izq < der) {
intercambiar(&array[izq], &array[der]);
}
}
// Colocar el pivote en su posición final
intercambiar(&array[inicio], &array[izq]);
return izq; // Devolver el índice del pivote final
}
// Implementación principal de Quick Sort (Hoare)
// Complejidad temporal: O(N log N) en promedio, O(N^2) en el peor caso.
// Complejidad espacial: O(log N) para la recursión.
// Estabilidad: Inestable
void ordenarRapidoHoare(int* array, int inicio, int fin) {
if (inicio >= fin) return;
// Optimización para subarreglos pequeños: usar Inserción Directa
// (Asumimos que ordenarInsercion está definido o se incluye aquí para un segmento)
// if (fin - inicio + 1 < 10) {
// ordenarInsercion(array + inicio, fin - inicio + 1);
// return;
// }
int indicePivoteFinal = particionarHoare(array, inicio, fin);
ordenarRapidoHoare(array, inicio, indicePivoteFinal - 1);
ordenarRapidoHoare(array, indicePivoteFinal + 1, fin);
}
(2) Método del Hueco (Lomuto con optimización)
Esta variante del algoritmo de partición (a menudo atribuida a Lomuto, pero presentada aquí con una visión de "hueco") funciona estableciendo un "hueco" en la posición del pivote inicial. Los elementos se mueven para llenar este hueco, creando uno nuevo, hasta que el pivote se coloca en su posición final.
Implementación en C (Método del Hueco):
// Partición usando el método del "hueco"
int particionarHueco(int* array, int inicio, int fin) {
// Usar mediana de tres y colocarla en 'inicio' como pivote
int indicePivote = obtenerPivoteMedianaDeTres(array, inicio, fin);
intercambiar(&array[inicio], &array[indicePivote]); // Colocar el pivote al inicio
int valorPivote = array[inicio];
int izq = inicio;
int der = fin;
int indiceHueco = inicio; // El "hueco" inicial está en la posición del pivote
while (izq < der) {
// Desde la derecha, buscar un elemento menor que el pivote
while (izq < der && array[der] >= valorPivote) {
der--;
}
// Llenar el hueco actual con el elemento encontrado y crear un nuevo hueco
array[indiceHueco] = array[der];
indiceHueco = der; // El nuevo hueco está en 'der'
// Desde la izquierda, buscar un elemento mayor que el pivote
while (izq < der && array[izq] <= valorPivote) {
izq++;
}
// Llenar el hueco actual con el elemento encontrado y crear un nuevo hueco
array[indiceHueco] = array[izq];
indiceHueco = izq; // El nuevo hueco está en 'izq'
}
// Colocar el valor del pivote en el hueco final
array[indiceHueco] = valorPivote;
return indiceHueco;
}
// Función principal de Quick Sort usando partición por el método del hueco
void ordenarRapidoHueco(int* array, int inicio, int fin) {
if (inicio >= fin) return;
int indicePivoteFinal = particionarHueco(array, inicio, fin);
ordenarRapidoHueco(array, inicio, indicePivoteFinal - 1);
ordenarRapidoHueco(array, indicePivoteFinal + 1, fin);
}
(3) Método de los Punteros Adelantados (Lomuto)
La partición de Lomuto utiliza un puntero (ptrMenores) para rastrear el final de la sublista de elementos menores que el pivote y otro puntero (ptrActual) para iterar a través del resto del arreglo. Cuando ptrActual encuentra un elemento menor que el pivote, se incrementa ptrMenores y se intercambian los elementos en ptrActual y ptrMenores.
Implementación en C (Método de los Punteros Adelantados):
// Partición usando el método de punteros adelantados (Lomuto)
int particionarPunterosAdelantados(int* array, int inicio, int fin) {
// Usar mediana de tres y colocarla en 'inicio' como pivote
int indicePivote = obtenerPivoteMedianaDeTres(array, inicio, fin);
intercambiar(&array[inicio], &array[indicePivote]); // Colocar el pivote al inicio
int valorPivote = array[inicio];
int ptrMenores = inicio; // Puntero al final de la sección de elementos menores que el pivote
// ptrActual recorre los elementos desde el segundo
for (int ptrActual = inicio + 1; ptrActual <= fin; ptrActual++) {
if (array[ptrActual] < valorPivote) {
ptrMenores++;
if (ptrMenores != ptrActual) { // Evitar intercambiar un elemento consigo mismo
intercambiar(&array[ptrMenores], &array[ptrActual]);
}
}
}
// Colocar el pivote en su posición final
intercambiar(&array[inicio], &array[ptrMenores]);
return ptrMenores; // Devolver el índice del pivote final
}
// Función principal de Quick Sort usando partición por punteros adelantados
void ordenarRapidoPunterosAdelantados(int* array, int inicio, int fin) {
if (inicio >= fin) return;
int indicePivoteFinal = particionarPunterosAdelantados(array, inicio, fin);
ordenarRapidoPunterosAdelantados(array, inicio, indicePivoteFinal - 1);
ordenarRapidoPunterosAdelantados(array, indicePivoteFinal + 1, fin);
}
(4) Versión No Recursiva
El ordenamiento rápido también se puede implementar de forma no recursiva utilizando una pila para almacenar los rangos de subarreglos que necesitan ser ordenados. Esto evita el riesgo de desbordamiento de pila en el caso de un peor escenario de recursión profunda.
Para la implementación no recursiva, se necesita una estructura de pila. Aquí se muestra una abstracción de cómo funcionaría, asumiendo una pila ya implementada:
// Estructura y funciones básicas de una pila (abstracción)
typedef struct {
int* data;
int top;
int capacity;
} Pila;
void inicializarPila(Pila* p, int cap) {
p->data = (int*)malloc(sizeof(int) * cap);
p->top = -1;
p->capacity = cap;
}
void destruirPila(Pila* p) {
free(p->data);
p->data = NULL;
p->top = -1;
p->capacity = 0;
}
void empujar(Pila* p, int val) {
if (p->top >= p->capacity - 1) { /* Manejo de error: pila llena */ return; }
p->data[++(p->top)] = val;
}
int sacar(Pila* p) {
if (p->top < 0) { /* Manejo de error: pila vacía */ return -1; }
return p->data[(p->top)--];
}
int estaVacia(Pila* p) {
return p->top == -1;
}
// Implementación de Quick Sort no recursivo (usando la partición de Hoare)
void ordenarRapidoNoRecursivo(int* array, int inicio, int fin) {
Pila rangosPila;
inicializarPila(&rangosPila, 100); // Tamaño arbitrario, ajustar si es necesario
empujar(&rangosPila, inicio);
empujar(&rangosPila, fin);
while (!estaVacia(&rangosPila)) {
int finActual = sacar(&rangosPila);
int inicioActual = sacar(&rangosPila);
if (inicioActual < finActual) {
int indicePivote = particionarHoare(array, inicioActual, finActual); // O usar otra partición
// Empujar los subrangos a la pila
if (indicePivote + 1 < finActual) {
empujar(&rangosPila, indicePivote + 1);
empujar(&rangosPila, finActual);
}
if (inicioActual < indicePivote - 1) {
empujar(&rangosPila, inicioActual);
empujar(&rangosPila, indicePivote - 1);
}
}
}
destruirPila(&rangosPila);
}
(5) Optimización: Partición de Tres Vías (Three-Way Partition)
Cuando un arreglo contiene muchos elementos duplicados, las particiones estándar de Quick Sort pueden ser ineficientes. La partición de tres vías clasifica los elementos en tres grupos: menores que el pivote, iguales al pivote, y mayores que el pivote. Esto ayuda a que los elementos iguales al pivote no sean procesados en las llamadas recursivas, mejorando el rendimiento en arreglos con muchos duplicados.
// Implementación de Quick Sort con Partición de Tres Vías
// Complejidad temporal: O(N log N) en promedio. Mejorado para arrays con muchos duplicados.
// Complejidad espacial: O(log N) para la recursión.
// Estabilidad: Inestable
void ordenarRapidoTresVias(int* array, int inicio, int fin) {
if (inicio >= fin) return;
// Seleccionar un pivote aleatorio o con mediana de tres
// Para simplificar, usamos el primer elemento como pivote.
// Para un mejor rendimiento, se recomienda obtenerPivoteMedianaDeTres.
// int indicePivote = obtenerPivoteMedianaDeTres(array, inicio, fin);
// intercambiar(&array[inicio], &array[indicePivote]);
int pivote = array[inicio];
int lt = inicio; // 'lt' rastrea el final de la sección < pivote
int gt = fin; // 'gt' rastrea el inicio de la sección > pivote
int i = inicio + 1; // 'i' es el puntero actual
while (i <= gt) {
if (array[i] < pivote) {
intercambiar(&array[lt], &array[i]);
lt++;
i++;
} else if (array[i] > pivote) {
intercambiar(&array[i], &array[gt]);
gt--;
} else { // array[i] == pivote
i++;
}
}
// Ahora, el array está particionado en [inicio...lt-1] < pivote, [lt...gt] == pivote, [gt+1...fin] > pivote
ordenarRapidoTresVias(array, inicio, lt - 1);
ordenarRapidoTresVias(array, gt + 1, fin);
}
(6) Introsort (Ordenamiento Introspectivo)
Introsort es un algoritmo de ordenamiento híbrido diseñado por David Musser en 1997. Combina Quick Sort, Heap Sort e Insertion Sort para ofrecer el mejor rendimiento en la mayoría de los casos. Utiliza Quick Sort recursivamente, pero si la profundidad de la recursión excede un umbral (generalmente 2 * log N), cambia a Heap Sort para garantizar una complejidad O(N log N) en el peor caso. Para pequeños subarreglos, cambia a Insertion Sort por su eficiencia en datos casi ordenados.
// (Necesita las implementaciones de ordenarInsercion y ordenarMonticulos previamente definidas)
// Calcula log base 2 de N
int logBase2(int n) {
int logN = 0;
while ((1 << logN) <= n) {
logN++;
}
return logN - 1;
}
// Función auxiliar para Introsort
void _introSort(int* array, int inicio, int fin, int profundidadMaxima) {
int tamano = fin - inicio + 1;
// Optimización 1: Subarreglos pequeños con Insertion Sort
if (tamano < 16) { // Umbral común, puede variar
ordenarInsercion(array + inicio, tamano);
return;
}
// Optimización 2: Evitar el peor caso de Quick Sort con Heap Sort
if (profundidadMaxima == 0) {
ordenarMonticulos(array + inicio, tamano);
return;
}
// Usar Quick Sort (usamos particionHoare como ejemplo)
int indicePivoteFinal = particionarHoare(array, inicio, fin);
_introSort(array, inicio, indicePivoteFinal - 1, profundidadMaxima - 1);
_introSort(array, indicePivoteFinal + 1, fin, profundidadMaxima - 1);
}
// Implementación principal de Introsort
// Complejidad temporal: O(N log N) en el mejor, promedio y peor caso.
// Complejidad espacial: O(log N) para la recursión.
// Estabilidad: Inestable
void ordenarIntrospectivo(int* array, int tamano) {
if (tamano <= 1) return;
int profundidadMaxima = 2 * logBase2(tamano); // Umbral típico para cambiar a Heap Sort
_introSort(array, 0, tamano - 1, profundidadMaxima);
}
7. Ordenamiento por Fusión (Merge Sort)
El ordenamiento por fusión (Merge Sort) es un algoritmo de "divide y vencerás" que divide recursivamente un arreglo en dos mitades hasta que cada subarreglo tenga un solo elemento (y por lo tanto esté ordenado). Luego, fusiona (combina) estas mitades ordenadas de manera que el resultado sea un arreglo completamente ordenado.
(1) Versión Recursiva
Implementación en C (Recursiva):
// Función auxiliar para fusionar dos subarreglos ordenados
// [inicio...medio] y [medio+1...fin]
void fusionar(int* array, int* tempArray, int inicio, int medio, int fin) {
int inicio1 = inicio;
int fin1 = medio;
int inicio2 = medio + 1;
int fin2 = fin;
int indiceTemp = inicio;
// Comparar y copiar elementos al arreglo temporal
while (inicio1 <= fin1 && inicio2 <= fin2) {
if (array[inicio1] <= array[inicio2]) {
tempArray[indiceTemp++] = array[inicio1++];
} else {
tempArray[indiceTemp++] = array[inicio2++];
}
}
// Copiar elementos restantes del primer subarreglo
while (inicio1 <= fin1) {
tempArray[indiceTemp++] = array[inicio1++];
}
// Copiar elementos restantes del segundo subarreglo
while (inicio2 <= fin2) {
tempArray[indiceTemp++] = array[inicio2++];
}
// Copiar los elementos ordenados del arreglo temporal de vuelta al arreglo original
for (int i = inicio; i <= fin; i++) {
array[i] = tempArray[i];
}
}
// Función recursiva principal de Merge Sort
void _ordenarFusionRecursivo(int* array, int* tempArray, int inicio, int fin) {
if (inicio >= fin) {
return;
}
int medio = inicio + (fin - inicio) / 2;
_ordenarFusionRecursivo(array, tempArray, inicio, medio);
_ordenarFusionRecursivo(array, tempArray, medio + 1, fin);
fusionar(array, tempArray, inicio, medio, fin);
}
// Implementación de Merge Sort Recursivo
// Complejidad temporal: O(N log N)
// Complejidad espacial: O(N) para el arreglo temporal + O(log N) para la pila de recursión.
// Estabilidad: Estable
void ordenarFusion(int* array, int tamano) {
int* tempArray = (int*)malloc(sizeof(int) * tamano);
if (tempArray == NULL) {
perror("Fallo al asignar memoria para tempArray");
return;
}
_ordenarFusionRecursivo(array, tempArray, 0, tamano - 1);
free(tempArray);
tempArray = NULL;
}
(2) Versión No Recursiva (Iterativa)
El ordenamiento por fusión también se puede implementar de forma iterativa, fusionando subarreglos de tamaño creciente (1, 2, 4, 8, etc.) hasta que todo el arreglo esté ordenado. Esto evita la sobrecarga de la recursión y el riesgo de desbordamiento de pila.
// Implementación de Merge Sort No Recursivo (Iterativo)
// Complejidad temporal: O(N log N)
// Complejidad espacial: O(N) para el arreglo temporal.
// Estabilidad: Estable
void ordenarFusionNoRecursivo(int* array, int tamano) {
int* tempArray = (int*)malloc(sizeof(int) * tamano);
if (tempArray == NULL) {
perror("Fallo al asignar memoria para tempArray");
return;
}
// 'segmentoTam' es el tamaño de los subarreglos a fusionar
for (int segmentoTam = 1; segmentoTam < tamano; segmentoTam *= 2) {
// Recorrer el arreglo, fusionando segmentos de tamaño 'segmentoTam'
for (int i = 0; i < tamano; i += 2 * segmentoTam) {
int inicio1 = i;
int fin1 = i + segmentoTam - 1;
int inicio2 = i + segmentoTam;
int fin2 = i + 2 * segmentoTam - 1;
// Ajustar los límites para el final del arreglo
if (fin1 >= tamano) { // Si el primer segmento ya excede el límite
break;
}
if (fin2 >= tamano) { // Si el segundo segmento excede el límite
fin2 = tamano - 1;
}
// Realizar la fusión de los dos segmentos
// Copiar los elementos al arreglo temporal y luego de vuelta
int idxTemp = i;
int originalInicio1 = inicio1; // Guardar el inicio original para memcpy
while (inicio1 <= fin1 && inicio2 <= fin2) {
if (array[inicio1] <= array[inicio2]) {
tempArray[idxTemp++] = array[inicio1++];
} else {
tempArray[idxTemp++] = array[inicio2++];
}
}
while (inicio1 <= fin1) {
tempArray[idxTemp++] = array[inicio1++];
}
while (inicio2 <= fin2) {
tempArray[idxTemp++] = array[inicio2++];
}
// Copiar los elementos fusionados del arreglo temporal de vuelta al original
for (int k = originalInicio1; k < idxTemp; k++) {
array[k] = tempArray[k];
}
}
}
free(tempArray);
tempArray = NULL;
}
(3) Ordenamiento por Fusión Externa (External Merge Sort)
El ordenamiento externo se usa para conjuntos de datos demasiado grandes para caber en la memoria principal. La estrategia es "ordenar-fusionar": los datos se leen en bloques que caben en memoria, se ordenan internamente, y se escriben en archivos temporales. Luego, estos archivos temporales ordenados se fusionan progresivamente para producir el archivo final ordenado.
Implementación en C (Ejemplo Simplificado de Fusión Externa):
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
// Función de comparación para qsort
int compararEnteros(const void* a, const void* b) {
return (*(int*)a - *(int*)b);
}
// Genera N números aleatorios y los escribe en un archivo
void generarDatosAleatorios(const char* nombreArchivo, int cantidad) {
FILE* archivoSalida = fopen(nombreArchivo, "w");
if (!archivoSalida) {
perror("Error al abrir archivo para escritura");
return;
}
srand((unsigned int)time(NULL));
for (int i = 0; i < cantidad; ++i) {
fprintf(archivoSalida, "%d\n", rand());
}
fclose(archivoSalida);
}
// Lee N datos de 'archivoEntrada', los ordena y los escribe en 'archivoTemporal'
// Retorna la cantidad de datos leídos.
int leerYOrdenarBloque(FILE* archivoEntrada, const char* archivoTemporal, int tamanoBloque) {
int* buffer = (int*)malloc(sizeof(int) * tamanoBloque);
if (!buffer) {
perror("Fallo de malloc para buffer");
return 0;
}
int count = 0;
while (count < tamanoBloque && fscanf(archivoEntrada, "%d", &buffer[count]) != EOF) {
count++;
}
if (count == 0) {
free(buffer);
return 0;
}
qsort(buffer, count, sizeof(int), compararEnteros);
FILE* ftemp = fopen(archivoTemporal, "w");
if (!ftemp) {
perror("Error al abrir archivo temporal para escritura");
free(buffer);
return 0;
}
for (int i = 0; i < count; ++i) {
fprintf(ftemp, "%d\n", buffer[i]);
}
fclose(ftemp);
free(buffer);
return count;
}
// Fusiona dos archivos ordenados (f1, f2) en un tercer archivo (fMerged)
void fusionarArchivos(const char* f1, const char* f2, const char* fMerged) {
FILE* file1 = fopen(f1, "r");
FILE* file2 = fopen(f2, "r");
FILE* merged = fopen(fMerged, "w");
if (!file1 || !file2 || !merged) {
perror("Error al abrir archivos para fusionar");
if (file1) fclose(file1);
if (file2) fclose(file2);
if (merged) fclose(merged);
return;
}
int val1, val2;
int ret1 = fscanf(file1, "%d", &val1);
int ret2 = fscanf(file2, "%d", &val2);
while (ret1 != EOF && ret2 != EOF) {
if (val1 < val2) {
fprintf(merged, "%d\n", val1);
ret1 = fscanf(file1, "%d", &val1);
} else {
fprintf(merged, "%d\n", val2);
ret2 = fscanf(file2, "%d", &val2);
}
}
while (ret1 != EOF) {
fprintf(merged, "%d\n", val1);
ret1 = fscanf(file1, "%d", &val1);
}
while (ret2 != EOF) {
fprintf(merged, "%d\n", val2);
ret2 = fscanf(file2, "%d", &val2);
}
fclose(file1);
fclose(file2);
fclose(merged);
}
// Función principal para el ordenamiento por fusión externa
void ordenarFusionExterna(const char* archivoOriginal, const char* archivoSalida, int tamanoMemoria) {
FILE* entradaOriginal = fopen(archivoOriginal, "r");
if (!entradaOriginal) {
perror("Error al abrir el archivo original");
return;
}
const char* tempFile1 = "temp_sorted_block1.txt";
const char* tempFile2 = "temp_sorted_block2.txt";
const char* mergeResultFile = "temp_merge_result.txt";
// Primera pasada: crear bloques ordenados
int bloquesGenerados = 0;
while (leerYOrdenarBloque(entradaOriginal, tempFile1, tamanoMemoria) > 0) {
bloquesGenerados++;
// En un escenario real, guardar tempFile1 con un nombre único y repetir
// Para este ejemplo simplificado, solo se muestra el principio
break; // Solo para un ejemplo básico
}
fclose(entradaOriginal);
// En un algoritmo completo, aquí se haría un ciclo de fusiones multi-paso.
// Para simplificar, asumimos que 'tempFile1' es el primer bloque ya ordenado
// y el resto de los datos se leerán y fusionarán con él.
// Si solo se generó un bloque o ningún bloque
if (bloquesGenerados == 0) {
// Archivo vacío o muy pequeño
remove(tempFile1);
return;
} else if (bloquesGenerados == 1) {
rename(tempFile1, archivoSalida); // El archivo ya está ordenado
return;
}
// Simulación de la siguiente etapa de fusión
// En un caso real, esto sería un bucle hasta que todos los bloques estén fusionados.
// Aquí, leemos el resto del archivo original por bloques y fusionamos con el resultado acumulado.
// Abre de nuevo el archivo original para continuar leyendo
entradaOriginal = fopen(archivoOriginal, "r");
// Saltar los datos ya procesados en el primer bloque
fseek(entradaOriginal, ftell(entradaOriginal), SEEK_SET);
while(leerYOrdenarBloque(entradaOriginal, tempFile2, tamanoMemoria) > 0) {
fusionarArchivos(tempFile1, tempFile2, mergeResultFile);
remove(tempFile1);
remove(tempFile2);
rename(mergeResultFile, tempFile1); // 'tempFile1' ahora contiene el resultado de la fusión
}
fclose(entradaOriginal);
rename(tempFile1, archivoSalida);
remove(tempFile2); // Por si quedó algo
printf("Ordenamiento externo completado. Resultado en %s\n", archivoSalida);
}
8. Ordenamiento por Conteo (Counting Sort)
El ordenamiento por conteo es un algoritmo de ordenamiento lineal (no basado en comparaciones) adecuado para ordenar números enteros dentro de un rango específico. No compara elementos, sino que cuenta la frecuencia de cada valor y usa esa información para colocar los elementos en su posición correcta.
Implementación en C:
// Implementación del Ordenamiento por Conteo
// Complejidad temporal: O(N + R), donde R es el rango de los valores (max - min + 1).
// Complejidad espacial: O(R)
// Estabilidad: Estable (con una implementación cuidadosa, como la de abajo)
void ordenarConteo(int* array, int tamano) {
if (tamano <= 1) return;
// 1. Encontrar el valor mínimo y máximo para determinar el rango
int minVal = array[0];
int maxVal = array[0];
for (int i = 1; i < tamano; i++) {
if (array[i] < minVal) minVal = array[i];
if (array[i] > maxVal) maxVal = array[i];
}
int rango = maxVal - minVal + 1;
int* recuento = (int*)calloc(rango, sizeof(int)); // calloc inicializa a 0
if (recuento == NULL) {
perror("Fallo al asignar memoria para recuento");
return;
}
// 2. Contar la frecuencia de cada elemento
for (int i = 0; i < tamano; i++) {
recuento[array[i] - minVal]++;
}
// 3. Modificar el arreglo de recuento para almacenar posiciones finales
// Esto hace que el algoritmo sea estable
for (int i = 1; i < rango; i++) {
recuento[i] += recuento[i - 1];
}
// 4. Crear un arreglo temporal para almacenar los elementos ordenados
int* arregloSalida = (int*)malloc(sizeof(int) * tamano);
if (arregloSalida == NULL) {
perror("Fallo al asignar memoria para arregloSalida");
free(recuento);
return;
}
// 5. Construir el arreglo ordenado (recorriendo el original de derecha a izquierda para estabilidad)
for (int i = tamano - 1; i >= 0; i--) {
arregloSalida[recuento[array[i] - minVal] - 1] = array[i];
recuento[array[i] - minVal]--;
}
// 6. Copiar los elementos ordenados de vuelta al arreglo original
for (int i = 0; i < tamano; i++) {
array[i] = arregloSalida[i];
}
free(recuento);
free(arregloSalida);
}
La eficiencia del ordenamiento por conteo depende en gran medida del rango de los valores de entrada. Si el rango es comparable al número de elementos, es muy eficiente (O(N)), pero si el rango es mucho mayor que N, su complejidad espacial y temporal se deteriora.
9. Ordenamiento por Cubos (Bucket Sort)
El ordenamiento por cubos (Bucket Sort) es un algoritmo de ordenamiento que distribuye los elementos de un arreglo en un número finito de "cubos" (buckets). Cada cubo se ordena individualmente (usando otro algoritmo de ordenamiento, como inserción) y luego los elementos de los cubos se concatenan en orden para formar el arreglo final ordenado.
Es efectivo cuando los datos de entrada están uniformemente distribuidos en un rango. No se proporcionará código detallado aquí, ya que el enfoque depende de la implementación de los "cubos" (listas enlazadas, arreglos dinámicos, etc.).
10. Ordenamiento por Radix (Radix Sort)
El ordenamiento por radix (Radix Sort) es un algoritmo de ordenamiento lineal que ordena los números procesando los dígitos individuales desde el menos significativo al más significativo (LSD Radix Sort) o viceversa (MSD Radix Sort). Utiliza un algoritmo de ordenamiento estable auxiliar (como el ordenamiento por conteo) para ordenar los números basándose en el valor de cada dígito.
Este algoritmo es eficiente para ordenar enteros largos o cadenas de caracteres. Al igual que el ordenamiento por cubos, su implementación puede ser compleja y no se incluye un ejemplo de código completo aquí.
Evaluación del Rendimiento de Algoritmos
Para comprender la eficiencia práctica de estos algoritmos, es común realizar pruebas de rendimiento que midan el tiempo de ejecución en diversas condiciones. Un ejemplo de código para comparar el tiempo de ejecución en C:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h> // Para memcpy, memset
// Incluir todas las funciones de ordenamiento implementadas arriba
// #include "ordenamientos.h"
// Función auxiliar para imprimir un arreglo (opcional)
void imprimirArray(int* array, int tamano) {
for (int i = 0; i < tamano; i++) {
printf("%d ", array[i]);
}
printf("\n");
}
void probarRendimiento() {
srand((unsigned int)time(NULL));
const int N = 100000; // Tamaño del arreglo para la prueba
int* arrOriginal = (int*)malloc(sizeof(int) * N);
// Generar datos aleatorios una sola vez
for (int i = 0; i < N; i++) {
arrOriginal[i] = rand() + i; // Datos con cierta distribución
}
// Crear copias del arreglo original para cada algoritmo
int* arrCopia1 = (int*)malloc(sizeof(int) * N);
int* arrCopia2 = (int*)malloc(sizeof(int) * N);
int* arrCopia3 = (int*)malloc(sizeof(int) * N);
int* arrCopia4 = (int*)malloc(sizeof(int) * N);
int* arrCopia5 = (int*)malloc(sizeof(int) * N);
int* arrCopia6 = (int*)malloc(sizeof(int) * N);
int* arrCopia7 = (int*)malloc(sizeof(int) * N);
int* arrCopia8 = (int*)malloc(sizeof(int) * N);
clock_t tiempoInicio, tiempoFin;
// Prueba de Ordenamiento por Inserción
memcpy(arrCopia1, arrOriginal, sizeof(int) * N);
tiempoInicio = clock();
ordenarInsercion(arrCopia1, N);
tiempoFin = clock();
printf("Tiempo Insercion: %ld ms\n", (long)(tiempoFin - tiempoInicio));
// Prueba de Ordenamiento de Shell
memcpy(arrCopia2, arrOriginal, sizeof(int) * N);
tiempoInicio = clock();
ordenarShell(arrCopia2, N);
tiempoFin = clock();
printf("Tiempo Shell: %ld ms\n", (long)(tiempoFin - tiempoInicio));
// Prueba de Ordenamiento por Montículos
memcpy(arrCopia3, arrOriginal, sizeof(int) * N);
tiempoInicio = clock();
ordenarMonticulos(arrCopia3, N);
tiempoFin = clock();
printf("Tiempo Monticulos: %ld ms\n", (long)(tiempoFin - tiempoInicio));
// Prueba de Ordenamiento de Burbuja
memcpy(arrCopia4, arrOriginal, sizeof(int) * N);
tiempoInicio = clock();
ordenarBurbuja(arrCopia4, N);
tiempoFin = clock();
printf("Tiempo Burbuja: %ld ms\n", (long)(tiempoFin - tiempoInicio));
// Prueba de Ordenamiento por Selección
memcpy(arrCopia5, arrOriginal, sizeof(int) * N);
tiempoInicio = clock();
ordenarSeleccion(arrCopia5, N);
tiempoFin = clock();
printf("Tiempo Seleccion: %ld ms\n", (long)(tiempoFin - tiempoInicio));
// Prueba de Ordenamiento Rápido (Hoare)
memcpy(arrCopia6, arrOriginal, sizeof(int) * N);
tiempoInicio = clock();
ordenarRapidoHoare(arrCopia6, 0, N - 1); // O usar ordenarIntrospectivo(arrCopia6, N);
tiempoFin = clock();
printf("Tiempo QuickSort: %ld ms\n", (long)(tiempoFin - tiempoInicio));
// Prueba de Ordenamiento por Fusión
memcpy(arrCopia7, arrOriginal, sizeof(int) * N);
tiempoInicio = clock();
ordenarFusion(arrCopia7, N); // O usar ordenarFusionNoRecursivo(arrCopia7, N);
tiempoFin = clock();
printf("Tiempo MergeSort: %ld ms\n", (long)(tiempoFin - tiempoInicio));
// Prueba de Ordenamiento por Conteo
memcpy(arrCopia8, arrOriginal, sizeof(int) * N);
tiempoInicio = clock();
ordenarConteo(arrCopia8, N);
tiempoFin = clock();
printf("Tiempo Conteo: %ld ms\n", (long)(tiempoFin - tiempoInicio));
free(arrOriginal);
free(arrCopia1); free(arrCopia2); free(arrCopia3); free(arrCopia4);
free(arrCopia5); free(arrCopia6); free(arrCopia7); free(arrCopia8);
}
Resumen Comparativo de Algoritmos de Ordenación
La siguiente tabla resume las características clave de los algoritmos de ordenación más comunes:
| Algoritmo | Complejidad Temporal (Mejor Caso) | Complejidad Temporal (Caso Promedio) | Complejidad Temporal (Peor Caso) | Complejidad Espacial | Estabilidad | Tipo |
|---|---|---|---|---|---|---|
| Burbuja | O(N) | O(N2) | O(N2) | O(1) | Sí | Comparación |
| Selección | O(N2) | O(N2) | O(N2) | O(1) | No | Comparación |
| Inserción Directa | O(N) | O(N2) | O(N2) | O(1) | Sí | Comparación |
| Shell | O(N log2 N) | O(N log2 N) o O(N1.3) | O(N2) | O(1) | No | Comparación |
| Montículos | O(N log N) | O(N log N) | O(N log N) | O(1) | No | Comparación |
| Rápido | O(N log N) | O(N log N) | O(N2) | O(log N) | No | Comparación |
| Fusión | O(N log N) | O(N log N) | O(N log N) | O(N) | Sí | Comparación |
| Conteo | O(N + R) | O(N + R) | O(N + R) | O(R) | Sí | No Comparación |
| Cubos | O(N + K) | O(N + K) | O(N2) | O(N + K) | Sí | No Comparación |
| Radix | O(N * K) | O(N * K) | O(N * K) | O(N + K) | Sí | No Comparación |
Donde N es el número de elementos, R es el rango de valores, y K es el número de cubos o el número de dígitos (para Radix Sort).