1. Ordenación por Inserción

Este método construye una secuencia ordenada incrementalmente al insertar cada elemento en su posición correcta.

1.1 Inserción Directa

Algoritmo básico que compara y desplaza elementos para encontrar la ubicación adecuada.

#include <stdio.h>

void ordenarPorInsercion(int vector[], int longitud) {
    for (int i = 1; i < longitud; i++) {
        int clave = vector[i];
        int j = i - 1;
        while (j >= 0 && vector[j] > clave) {
            vector[j + 1] = vector[j];
            j--;
        }
        vector[j + 1] = clave;
    }
}

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

int main() {
    int datos[] = {49, 38, 65, 97, 76, 13, 27, 49};
    int tam = sizeof(datos) / sizeof(datos[0]);
    ordenarPorInsercion(datos, tam);
    mostrarArreglo(datos, tam);
    return 0;
}

• Complejidad espacial: O(1)
• Complejidad temporal: O(n^2) en promedio y peor caso.
• Estable: No altera el orden relativo de elementos iguales.

1.2 Inserción Binaria

Mejora la inserción directa usando búsqueda binaria para localizar la posición de inserción.

void insercionBinaria(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int valor = arr[i];
        int izquierda = 0, derecha = i - 1;
        while (izquierda <= derecha) {
            int medio = (izquierda + derecha) / 2;
            if (arr[medio] > valor)
                derecha = medio - 1;
            else
                izquierda = medio + 1;
        }
        for (int j = i - 1; j >= izquierda; j--)
            arr[j + 1] = arr[j];
        arr[izquierda] = valor;
    }
}

• Complejidad temporal: O(n^2), pero con menos comparaciones que la inserción directa.

1.3 Ordenación de Shell

Utiliza secuencias de incrementos para ordenar sublistas separadas, acercando los elementos a su posición final.

void shellSort(int arr[], int n) {
    for (int brecha = n / 2; brecha > 0; brecha /= 2) {
        for (int i = brecha; i < n; i++) {
            int temp = arr[i];
            int j;
            for (j = i; j >= brecha && arr[j - brecha] > temp; j -= brecha)
                arr[j] = arr[j - brecha];
            arr[j] = temp;
        }
    }
}

• Complejidad temporal: Aproximadamente O(n^1.3), con peor caso O(n^2).
• No estable: Puede cambiar el orden de elementos idénticos.

2. Ordenación por Intercambio

Basado en intercambiar elementos mal ubicados hasta que la secuencia esté ordenada.

2.1 Burbuja

Compara pares adyacentes y los intercambia si están en orden incorrecto.

void burbuja(int vector[], int tam) {
    int intercambiado;
    for (int i = 0; i < tam - 1; i++) {
        intercambiado = 0;
        for (int j = 0; j < tam - i - 1; j++) {
            if (vector[j] > vector[j + 1]) {
                int temp = vector[j];
                vector[j] = vector[j + 1];
                vector[j + 1] = temp;
                intercambiado = 1;
            }
        }
        if (!intercambiado) break;
    }
}

• Complejidad temporal: O(n^2).
• Estable: Preserva el orden de elementos iguales.

2.2 Quicksort

Selecciona un pivote y particiona el arreglo en elementos menores y mayores, luego ordena recursivamente.

int particionar(int arr[], int inicio, int fin) {
    int pivote = arr[inicio];
    while (inicio < fin) {
        while (inicio < fin && arr[fin] >= pivote) fin--;
        arr[inicio] = arr[fin];
        while (inicio < fin && arr[inicio] <= pivote) inicio++;
        arr[fin] = arr[inicio];
    }
    arr[inicio] = pivote;
    return inicio;
}

void quicksort(int arr[], int inicio, int fin) {
    if (inicio < fin) {
        int pos = particionar(arr, inicio, fin);
        quicksort(arr, inicio, pos - 1);
        quicksort(arr, pos + 1, fin);
    }
}

• Complejidad temporal: Mejor caso O(n log n), peor caso O(n^2).
• No estable: Puede reordenar elementos iguales.
• Eficiente en promedio para grandes conjuntos de datos.

3. Ordenación por Selección

Selecciona el elemento más pequeño (o grande) en cada pasada y lo coloca en su posición correcta.

3.1 Selección Simple

Encuentra el mínimo en la porción no ordenada y lo intecrambia con el primer elemento no ordenado.

void seleccionSimple(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int indiceMin = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[indiceMin])
                indiceMin = j;
        }
        if (indiceMin != i) {
            int temp = arr[i];
            arr[i] = arr[indiceMin];
            arr[indiceMin] = temp;
        }
    }
}

• Complejidad temporal: O(n^2).
• No estable: No garantiza el orden relativo de elemantos iguales.

3.2 Ordenación por Montículos

Utiliza una estructura de montículo para extraer repetidamente el elemento extremo.

3.2.1 Montículo Máximo

El nodo padre es mayor o igual que sus hijos, útil para ordenación ascendente.

void ajustarMaximo(int arr[], int k, int n) {
    int temp = arr[k];
    for (int i = 2*k; i <= n; i *= 2) {
        if (i < n && arr[i] < arr[i+1]) i++;
        if (temp >= arr[i]) break;
        arr[k] = arr[i];
        k = i;
    }
    arr[k] = temp;
}

void construirMonticuloMaximo(int arr[], int n) {
    for (int i = n/2; i > 0; i--)
        ajustarMaximo(arr, i, n);
}

void heapsort(int arr[], int n) {
    construirMonticuloMaximo(arr, n);
    for (int i = n; i > 1; i--) {
        int temp = arr[1];
        arr[1] = arr[i];
        arr[i] = temp;
        ajustarMaximo(arr, 1, i - 1);
    }
}

3.2.2 Montículo Mínimo

El nodo padre es menor o igual que sus hijos, para ordenación descendente.

void ajustarMinimo(int arr[], int k, int n) {
    int temp = arr[k];
    for (int i = 2*k; i <= n; i *= 2) {
        if (i < n && arr[i] > arr[i+1]) i++;
        if (temp <= arr[i]) break;
        arr[k] = arr[i];
        k = i;
    }
    arr[k] = temp;
}

void construirMonticuloMinimo(int arr[], int n) {
    for (int i = n/2; i > 0; i--)
        ajustarMinimo(arr, i, n);
}

• Complejidad temporal: O(n log n).
• No estable: No preserva el orden de elementos iguales.