Este artículo está dedicado a programadores en C que buscan dominar algoritmos de ordenación eficientes. Si ya conoces los métodos básicos y deseas explorar técnicas más veloces, aquí profundizaremos en los principios e implementaciones de quicksort, mergesort y heasport.

Aprenderás a:

1. Comprender la idea central de tres algoritmos de ordenación eficientes.
2. Dominar la estrategia divide y vencerás de quicksort y su implementación.
3. Dominar las técnicas de fusión de mergesort y su aplicación.
4. Dominar el uso de la estructura de datos de montículo (heap) en heapsort.
5. Aprender a seleccionar el algoritmo eficiente adecuado según el escenario.

¡Comencemos a explorar el mundo refinado de los algoritmos de ordenación eficientes!

Sección 1: La Necesidad de la Ordenación Eficiente

1. De lo Básico a lo Avanzado

Algoritmos de ordenación fundamentales con complejidad temporal O(n²) presentan un cuello de botella de rendimiento evidente al escalar:

• 1000 elementos: aproximadamente 1 millón de operaciones.
• 10,000 elementos: aproximadamente 100 millones de operaciones.
• 100,000 elementos: aproximadamente 10 mil millones de operaciones.

Los algoritmos eficientes reducen esta complejidad a O(n log n) mediante estrategias más inteligentes, mejorando drásticamente el manejo de grandes volúmenes de datos.

Ejemplo de Código: Comparación de Rendimiento

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

// Ordenación por Inserción - O(n²)
void insertionSort(int datos[], int longitud) {
    for (int idx = 1; idx < longitud; idx++) {
        int valorActual = datos[idx];
        int pos = idx - 1;
        while (pos >= 0 && datos[pos] > valorActual) {
            datos[pos + 1] = datos[pos];
            pos--;
        }
        datos[pos + 1] = valorActual;
    }
}

// Declaración adelantada de quickSort
void quickSort(int datos[], int inicio, int fin);

void compararRendimiento() {
    const int cantidad = 10000;
    int *conjuntoA = (int*)malloc(cantidad * sizeof(int));
    int *conjuntoB = (int*)malloc(cantidad * sizeof(int));
    
    // Población con datos aleatorios
    for (int i = 0; i < cantidad; i++) {
        conjuntoA[i] = rand() % 10000;
        conjuntoB[i] = conjuntoA[i]; // Clonar los mismos datos
    }
    
    printf("Volumen de datos: %d elementos\n", cantidad);
    
    // Medir inserción
    clock_t inicio = clock();
    insertionSort(conjuntoA, cantidad);
    clock_t fin = clock();
    printf("Tiempo de inserción: %.3f s\n", (double)(fin - inicio) / CLOCKS_PER_SEC);
    
    // Medir quicksort
    inicio = clock();
    quickSort(conjuntoB, 0, cantidad - 1);
    fin = clock();
    printf("Tiempo de quicksort: %.3f s\n", (double)(fin - inicio) / CLOCKS_PER_SEC);
    
    free(conjuntoA);
    free(conjuntoB);
}

// Implementación de quickSort
void quickSort(int datos[], int inicio, int fin) {
    if (inicio < fin) {
        // Paso de partición
        int pivote = datos[fin];
        int i = inicio - 1;
        
        for (int j = inicio; j < fin; j++) {
            if (datos[j] < pivote) {
                i++;
                int temp = datos[i];
                datos[i] = datos[j];
                datos[j] = temp;
            }
        }
        
        int temp = datos[i + 1];
        datos[i + 1] = datos[fin];
        datos[fin] = temp;
        int puntoDivision = i + 1;
        
        // Recursión
        quickSort(datos, inicio, puntoDivision - 1);
        quickSort(datos, puntoDivision + 1, fin);
    }
}

int main() {
    compararRendimiento();
    return 0;
}

Salida esperada:

Volumen de datos: 10000 elementos
Tiempo de inserción: 0.045 s
Tiempo de quicksort: 0.002 s

2. Panorama General de Algoritmos Eficientes

Sección 2: Quicksort

1. Principio de Divide y Vencerás

La estrategia de quicksort:

1. Elegir pivote: Seleccionar un elemento como referencia.
2. Particionar: Reordenar el arreglo de modo que los elementos menores queden a la izquierda del pivote y los mayores a la derecha.
3. Recursión: Aplicar quicksort a cada sub-arreglo resultante.

Ejemplo de Código: Implementación con Visualización

#include <stdio.h>

// Función de partición: devuelve la posición final del pivote
int particionar(int arr[], int izq, int der) {
    int pivote = arr[der];  // Seleccionar el último como pivote
    int indiceMenor = izq - 1; // Índice del último elemento menor
    
    printf("Antes de particionar: ");
    for (int k = izq; k <= der; k++) printf("%d ", arr[k]);
    printf("(pivote: %d)\n", pivote);
    
    for (int j = izq; j < der; j++) {
        if (arr[j] <= pivote) {
            indiceMenor++;
            // Intercambiar arr[indiceMenor] y arr[j]
            int temp = arr[indiceMenor];
            arr[indiceMenor] = arr[j];
            arr[j] = temp;
        }
    }
    
    // Ubicar el pivote en su posición correcta
    int temp = arr[indiceMenor + 1];
    arr[indiceMenor + 1] = arr[der];
    arr[der] = temp;
    
    printf("Después de particionar: ");
    for (int k = izq; k <= der; k++) printf("%d ", arr[k]);
    printf("(pivote en índice %d)\n\n", indiceMenor + 1);
    
    return indiceMenor + 1;
}

void quickSort(int arr[], int izq, int der) {
    if (izq < der) {
        int puntoDivision = particionar(arr, izq, der);
        quickSort(arr, izq, puntoDivision - 1);
        quickSort(arr, puntoDivision + 1, der);
    }
}

void mostrarArreglo(int arr[], int tam) {
    for (int i = 0; i < tam; i++) printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int datos[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(datos) / sizeof(datos[0]);
    
    printf("Arreglo original: ");
    mostrarArreglo(datos, n);
    printf("\n=== Proceso de Quicksort ===\n");
    quickSort(datos, 0, n - 1);
    
    printf("Resultado final: ");
    mostrarArreglo(datos, n);
    return 0;
}

2. Optimización de Quicksort

La versión básica puede degradarse a O(n²). Se puede optimizar mediante la selección inteligente del pivote.

Ejemplo de Código: Quicksort Optimizado

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// Selección de pivote por mediana de tres
int pivoteMedianaDeTres(int arr[], int izq, int der) {
    int centro = izq + (der - izq) / 2;
    
    // Ordenar los tres elementos
    if (arr[izq] > arr[centro]) {
        int temp = arr[izq]; arr[izq] = arr[centro]; arr[centro] = temp;
    }
    if (arr[izq] > arr[der]) {
        int temp = arr[izq]; arr[izq] = arr[der]; arr[der] = temp;
    }
    if (arr[centro] > arr[der]) {
        int temp = arr[centro]; arr[centro] = arr[der]; arr[der] = temp;
    }
    
    // Colocar la mediana en der-1
    int temp = arr[centro];
    arr[centro] = arr[der - 1];
    arr[der - 1] = temp;
    return arr[der - 1];
}

// Partición optimizada
int particionOptimizada(int arr[], int izq, int der) {
    int pivote = pivoteMedianaDeTres(arr, izq, der);
    int i = izq;
    int j = der - 1;
    
    while (1) {
        while (arr[++i] < pivote);
        while (arr[--j] > pivote);
        if (i < j) {
            int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
        } else {
            break;
        }
    }
    
    int temp = arr[i];
    arr[i] = arr[der - 1];
    arr[der - 1] = temp;
    return i;
}

void quickSortOptimizado(int arr[], int izq, int der) {
    // Usar inserción para arreglos pequeños
    if (der - izq + 1 <= 10) {
        for (int i = izq + 1; i <= der; i++) {
            int clave = arr[i];
            int j = i - 1;
            while (j >= izq && arr[j] > clave) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = clave;
        }
        return;
    }
    
    if (izq < der) {
        int p = particionOptimizada(arr, izq, der);
        quickSortOptimizado(arr, izq, p - 1);
        quickSortOptimizado(arr, p + 1, der);
    }
}

// Función de prueba
void probarOptimizacion() {
    const int tamano = 1000;
    int *arrPeorCaso = (int*)malloc(tamano * sizeof(int));
    int *arrOptimizado = (int*)malloc(tamano * sizeof(int));
    
    for (int i = 0; i < tamano; i++) {
        arrPeorCaso[i] = i;
        arrOptimizado[i] = i;
    }
    
    printf("Prueba con caso peor (arreglo ordenado):\n");
    
    clock_t inicio = clock();
    quickSort(arrPeorCaso, 0, tamano - 1);
    clock_t fin = clock();
    printf("Quicksort básico: %.3f s\n", (double)(fin - inicio) / CLOCKS_PER_SEC);
    
    inicio = clock();
    quickSortOptimizado(arrOptimizado, 0, tamano - 1);
    fin = clock();
    printf("Quicksort optimizado: %.3f s\n", (double)(fin - inicio) / CLOCKS_PER_SEC);
    
    free(arrPeorCaso);
    free(arrOptimizado);
}

// Implementación básica para comparación
void quickSort(int arr[], int izq, int der) {
    if (izq < der) {
        int pivote = arr[der];
        int i = izq - 1;
        for (int j = izq; j < der; j++) {
            if (arr[j] <= pivote) {
                i++;
                int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
            }
        }
        int temp = arr[i+1]; arr[i+1] = arr[der]; arr[der] = temp;
        int p = i+1;
        quickSort(arr, izq, p-1);
        quickSort(arr, p+1, der);
    }
}

int main() {
    probarOptimizacion();
    return 0;
}

Sección 3: Mergesort

1. El Arte de la Fusión Ordenada

La estrategia de mergesort:

1. Dividir: Partir el arreglo en dos mitades.
2. Conquistar: Ordenar recursivamente cada mitad.
3. Combinar: Fusionar las dos mitades ya ordenadas en una sola.

Ejemplo de Código: Implementación Paso a Paso

#include <stdio.h>
#include <stdlib.h>

// Fusionar dos sub-arreglos ordenados
void fusionar(int arr[], int izq, int medio, int der) {
    int tamIzq = medio - izq + 1;
    int tamDer = der - medio;
    
    int *tempIzq = (int*)malloc(tamIzq * sizeof(int));
    int *tempDer = (int*)malloc(tamDer * sizeof(int));
    
    for (int i = 0; i < tamIzq; i++) tempIzq[i] = arr[izq + i];
    for (int j = 0; j < tamDer; j++) tempDer[j] = arr[medio + 1 + j];
    
    int i = 0, j = 0, k = izq;
    
    printf("Fusionando [%d-%d] y [%d-%d]: ", izq, medio, medio+1, der);
    
    while (i < tamIzq && j < tamDer) {
        if (tempIzq[i] <= tempDer[j]) {
            arr[k++] = tempIzq[i++];
        } else {
            arr[k++] = tempDer[j++];
        }
    }
    
    while (i < tamIzq) arr[k++] = tempIzq[i++];
    while (j < tamDer) arr[k++] = tempDer[j++];
    
    for (int idx = izq; idx <= der; idx++) printf("%d ", arr[idx]);
    printf("\n");
    
    free(tempIzq);
    free(tempDer);
}

void mergeSort(int arr[], int izq, int der) {
    if (izq < der) {
        int medio = izq + (der - izq) / 2;
        printf("Dividir: [%d-%d] en [%d-%d] y [%d-%d]\n", izq, der, izq, medio, medio+1, der);
        mergeSort(arr, izq, medio);
        mergeSort(arr, medio + 1, der);
        fusionar(arr, izq, medio, der);
    }
}

int main() {
    int datos[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(datos) / sizeof(datos[0]);
    
    printf("Arreglo original: ");
    for (int i = 0; i < n; i++) printf("%d ", datos[i]);
    printf("\n\n=== Proceso de Mergesort ===\n");
    mergeSort(datos, 0, n - 1);
    printf("\nResultado final: ");
    for (int i = 0; i < n; i++) printf("%d ", datos[i]);
    printf("\n");
    return 0;
}

2. Aplicaciones de Mergesort

Su estabilidad lo hace ideal para ordenamiento por múltiples criterios.

Ejemplo de Código: Ordenar Estructuras con Múltiples Claves

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    char nombre[50];
    int calificacion;
    int matricula;
} Estudiante;

// Comparación: calificación descendente, luego matrícula ascendente
int compararEstudiantes(const Estudiante *a, const Estudiante *b) {
    if (a->calificacion != b->calificacion) {
        return b->calificacion - a->calificacion;
    }
    return a->matricula - b->matricula;
}

void fusionarEstudiantes(Estudiante arr[], int izq, int medio, int der) {
    int n1 = medio - izq + 1;
    int n2 = der - medio;
    
    Estudiante *L = (Estudiante*)malloc(n1 * sizeof(Estudiante));
    Estudiante *R = (Estudiante*)malloc(n2 * sizeof(Estudiante));
    
    for (int i = 0; i < n1; i++) L[i] = arr[izq + i];
    for (int j = 0; j < n2; j++) R[j] = arr[medio + 1 + j];
    
    int i = 0, j = 0, k = izq;
    while (i < n1 && j < n2) {
        if (compararEstudiantes(&L[i], &R[j]) <= 0) {
            arr[k++] = L[i++];
        } else {
            arr[k++] = R[j++];
        }
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
    
    free(L);
    free(R);
}

void mergeSortEstudiantes(Estudiante arr[], int izq, int der) {
    if (izq < der) {
        int medio = izq + (der - izq) / 2;
        mergeSortEstudiantes(arr, izq, medio);
        mergeSortEstudiantes(arr, medio + 1, der);
        fusionarEstudiantes(arr, izq, medio, der);
    }
}

int main() {
    Estudiante alumnos[] = {
        {"Ana", 85, 1001},
        {"Bruno", 92, 1002},
        {"Carla", 85, 1003},
        {"David", 78, 1004},
        {"Elena", 92, 1005}
    };
    int n = sizeof(alumnos) / sizeof(alumnos[0]);
    
    printf("Datos originales:\n");
    for (int i = 0; i < n; i++) {
        printf("%s\t%d\t%d\n", alumnos[i].nombre, alumnos[i].calificacion, alumnos[i].matricula);
    }
    
    printf("\nOrdenando por calificación descendente, luego matrícula...\n");
    mergeSortEstudiantes(alumnos, 0, n - 1);
    
    printf("\nResultado:\n");
    for (int i = 0; i < n; i++) {
        printf("%s\t%d\t%d\n", alumnos[i].nombre, alumnos[i].calificacion, alumnos[i].matricula);
    }
    return 0;
}

Sección 4: Heapsort

1. Principio del Montículo

Heapsort utiliza la propiedad del montículo máximo:

1. Construir montículo: Transformar el arreglo en un montículo máximo.
2. Ordenar: Extraer repetidamente el elemento máximo (raíz) y reestructurar el montículo.

Ejemplo de Código: Implementación Detallada

#include <stdio.h>

// Ajustar el montículo para el nodo i
void ajustarMonticulo(int arr[], int n, int i) {
    int mayor = i;
    int hijoIzq = 2 * i + 1;
    int hijoDer = 2 * i + 2;
    
    if (hijoIzq < n && arr[hijoIzq] > arr[mayor]) mayor = hijoIzq;
    if (hijoDer < n && arr[hijoDer] > arr[mayor]) mayor = hijoDer;
    
    if (mayor != i) {
        int temp = arr[i];
        arr[i] = arr[mayor];
        arr[mayor] = temp;
        ajustarMonticulo(arr, n, mayor);
    }
}

void heapSort(int arr[], int n) {
    printf("=== Construyendo montículo máximo ===\n");
    for (int i = n / 2 - 1; i >= 0; i--) {
        ajustarMonticulo(arr, n, i);
        printf("Ajustado nodo %d: ", i);
        for (int j = 0; j < n; j++) printf("%d ", arr[j]);
        printf("\n");
    }
    
    printf("\n=== Proceso de ordenación ===\n");
    for (int i = n - 1; i > 0; i--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        
        printf("Intercambio: %d a posición %d. ", temp, i);
        for (int j = 0; j < n; j++) printf("%d ", arr[j]);
        printf("\n");
        
        ajustarMonticulo(arr, i, 0);
    }
}

int main() {
    int datos[] = {4, 10, 3, 5, 1};
    int n = sizeof(datos) / sizeof(datos[0]);
    
    printf("Arreglo original: ");
    for (int i = 0; i < n; i++) printf("%d ", datos[i]);
    printf("\n\n");
    
    heapSort(datos, n);
    
    printf("\nResultado final: ");
    for (int i = 0; i < n; i++) printf("%d ", datos[i]);
    printf("\n");
    return 0;
}

2. Aplicaciones Especiales de Heapsort

Ideal para obtener los K elementos más grandes de un conjunto sin ordenar completamente.

Ejemplo de Código: Obtener los Top K Elementos

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void obtenerTopK(int arr[], int n, int k) {
    // Construir un montículo mínimo de tamaño k
    for (int i = k / 2 - 1; i >= 0; i--) {
        int menor = i;
        int izq = 2*i + 1;
        int der = 2*i + 2;
        
        if (izq < k && arr[izq] < arr[menor]) menor = izq;
        if (der < k && arr[der] < arr[menor]) menor = der;
        
        if (menor != i) {
            int temp = arr[i]; arr[i] = arr[menor]; arr[menor] = temp;
        }
    }
    
    // Procesar los elementos restantes
    for (int i = k; i < n; i++) {
        if (arr[i] > arr[0]) {
            arr[0] = arr[i];
            // Reajustar montículo mínimo
            int j = 0;
            while (j < k) {
                int menor = j;
                int izq = 2*j + 1;
                int der = 2*j + 2;
                if (izq < k && arr[izq] < arr[menor]) menor = izq;
                if (der < k && arr[der] < arr[menor]) menor = der;
                if (menor == j) break;
                int temp = arr[j]; arr[j] = arr[menor]; arr[menor] = temp;
                j = menor;
            }
        }
    }
    
    // Ordenar los k elementos (usando burbuja simple)
    for (int i = 0; i < k - 1; i++) {
        for (int j = 0; j < k - i - 1; j++) {
            if (arr[j] < arr[j+1]) {
                int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp;
            }
        }
    }
}

void probarTopK() {
    const int n = 20;
    const int k = 5;
    int arr[n];
    
    srand(time(NULL));
    printf("Conjunto original: ");
    for (int i = 0; i < n; i++) {
        arr[i] = rand() % 100;
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    int copia[n];
    for (int i = 0; i < n; i++) copia[i] = arr[i];
    
    obtenerTopK(copia, n, k);
    
    printf("Los %d mayores: ", k);
    for (int i = 0; i < k; i++) printf("%d ", copia[i]);
    printf("\n");
}

int main() {
    probarTopK();
    return 0;
}

Sección 5: Comparación y Selección

1. Rendimiento Comparativo

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// Funciones de ordenación (versiones simplificadas para el ejemplo)
void qs(int a[], int l, int h) {
    if (l < h) {
        int p = a[h], i = l-1;
        for (int j=l; j<h; j++) if (a[j]<=p) { i++; int t=a[i]; a[i]=a[j]; a[j]=t; }
        int t=a[i+1]; a[i+1]=a[h]; a[h]=t; int pi=i+1;
        qs(a,l,pi-1); qs(a,pi+1,h);
    }
}
void merge(int a[], int l, int m, int r) {
    int n1=m-l+1, n2=r-m;
    int *L=malloc(n1*sizeof(int)), *R=malloc(n2*sizeof(int));
    for (int i=0;i<n1;i++) L[i]=a[l+i];
    for (int j=0;j<n2;j++) R[j]=a[m+1+j];
    int i=0,j=0,k=l;
    while(i<n1&&j<n2) a[k++]=L[i]<=R[j]?L[i++]:R[j++];
    while(i<n1) a[k++]=L[i++];
    while(j<n2) a[k++]=R[j++];
    free(L); free(R);
}
void ms(int a[], int l, int r) {
    if (l<r) { int m=l+(r-l)/2; ms(a,l,m); ms(a,m+1,r); merge(a,l,m,r); }
}
void heapify(int a[], int n, int i) {
    int largest=i, l=2*i+1, r=2*i+2;
    if (l<n&&a[l]>a[largest]) largest=l;
    if (r<n&&a[r]>a[largest]) largest=r;
    if (largest!=i) { int t=a[i]; a[i]=a[largest]; a[largest]=t; heapify(a,n,largest); }
}
void hs(int a[], int n) {
    for (int i=n/2-1;i>=0;i--) heapify(a,n,i);
    for (int i=n-1;i>0;i--) { int t=a[0]; a[0]=a[i]; a[i]=t; heapify(a,i,0); }
}

void pruebaRendimiento() {
    const int tamanos[] = {1000, 5000, 10000};
    const char *nombres[] = {"Quicksort", "Mergesort", "Heapsort"};
    
    printf("Comparación de Algoritmos de Ordenación Eficiente\n");
    printf("===============================================\n\n");
    
    for (int s = 0; s < 3; s++) {
        int n = tamanos[s];
        int *original = malloc(n * sizeof(int));
        int *copia = malloc(n * sizeof(int));
        
        for (int i = 0; i < n; i++) original[i] = rand() % 10000;
        
        printf("Tamaño de datos: %d\n", n);
        printf("Algoritmo\tTiempo (s)\n");
        printf("--------\t----------\n");
        
        for (int i = 0; i < n; i++) copia[i] = original[i];
        clock_t inicio = clock();
        qs(copia, 0, n-1);
        clock_t fin = clock();
        printf("%s\t\t%.6f\n", nombres[0], (double)(fin-inicio)/CLOCKS_PER_SEC);
        
        for (int i = 0; i < n; i++) copia[i] = original[i];
        inicio = clock();
        ms(copia, 0, n-1);
        fin = clock();
        printf("%s\t\t%.6f\n", nombres[1], (double)(fin-inicio)/CLOCKS_PER_SEC);
        
        for (int i = 0; i < n; i++) copia[i] = original[i];
        inicio = clock();
        hs(copia, n);
        fin = clock();
        printf("%s\t\t%.6f\n", nombres[2], (double)(fin-inicio)/CLOCKS_PER_SEC);
        
        printf("\n");
        free(original);
        free(copia);
    }
}

int main() {
    pruebaRendimiento();
    return 0;
}

2. Guía para Seleccionar el Algoritmo