Explorando Algoritmos Clásicos de Ordenamiento: Implementación y Análisis

Los algoritmos de ordenamiento son fundamentales en la informática, permitiendo organizar datos de manera eficiente. Esta sección profundiza en la implementación y las características de los algoritmos de ordenamiento más comunes.

1. Conceptos Fundamentales del Ordenamiento

El ordenamiento consiste en organizar una secuencia de registros según el valor de una o más claves, ya sea en orden ascendente o descendente. Algunos conceptos clave incluyen:

  • Estabilidad: Un algoritmo de ordenamiento es estable si mantiene el orden relativo de los elementos con claves iguales. Es decir, si dos elementos r[i] y r[j] tienen la misma clave y r[i] aparece antes que r[j] en la secuencia original, seguirán manteniendo ese orden después de ser ordenados.
  • Ordenamiento Interno: Todos los elementos de datos caben en la memoria principal durante el proceso.
  • Ordenamiento Externo: Cuando el volumen de datos excede la capacidad de la memoria principal, requiriendo movimientos de datos entre memoria principal y secundaria.

2. Ordenamiento por Inserción

2.1 Ordenamiento por Inserción Directa

Este es uno de los métodos de ordenamiento más sencillos. Su lógica se asemeja a cómo se ordenan las cartas en la mano de un jugador de póker.

Principio Algorítmico

Se construye una lista ordenada insertando un elemento a la vez en su posición correcta dentro de la sublista ya ordenada. Se toma un elemento del segmento no ordenado y se lo compara con los elementos del segmento ordenado, desplazando los elementos mayores (o menores) para hacer espacio hasta encontrar su ubicación adecuada.

Implementación en C

Consideremos un arreglo de números enteros. La función ordenarInsercionDirecta implementa este método:

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

// Ordenamiento por Inserción Directa
void ordenarInsercionDirecta(int* arreglo, int tamano) {
    for (int i = 1; i < tamano; ++i) {
        int valorActual = arreglo[i];
        int j = i - 1;
        // Desplazar elementos mayores que valorActual hacia la derecha
        while (j >= 0 && arreglo[j] > valorActual) {
            arreglo[j + 1] = arreglo[j];
            j--;
        }
        // Insertar valorActual en su posición correcta
        arreglo[j + 1] = valorActual;
    }
}
Características
  • Eficiencia Temporal: O(N^2) en el peor y caso promedio, pero O(N) si el arreglo está casi ordenado.
  • Eficiencia Espacial: O(1), ya que solo requiere una pequeña cantidad de espacio adicional.
  • Estabilidad: Es un algoritmo estable.

2.2 Ordenamiento Shell (Inserción con Incremento Decreciente)

El ordenaimento Shell es una mejora del ordenamiento por inserción directa. Permite intercambiar elementos que están lejos, reduciendo el número de comparaciones y movimientos necesarios en las etapas finales.

Principio Algorítmico

Utiliza una secuencia de "brechas" (gap) que se van reduciendo. Inicialmente, ordena sublistas de elementos espaciados por gap (pre-ordenamiento). A medida que gap disminuye, el arreglo se vuelve más ordenado. La última brecha siempre es 1, lo que equivale a un ordenamiento por inserción directa sobre un arreglo ya casi ordenado, siendo muy eficiente.

Implementación en C
void ordenarShell(int* arreglo, int tamano) {
    int brecha = tamano;
    while (brecha > 1) {
        // Reducir la brecha, por ejemplo, con la secuencia Knuth (gap = gap / 3 + 1)
        brecha = brecha / 3 + 1;
        for (int i = brecha; i < tamano; ++i) {
            int valorActual = arreglo[i];
            int j = i - brecha;
            // Realizar una inserción con la brecha actual
            while (j >= 0 && arreglo[j] > valorActual) {
                arreglo[j + brecha] = arreglo[j];
                j -= brecha;
            }
            arreglo[j + brecha] = valorActual;
        }
    }
}
Características
  • Optimización: Mejora el ordenamiento por inserción directa.
  • Eficiencia Temporal: Es complejo de calcular y depende de la secuencia de brechas. Comúnmente se cita entre O(N log N) y O(N^(3/2)).
  • Eficiencia Espacial: O(1).
  • Estabilidad: Inestable, ya que elementos iguales pueden cambiar su orden relativo durante las fases de pre-ordenamiento con brechas grandes.

3. Ordenamiento por Selección

3.1 Ordenamiento por Selección Directa

Este método es intuitivo, pero su rendimiento no es óptimo.

Principio Algorítmico

En cada iteración, se busca el elemento más pequeño (o más grande) en la parte no ordenada del arreglo y se intercambia con el primer elemento de esa sección no ordenada. Este proceso se repite hasta que todo el arreglo está ordenado.

Implementación en C (versión optimizada con dos punteros)

Una mejora es encontrar tanto el mínimo como el máximo en cada pasada para colocarlos en sus posiciones extremas, reduciendo las pasadas a la mitad.

void ordenarSeleccionDirecta(int* arreglo, int tamano) {
    for (int i = 0, j = tamano - 1; i < j; ++i, --j) {
        int indiceMin = i;
        int indiceMax = i;
        for (int k = i + 1; k <= j; ++k) {
            if (arreglo[k] < arreglo[indiceMin]) {
                indiceMin = k;
            }
            if (arreglo[k] > arreglo[indiceMax]) {
                indiceMax = k;
            }
        }
        
        // Colocar el mínimo en la posición 'i'
        intercambiar(&arreglo[indiceMin], &arreglo[i]);

        // Si el máximo estaba en la posición original de 'i',
        // su nueva posición es 'indiceMin' después del intercambio
        if (indiceMax == i) {
            indiceMax = indiceMin;
        }
        
        // Colocar el máximo en la posición 'j'
        intercambiar(&arreglo[indiceMax], &arreglo[j]);
    }
}
Características
  • Eficiencia Temporal: O(N^2) en todos los casos.
  • Eficiencia Espacial: O(1).
  • Estabilidad: Inestable.

3.2 Ordenamiento por Montículos (Heap Sort)

El ordenamiento por montículos es otra forma de ordenamiento por selección, pero mucho más eficiente gracias a la estructura de datos de montículo.

Principio Algorítmico

Consiste en construir un montículo (heap) con los elementos del arreglo. Para ordenar ascendentemente, se construye un montículo máximo. El elemento más grande (la raíz del montículo) se extrae y se coloca al final del arreglo, y el montículo se reajusta. Este proceso se repite hasta que todos los elementos están en su lugar.

Implementación en C
// Función para reajustar el montículo (heapify)
void ajustarMonticuloAbajo(int* arreglo, int tamano, int indicePadre) {
    int indiceHijo = 2 * indicePadre + 1; // Hijo izquierdo
    while (indiceHijo < tamano) {
        // Determinar el hijo más grande
        if (indiceHijo + 1 < tamano && arreglo[indiceHijo + 1] > arreglo[indiceHijo]) {
            indiceHijo++;
        }
        // Si el padre es menor que el hijo más grande, intercambiar
        if (arreglo[indicePadre] < arreglo[indiceHijo]) {
            intercambiar(&arreglo[indicePadre], &arreglo[indiceHijo]);
            indicePadre = indiceHijo;
            indiceHijo = 2 * indicePadre + 1;
        } else {
            break; // El montículo está en orden
        }
    }
}

// Ordenamiento por Montículos
void ordenarMonticulos(int* arreglo, int tamano) {
    // Construir un montículo máximo (heapify desde el último nodo no hoja)
    for (int i = (tamano / 2) - 1; i >= 0; --i) {
        ajustarMonticuloAbajo(arreglo, tamano, i);
    }

    // Extraer elementos del montículo uno por uno
    for (int i = tamano - 1; i > 0; --i) {
        intercambiar(&arreglo[0], &arreglo[i]); // Mover la raíz (máximo) al final
        ajustarMonticuloAbajo(arreglo, i, 0); // Reajustar el montículo con el tamaño reducido
    }
}
Características
  • Eficiencia Temporal: O(N log N) en todos los casos.
  • Eficiencia Espacial: O(1).
  • Estabilidad: Inestable.

4. Ordenamiento por Intercambio

Los algoritmos de ordenamiento por intercambio reordenan los elementos comparando pares y permutando su posición si están en el orden incorrecto.

4.1 Ordenamiento de Burbuja (Bubble Sort)

Uno de los algoritmos más simples de entender.

Principio Algorítmico

Compara elemenots adyacentes y los intercambia si están en el orden incorrecto. Repite este proceso, haciendo "flotar" los elementos más grandes (o más pequeños) a su posición final en cada pasada. El recorrido se detiene cuando no se realizan más intercambios en una pasada.

Implementación en C (con optimización)
void ordenarBurbuja(int* arreglo, int tamano) {
    int intercambiado;
    for (int i = 0; i < tamano - 1; ++i) {
        intercambiado = 0; // Bandera para detectar si hubo intercambios
        for (int j = 0; j < tamano - 1 - i; ++j) {
            if (arreglo[j] > arreglo[j + 1]) {
                intercambiar(&arreglo[j], &arreglo[j + 1]);
                intercambiado = 1; // Se realizó un intercambio
            }
        }
        // Si no hubo intercambios en esta pasada, el arreglo ya está ordenado
        if (intercambiado == 0) {
            break;
        }
    }
}
Características
  • Eficiencia Temporal: O(N^2) en el peor y caso promedio. O(N) en el mejor caso (cuando el arreglo ya está ordenado).
  • Eficiencia Espacial: O(1).
  • Estabilidad: Estable.

4.2 Ordenamiento Rápido (Quick Sort) - Recursivo

Inventado por Tony Hoare, es uno de los algoritmos de ordenamiento más rápidos y ampliamente utilizados en la práctica.

Principio Algorítmico

Es un algoritmo de "divide y vencerás". Selecciona un elemento del arreglo 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 dos subarreglos hasta que el arreglo completo esté ordenado.

Métodos de Partición

Existen varias estrategias para la partición:

  1. Esquema Hoare: Mantiene dos punteros, uno desde la izquierda y otro desde la derecha, moviéndolos hacia el centro e intercambiando elementos hasta que se cruzan.
  2. Esquema Lomuto (Método del Pivote Hueco): Mantiene una "posición hueca" y va rellenándola con elementos adecuados, creando nuevos huecos.
  3. Esquema de dos Punteros (Front-Back Pointers): Un puntero para el final de los elementos "menores" y otro para recorrer el arreglo.
Selección del Pivote (Optimización: Mediana de Tres)

Elegir un buen pivote es crucial. Un pivote subóptimo (ej. el primer o último elemento de un arreglo ya ordenado) puede llevar al peor caso de O(N^2). La "mediana de tres" selecciona el pivote como la mediana de los elementos en el inicio, el medio y el final del subarreglo, reduciendo la probabilidad de casos extremos.

// Función auxiliar para encontrar el índice del pivote usando la mediana de tres
int obtenerIndiceMedianaDeTres(int* arreglo, int izq, int der) {
    int centro = izq + (der - izq) / 2;
    if (arreglo[izq] > arreglo[centro]) {
        intercambiar(&arreglo[izq], &arreglo[centro]);
    }
    if (arreglo[izq] > arreglo[der]) {
        intercambiar(&arreglo[izq], &arreglo[der]);
    }
    if (arreglo[centro] > arreglo[der]) {
        intercambiar(&arreglo[centro], &arreglo[der]);
    }
    return centro; // Devuelve el índice del valor que es la mediana
}
Implementación en C (Esquema Lomuto con Mediana de Tres)
// Partición usando el esquema Lomuto (Método del Pivote Hueco)
int particionLomuto(int* arreglo, int izq, int der) {
    int indicePivote = obtenerIndiceMedianaDeTres(arreglo, izq, der);
    intercambiar(&arreglo[indicePivote], &arreglo[izq]); // Mover el pivote al inicio
    int valorPivote = arreglo[izq];
    int indiceHueco = izq; // La posición del pivote es ahora un "hueco"

    while (izq < der) {
        // Buscar desde la derecha un elemento menor que el pivote
        while (izq < der && arreglo[der] >= valorPivote) {
            der--;
        }
        // Si se encuentra, moverlo al hueco y actualizar la posición del hueco
        if (izq < der) {
            arreglo[indiceHueco] = arreglo[der];
            indiceHueco = der;
        }

        // Buscar desde la izquierda un elemento mayor que el pivote
        while (izq < der && arreglo[izq] <= valorPivote) {
            izq++;
        }
        // Si se encuentra, moverlo al hueco y actualizar la posición del hueco
        if (izq < der) {
            arreglo[indiceHueco] = arreglo[izq];
            indiceHueco = izq;
        }
    }
    arreglo[indiceHueco] = valorPivote; // Colocar el pivote en su posición final
    return indiceHueco; // Devolver el índice del pivote
}

// Ordenamiento Rápido Recursivo
void quickSortRecursivo(int* arreglo, int inicio, int fin) {
    if (inicio >= fin) {
        return; // Caso base: subarreglo de 0 o 1 elemento ya ordenado
    }

    // Optimización: para subarreglos pequeños, usar inserción directa
    if (fin - inicio + 1 < 10) { // Umbral de ejemplo: 10 elementos
        ordenarInsercionDirecta(arreglo + inicio, fin - inicio + 1);
        return;
    }

    int indicePivote = particionLomuto(arreglo, inicio, fin);
    quickSortRecursivo(arreglo, inicio, indicePivote - 1); // Ordenar subarreglo izquierdo
    quickSortRecursivo(arreglo, indicePivote + 1, fin);   // Ordenar subarreglo derecho
}

4.3 Ordenamiento Rápido (Quick Sort) - No Recursivo

Aunque la versión recursiva es elegante, puede causar desbordamiento de pila con entradas muy grandes o casi ordenadas. Una implementación no recursiva utiliza una pila explícita para gestionar los rangos de subarreglos a ordenar.

Estructura de Pila para Quick Sort No Recursivo

Necesitamos una implementación básica de pila para almacenar los límites de los subarreglos (inicio y fin).

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h> // Para 'bool'

typedef int ElementoPila;

typedef struct {
    ElementoPila* datos;
    int cima;
    int capacidad;
} PilaRangos;

void inicializarPila(PilaRangos* p) {
    p->datos = (ElementoPila*)malloc(sizeof(ElementoPila) * 4);
    if (!p->datos) {
        perror("Error al asignar memoria para la pila");
        exit(EXIT_FAILURE);
    }
    p->capacidad = 4;
    p->cima = 0;
}

void destruirPila(PilaRangos* p) {
    free(p->datos);
    p->datos = NULL;
    p->capacidad = 0;
    p->cima = 0;
}

void apilar(PilaRangos* p, ElementoPila valor) {
    if (p->cima == p->capacidad) {
        p->capacidad *= 2;
        p->datos = (ElementoPila*)realloc(p->datos, sizeof(ElementoPila) * p->capacidad);
        if (!p->datos) {
            perror("Error al reasignar memoria para la pila");
            exit(EXIT_FAILURE);
        }
    }
    p->datos[p->cima++] = valor;
}

ElementoPila desapilar(PilaRangos* p) {
    if (p->cima == 0) {
        fprintf(stderr, "Error: la pila está vacía.\n");
        exit(EXIT_FAILURE);
    }
    return p->datos[--p->cima];
}

bool estaVacia(PilaRangos* p) {
    return p->cima == 0;
}
Implementación en C
// Ordenamiento Rápido No Recursivo
void quickSortNoRecursivo(int* arreglo, int inicio, int fin) {
    PilaRangos pila;
    inicializarPila(&pila);

    // Apilar el rango inicial del arreglo
    apilar(&pila, inicio);
    apilar(&pila, fin);

    while (!estaVacia(&pila)) {
        // Desapilar los límites del subarreglo (fin, luego inicio)
        int limiteSuperior = desapilar(&pila);
        int limiteInferior = desapilar(&pila);

        // Realizar la partición
        int indicePivote = particionLomuto(arreglo, limiteInferior, limiteSuperior);

        // Si hay subarreglo derecho, apilar sus límites
        if (indicePivote + 1 < limiteSuperior) {
            apilar(&pila, indicePivote + 1);
            apilar(&pila, limiteSuperior);
        }

        // Si hay subarreglo izquierdo, apilar sus límites
        if (limiteInferior < indicePivote - 1) {
            apilar(&pila, limiteInferior);
            apilar(&pila, indicePivote - 1);
        }
    }
    destruirPila(&pila);
}
Características del Ordenamiento Rápido
  • Eficiencia Temporal: O(N log N) en el caso promedio, O(N^2) en el peor caso (mitigado con la selección de pivote).
  • Eficiencia Espacial: O(log N) en el caso promedio (debido a la profundidad de la recursión/pila), O(N) en el peor caso.
  • Estabilidad: Inestable.

5. Ordenamiento por Fusión (Merge Sort)

El ordenamiento por fusión es un algoritmo eficiente basado en el principio de "divide y vencerás".

5.1 Versión Recursiva

Principio Algorítmico

Divide el arreglo por la mitad repetidamente hasta obtener subarreglos de un solo elemento (que se consideran ordenados). Luego, fusiona estos subarreglos de forma recursiva, combinando dos subarreglos ordenados en uno solo más grande y también ordenado, hasta que se reconstruye el arreglo original completo y ordenado.

Implementación en C
// Función auxiliar para fusionar dos subarreglos ordenados
void fusionarSubarreglos(int* arreglo, int inicio, int medio, int fin, int* auxiliar) {
    int i = inicio;      // Puntero para el primer subarreglo [inicio...medio]
    int j = medio + 1;   // Puntero para el segundo subarreglo [medio+1...fin]
    int k = inicio;      // Puntero para el arreglo auxiliar

    // Fusionar elementos de ambos subarreglos en el arreglo auxiliar
    while (i <= medio && j <= fin) {
        if (arreglo[i] <= arreglo[j]) {
            auxiliar[k++] = arreglo[i++];
        } else {
            auxiliar[k++] = arreglo[j++];
        }
    }

    // Copiar los elementos restantes del primer subarreglo (si los hay)
    while (i <= medio) {
        auxiliar[k++] = arreglo[i++];
    }

    // Copiar los elementos restantes del segundo subarreglo (si los hay)
    while (j <= fin) {
        auxiliar[k++] = arreglo[j++];
    }

    // Copiar los elementos ordenados del auxiliar de vuelta al arreglo original
    for (i = inicio; i <= fin; ++i) {
        arreglo[i] = auxiliar[i];
    }
}

// Función recursiva principal para Merge Sort
void _ordenarFusionRecursivo(int* arreglo, int inicio, int fin, int* auxiliar) {
    if (inicio >= fin) {
        return; // Caso base: subarreglo de 0 o 1 elemento
    }

    int medio = inicio + (fin - inicio) / 2;
    _ordenarFusionRecursivo(arreglo, inicio, medio, auxiliar);        // Ordenar mitad izquierda
    _ordenarFusionRecursivo(arreglo, medio + 1, fin, auxiliar);    // Ordenar mitad derecha
    fusionarSubarreglos(arreglo, inicio, medio, fin, auxiliar);    // Fusionar las dos mitades
}

// Ordenamiento por Fusión Recursivo
void ordenarFusionRecursivo(int* arreglo, int tamano) {
    int* auxiliar = (int*)malloc(sizeof(int) * tamano);
    if (!auxiliar) {
        perror("Error al asignar memoria para el arreglo auxiliar");
        exit(EXIT_FAILURE);
    }
    _ordenarFusionRecursivo(arreglo, 0, tamano - 1, auxiliar);
    free(auxiliar);
}

5.2 Versión No Recursiva

Principio Algorítmico

En lugar de dividir recursivamente, la versión no recursiva fusiona subarreglos de tamaño creciente. Comienza fusionando pares de elementos adyacentes, luego pares de subarreglos de 2 elementos, luego de 4, y así sucesivamente, hasta que todo el arreglo está fusionado.

Implementación en C
void ordenarFusionNoRecursivo(int* arreglo, int tamano) {
    int* auxiliar = (int*)malloc(sizeof(int) * tamano);
    if (!auxiliar) {
        perror("Error al asignar memoria para el arreglo auxiliar");
        exit(EXIT_FAILURE);
    }

    // `tamanoBloque` controla el tamaño de los subarreglos a fusionar
    for (int tamanoBloque = 1; tamanoBloque < tamano; tamanoBloque *= 2) {
        // `i` recorre el arreglo, marcando el inicio del primer subarreglo de cada par
        for (int i = 0; i < tamano; i += 2 * tamanoBloque) {
            int inicio1 = i;
            int fin1 = i + tamanoBloque - 1;
            int inicio2 = i + tamanoBloque;
            int fin2 = i + 2 * tamanoBloque - 1;

            // Ajustar límites si exceden el tamaño del arreglo
            if (fin1 >= tamano) break; // Primer bloque ya fuera de límites o es el último
            if (inicio2 >= tamano) { // Segundo bloque no existe o es parcial
                // Solo necesitamos copiar el primer bloque al auxiliar si no es el último
                // y luego de nuevo al original si está en una posición distinta
                int k = inicio1;
                while (inicio1 <= fin1) {
                    auxiliar[k++] = arreglo[inicio1++];
                }
                for (k = i; k <= fin1; ++k) {
                    arreglo[k] = auxiliar[k];
                }
                break; // No hay segundo bloque para fusionar
            }
            if (fin2 >= tamano) fin2 = tamano - 1; // Segundo bloque parcial

            // Fusionar los dos subarreglos
            int k = inicio1; // Puntero para el arreglo auxiliar
            int p1 = inicio1;
            int p2 = inicio2;

            while (p1 <= fin1 && p2 <= fin2) {
                if (arreglo[p1] <= arreglo[p2]) {
                    auxiliar[k++] = arreglo[p1++];
                } else {
                    auxiliar[k++] = arreglo[p2++];
                }
            }
            while (p1 <= fin1) {
                auxiliar[k++] = arreglo[p1++];
            }
            while (p2 <= fin2) {
                auxiliar[k++] = arreglo[p2++];
            }
            // Copiar del auxiliar de vuelta al arreglo original
            for (k = i; k <= fin2; ++k) {
                arreglo[k] = auxiliar[k];
            }
        }
    }
    free(auxiliar);
}
Características del Ordenamiento por Fusión
  • Eficiencia Temporal: O(N log N) en todos los casos (mejor, promedio, peor).
  • Eficiencia Espacial: O(N) debido al arreglo auxiliar necesario para la fusión.
  • Estabilidad: Estable.

6. Ordenamiento por Conteo (Counting Sort) - No Comparativo

A diferencia de los algoritmos anteriores que se basan en comparaciones, el ordenamiento por conteo es un algoritmo no comparativo, lo que le permite ser más rápido bajo ciertas condiciones.

Principio Algorítmico

Se basa en la idea de que, para cada elemento de entrada, se cuenta cuántos elementos son menores o iguales a él. Con esta información, el elemanto puede ser colocado directamente en su posición final en el arreglo de salida.

Optimización con Mapeo Relativo: Si los datos tienen un rango amplio pero son relativamente densos (ej. números entre 1000 y 1050), podemos encontrar el valor mínimo (minVal) y máximo (maxVal). El arreglo de conteo se dimensiona con maxVal - minVal + 1 elementos, y cada número x se mapea a la posición x - minVal en el arreglo de conteo. Esto ahorra memoria significativa.

Implementación en C
void ordenarConteo(int* arreglo, int tamano) {
    if (tamano <= 1) return;

    // 1. Encontrar el valor mínimo y máximo para determinar el rango
    int minVal = arreglo[0];
    int maxVal = arreglo[0];
    for (int i = 1; i < tamano; ++i) {
        if (arreglo[i] < minVal) minVal = arreglo[i];
        if (arreglo[i] > maxVal) maxVal = arreglo[i];
    }

    int rango = maxVal - minVal + 1;

    // 2. Crear un arreglo de conteo y inicializarlo a cero
    int* conteo = (int*)calloc(rango, sizeof(int)); // calloc inicializa a 0
    if (!conteo) {
        perror("Error al asignar memoria para el arreglo de conteo");
        exit(EXIT_FAILURE);
    }

    // 3. Contar la frecuencia de cada elemento en el arreglo original
    for (int i = 0; i < tamano; ++i) {
        conteo[arreglo[i] - minVal]++;
    }

    // 4. Reconstruir el arreglo ordenado
    int indiceActual = 0;
    for (int i = 0; i < rango; ++i) {
        while (conteo[i] > 0) {
            arreglo[indiceActual++] = i + minVal;
            conteo[i]--;
        }
    }

    // 5. Liberar la memoria del arreglo de conteo
    free(conteo);
}
Características del Ordenamiento por Conteo
  • Eficiencia Temporal: O(N + R), donde N es el número de elementos y R es el rango de los valores (max - min + 1).
  • Eficiencia Espacial: O(R).
  • Estabilidad: Es estable si se implementa cuidadosamente (como en el método de acumulación de frecuencias y recorrido inverso para colocar elementos), aunque la implementación directa mostrada aquí es estable si se insertan en el orden correcto.

7. Comparativa de Rendimiento

La eficiencia de los algoritmos de ordenamiento varía significativamente. Los algoritmos con complejidad O(N log N) generalmente superan a los de O(N^2) para grandes conjuntos de datos.

Por ejemplo, en pruebas con un millón de elementos enteros aleatorios en C, los tiempos de ejecución típicos (en milisegundos) muestran una clara diferencia:

  • Ordenamiento por Inserción Directa: Muy lento (varios miles de ms o más).
  • Ordenamiento de Burbuja: Similar al de inserción, muy lento.
  • Ordenamiento por Selección Directa: También muy lento.
  • Ordenamiento Shell: Significativamente más rápido que los O(N^2) (cientos de ms).
  • Ordenamiento por Montículos (Heap Sort): Rápido (decenas de ms).
  • Ordenamiento por Fusión (Merge Sort): Muy rápido (decenas de ms).
  • Ordenamiento Rápido (Quick Sort): Generalmente el más rápido en la práctica (unos pocos ms).
  • Ordenamiento por Conteo: Extremadamente rápido si el rango es pequeño (menos de un ms), pero su rendimiento depende fuertemente del rango de los datos.

8. Resumen de Complejidad y Estabilidad

Aquí se presenta una tabla comparativa de los algoritmos discutidos:

Algoritmo Complejidad Temporal (Mejor) Complejidad Temporal (Promedio) Complejidad Temporal (Peor) Complejidad Espacial Estabilidad
Inserción Directa O(N) O(N^2) O(N^2) O(1) Sí
Shell Sort O(N log^2 N) o O(N log N) Depende de la secuencia de brechas O(N^2) (peor caso poco común) O(1) No
Selección Directa O(N^2) O(N^2) O(N^2) O(1) No
Heap Sort O(N log N) O(N log N) O(N log N) O(1) No
Bubble Sort O(N) O(N^2) O(N^2) O(1) Sí
Quick Sort O(N log N) O(N log N) O(N^2) O(log N) No
Merge Sort O(N log N) O(N log N) O(N log N) O(N) Sí
Counting Sort O(N + R) O(N + R) O(N + R) O(R) Sí

Etiquetas: algoritmos-ordenamiento quick-sort merge-sort heap-sort insertion-sort

Publicado el 6-7 05:58

Etiquetas populares

©2026 Friki Work