Este artículo analiza varios algoritmos de ordenación fundamentalse, explorando sus implementaciones y optimizaciones. Se presentan funciones auxiliares comunes, seguidas de los algoritmos específicos.

Funciones auxiliares

Una operación frecuente es intercambiar dos valores.

void intercambiar(int *valor_a, int *valor_b) {
    int temporal = *valor_a;
    *valor_a = *valor_b;
    *valor_b = temporal;
}

Para ciertos algoritmos, como QuickSort, es útil obtener la mediana de tres elementos para mejorar la elección del pivote.

int obtenerMediana(int *arreglo, int izquierda, int derecha) {
    int centro = izquierda + (derecha - izquierda) / 2;
    if (arreglo[izquierda] < arreglo[centro]) {
        if (arreglo[centro] < arreglo[derecha]) {
            return centro;
        } else if (arreglo[izquierda] < arreglo[derecha]) {
            return derecha;
        } else {
            return izquierda;
        }
    } else {
        if (arreglo[derecha] < arreglo[centro]) {
            return centro;
        } else if (arreglo[derecha] < arreglo[izquierda]) {
            return derecha;
        } else {
            return izquierda;
        }
    }
}

1. Ordenamiento por inserción

Construye una secuencia ordenada un elemento a la vez. Se itera sobre el arreglo y se inserta cada elemento en su posición correcta dentro de la subsecuencia ya ordenada.

void ordenarPorInsercion(int *arreglo, int cantidad) {
    for (int indice = 1; indice < cantidad; ++indice) {
        int clave = arreglo[indice];
        int j = indice - 1;
        while (j >= 0 && arreglo[j] > clave) {
            arreglo[j + 1] = arreglo[j];
            --j;
        }
        arreglo[j + 1] = clave;
    }
}

2. Ordenamiento de Shell (Shell Sort)

Es una extensión del ordenamiento por inserción. Comienza ordenando elementos muy separados entre sí y reduce progresivamente el intervalo de comparación (el gap). Esto permite que los elementos se muevan grandes distancias en una sola operación, acercando el arreglo al orden antes de la fase final de inserción.

void ordenamientoShell(int *arreglo, int longitud) {
    for (int salto = longitud / 2; salto > 0; salto /= 2) {
        for (int i = salto; i < longitud; i += 1) {
            int temp = arreglo[i];
            int j;
            for (j = i; j >= salto && arreglo[j - salto] > temp; j -= salto) {
                arreglo[j] = arreglo[j - salto];
            }
            arreglo[j] = temp;
        }
    }
}

3. Ordenamiento por selección

Divide el arreglo en dos partes: una ordenada y otra no ordenada. En cada iteración, encuentra el elemento mínimo de la parte no ordenada y lo intercambia con el primer elemento de esa parte.

void ordenarPorSeleccion(int *arreglo, int tamano) {
    for (int i = 0; i < tamano - 1; i++) {
        int indice_min = i;
        for (int j = i + 1; j < tamano; j++) {
            if (arreglo[j] < arreglo[indice_min]) {
                indice_min = j;
            }
        }
        if (indice_min != i) {
            intercambiar(&arreglo[i], &arreglo[indice_min]);
        }
    }
}

4. Quicksort

a. Método clásico (Hoare) - versión recursiva

Selecciona un pivote y particiona el arreglo de manera que los elementos menores al pivote queden a su izquierda y los mayores a su derecha. Luego aplica recursión a las sublistas resultantes.

int particionarHoare(int *arreglo, int bajo, int alto) {
    int pivote = arreglo[bajo];
    int i = bajo - 1;
    int j = alto + 1;
    while (1) {
        do {
            i++;
        } while (arreglo[i] < pivote);
        do {
            j--;
        } while (arreglo[j] > pivote);
        if (i >= j)
            return j;
        intercambiar(&arreglo[i], &arreglo[j]);
    }
}

void quicksortHoare(int *arreglo, int bajo, int alto) {
    if (bajo < alto) {
        int pi = particionarHoare(arreglo, bajo, alto);
        quicksortHoare(arreglo, bajo, pi);
        quicksortHoare(arreglo, pi + 1, alto);
    }
}

b. Método del "hueco" (Dig Hole) - versión recursiva

int particionarHueco(int *arreglo, int bajo, int alto) {
    int pivote = arreglo[bajo];
    while (bajo < alto) {
        while (bajo < alto && arreglo[alto] >= pivote)
            alto--;
        arreglo[bajo] = arreglo[alto];
        while (bajo < alto && arreglo[bajo] <= pivote)
            bajo++;
        arreglo[alto] = arreglo[bajo];
    }
    arreglo[bajo] = pivote;
    return bajo;
}

void quicksortHueco(int *arreglo, int bajo, int alto) {
    if (bajo < alto) {
        int pi = particionarHueco(arreglo, bajo, alto);
        quicksortHueco(arreglo, bajo, pi - 1);
        quicksortHueco(arreglo, pi + 1, alto);
    }
}

c. Método de doble puntero (versión recursiva)

void quicksortDoblePuntero(int *arreglo, int bajo, int alto) {
    if (bajo < alto) {
        int pivote = arreglo[alto];
        int i = bajo - 1;
        for (int j = bajo; j < alto; j++) {
            if (arreglo[j] < pivote) {
                i++;
                intercambiar(&arreglo[i], &arreglo[j]);
            }
        }
        intercambiar(&arreglo[i + 1], &arreglo[alto]);
        int pi = i + 1;
        quicksortDoblePuntero(arreglo, bajo, pi - 1);
        quicksortDoblePuntero(arreglo, pi + 1, alto);
    }
}

d. Versión no recursiva (iterativa)

Utiliza una pila explícita para almacenar los límites de los subarreglos a ordenar, evitando la recursión.

void quicksortNoRecursivo(int *arreglo, int longitud) {
    // Implementación típica usando una pila para almacenar los índices bajo y alto.
    // Se omite el código completo por brevedad, pero sigue el mismo principio de partición.
}

5. Merge Sort (Ordenamiento por mezcla)

a. Versión recursiva

Divide el arreglo repetidamente a la mitad hasta que las sublistas tengan un solo elemento. Luego, fusiona (mezcla) las sublistas ordenadas para producir sublistas ordenadas más grandes hasta que se obtiene el arreglo completo ordenado.

void fusionar(int *arreglo, int izquierda, int medio, int derecha) {
    int n1 = medio - izquierda + 1;
    int n2 = derecha - medio;
    int L[n1], R[n2];
    for (int i = 0; i < n1; i++)
        L[i] = arreglo[izquierda + i];
    for (int j = 0; j < n2; j++)
        R[j] = arreglo[medio + 1 + j];
    int i = 0, j = 0, k = izquierda;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arreglo[k] = L[i];
            i++;
        } else {
            arreglo[k] = R[j];
            j++;
        }
        k++;
    }
    while (i < n1) {
        arreglo[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arreglo[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int *arreglo, int izquierda, int derecha) {
    if (izquierda < derecha) {
        int medio = izquierda + (derecha - izquierda) / 2;
        mergeSort(arreglo, izquierda, medio);
        mergeSort(arreglo, medio + 1, derecha);
        fusionar(arreglo, izquierda, medio, derecha);
    }
}

b. Versión no recursiva (iterativa)

Ordena subarreglos de tamaño creciente (1, 2, 4, 8, ...) fusionando pares de subarreglos adyacentes.

void mergeSortNoRecursivo(int *arreglo, int longitud) {
    for (int tamano_actual = 1; tamano_actual < longitud; tamano_actual *= 2) {
        for (int inicio_izq = 0; inicio_izq < longitud - 1; inicio_izq += 2 * tamano_actual) {
            int medio = min(inicio_izq + tamano_actual - 1, longitud - 1);
            int final_der = min(inicio_izq + 2 * tamano_actual - 1, longitud - 1);
            fusionar(arreglo, inicio_izq, medio, final_der);
        }
    }
}

6. Bubble Sort (Ordenamiento de burbuja)

Itera repetidamente a través del arreglo, compara elementos adyacentes y los intercambia si están en el orden incorrecto. El proceso se repite hasta que no se necesiten más intercambios.

void bubbleSort(int *arreglo, int n) {
    bool intercambiado;
    for (int i = 0; i < n - 1; i++) {
        intercambiado = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (arreglo[j] > arreglo[j + 1]) {
                intercambiar(&arreglo[j], &arreglo[j + 1]);
                intercambiado = true;
            }
        }
        if (!intercambiado)
            break;
    }
}

7. Heap Sort (Ordenamiento por montículo)

Construye un montículo máximo (o mínimo) a partir de los datos, luego extrae repetidamente el elemento raíz (el máximo) para reconstruir el montículo hasta que esté vacío.

void siftDown(int *arreglo, int n, int i) {
    int mayor = i;
    int izquierda = 2 * i + 1;
    int derecha = 2 * i + 2;
    if (izquierda < n && arreglo[izquierda] > arreglo[mayor])
        mayor = izquierda;
    if (derecha < n && arreglo[derecha] > arreglo[mayor])
        mayor = derecha;
    if (mayor != i) {
        intercambiar(&arreglo[i], &arreglo[mayor]);
        siftDown(arreglo, n, mayor);
    }
}

void heapSort(int *arreglo, int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        siftDown(arreglo, n, i);
    for (int i = n - 1; i > 0; i--) {
        intercambiar(&arreglo[0], &arreglo[i]);
        siftDown(arreglo, i, 0);
    }
}

8. Counting Sort (Ordenamiento por conteo)

No es un algoritmo de comparación. Cuenta el número de objetos que tienen valores de clave distintos y usa esas cuentas para determinar las posiciones de cada valor en la secuencia de salida. Es eficiente cuando el rango de valores de entrada (k) no es significativamente mayor que el número de elementos (n).

void countingSort(int *arreglo, int n) {
    if (n == 0) return;
    int max_val = arreglo[0], min_val = arreglo[0];
    for (int i = 1; i < n; i++) {
        if (arreglo[i] > max_val) max_val = arreglo[i];
        if (arreglo[i] < min_val) min_val = arreglo[i];
    }
    int rango = max_val - min_val + 1;
    int *conteo = (int*)calloc(rango, sizeof(int));
    int *salida = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++)
        conteo[arreglo[i] - min_val]++;
    for (int i = 1; i < rango; i++)
        conteo[i] += conteo[i - 1];
    for (int i = n - 1; i >= 0; i--) {
        salida[conteo[arreglo[i] - min_val] - 1] = arreglo[i];
        conteo[arreglo[i] - min_val]--;
    }
    for (int i = 0; i < n; i++)
        arreglo[i] = salida[i];
    free(conteo);
    free(salida);
}

Propiedad de estabilidad

Un algoritmo es estable si mantiene el orden relativo de los registros con claves iguales. Por ejemplo, Merge Sort y Bubble Sort son estables, mientras que QuickSort y Heap Sort no lo son.

Tabla resumen de complejidad