Algoritmos Esenciales de Programación: Búsqueda, Ordenación y Manipulación de Matrices

1. Búsqueda Binaria (Algoritmo Recursivo)

La búsqueda binaria es un método eficiente para localizar un elemento dentro de un contenedor ordenado.

int busquedaBinaria(const vector<int>& L, int ini, int fin, int x) {
    // CASO BASE: Si los índices se cruzan, el elemento no existe
    if (ini > fin) return -1; 

    int mitad = ini + (fin - ini) / 2;

    // ¡ENCONTRADO!
    if (L[mitad] == x) {
        return mitad; 
    }
    
    // ⚠️ ZONA DE CAMBIO: Si la lista estuviera ordenada de MAYOR a MENOR, invierte el '<' por '>'
    if (x < L[mitad]) {
        // Buscar en la sección izquierda
        return busquedaBinaria(L, ini, mitad - 1, x);
    } else {
        // Buscar en la sección derecha
        return busquedaBinaria(L, mitad + 1, fin, x);
    }
}

2. Encontrar el Máximo (Divide y Vencerás)

Este algoritmo utiliza la técnica de Divide y Vencerás para fragmentar el problema en subproblemas más pequeños hasta hallar el valor máximo.

int encontrarMaximoDyV(const vector<int>& L, int ini, int fin) {
    // CASO BASE: Si solo queda un elemento, ese es el máximo de ese trozo
    if (ini == fin) return L[ini]; 

    int mitad = ini + (fin - ini) / 2;

    // DIVIDE Y VENCERÁS
    int maxIzq = encontrarMaximoDyV(L, ini, mitad);     // Mitad izquierda
    int maxDer = encontrarMaximoDyV(L, mitad + 1, fin); // Mitad derecha

    // ⚠️ ZONA DE CAMBIO: Si se solicita el MÍNIMO, cambia el '>' por un '<'
    if (maxIzq > maxDer) {
        return maxIzq;
    } else {
        return maxDer;
    }
}

3. Encontrar un Elemento (Lista NO Ordenada - Quickselect)

Algoritmo basado en la partición de Quicksort para hallar el k-ésimo elemento en una lista desordenada de forma eficiente.

int seleccionK_Esimo(vector<int>& L, int k) {
    int ini = 0;
    int fin = L.size() - 1;
    
    // Realiza la primera partición (utiliza la función 'pivotar' de Quicksort)
    int x = pivotar(L, ini, fin); 
    
    // Bucle iterativo para ajustar el rango de búsqueda
    while (k != x) {
        if (x > k) {
            fin = x - 1; // El objetivo está a la izquierda
        } else {
            ini = x + 1; // El objetivo está a la derecha
        }
        x = pivotar(L, ini, fin); // Re-pivotar en la nueva sección
    }
    return L[x]; // Devuelve el elemento final
}

4. Girar una Matriz 90° a la Derecha

Para rotar una matriz cuadrada, se realizan dos pasos fundamentales: transposición e inversión de filas.

void rotarMatriz90Derecha(vector<vector<int>>& matriz) {
    int n = matriz.size();

    // PASO 1: Transponer la matriz (Filas pasan a ser Columnas)
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            swap(matriz[i][j], matriz[j][i]);
        }
    }

    // PASO 2: Invertir cada fila de forma independiente
    // ⚠️ ZONA DE CAMBIO: Si se requiere girar a la IZQUIERDA, se invierten las columnas (o las filas al inicio)
    for (int i = 0; i < n; i++) {
        int inicio = 0;
        int fin = n - 1;
        while (inicio < fin) {
            swap(matriz[i][inicio], matriz[i][fin]);
            inicio++;
            fin--;
        }
    }
}

6. Mergesort (Ordenación por Mezcla)

El Mergesort es un algoritmo de ordenación estable con una complejidad temporal de O(n log n).

Función Auxiliar: Merge

Combina las dos mitades manteniendo el orden establecido.

void merge(vector<int>& L, int ini, int mitad, int fin) {
    int n1 = mitad - ini + 1;
    int n2 = fin - mitad;

    vector<int> izq(n1), der(n2); // Listas auxiliares de memoria

    for (int i = 0; i < n1; i++) izq[i] = L[ini + i];
    for (int j = 0; j < n2; j++) der[j] = L[mitad + 1 + j];

    int i = 0, j = 0, k = ini;
    while (i < n1 && j < n2) {
        // ⚠️ LÍNEA CRÍTICA: Cambia '<=' por '>=' si se requiere orden DESCENDENTE
        if (izq[i] <= der[j]) { 
            L[k] = izq[i];
            i++;
        } else {
            L[k] = der[j];
            j++;
        }
        k++;
    }

    // Vaciar los elementos restantes
    while (i < n1) { L[k] = izq[i]; i++; k++; }
    while (j < n2) { L[k] = der[j]; j++; k++; }
}

Función Principal Recursiva

void mergeSort(vector<int>& L, int ini, int fin) {
    if (ini < fin) { 
        int mitad = ini + (fin - ini) / 2;

        mergeSort(L, ini, mitad);       // Procesar mitad izquierda
        mergeSort(L, mitad + 1, fin);   // Procesar mitad derecha
        merge(L, ini, mitad, fin);      // Combinar resultados
    }
}

7. Quicksort (Ordenación Rápida)

El Quicksort es uno de los algoritmos de ordenación más rápidos en la práctica, basado en la elección de un pivote.

Función Auxiliar: Pivotar

Coloca el pivote en su posición correcta y organiza los elementos menores y mayores a su alrededor.

int pivotar(vector<int>& L, int ini, int fin) {
    int pivote = L[fin]; // Uso del último elemento como pivote estándar
    int i = ini - 1;     

    for (int j = ini; j < fin; j++) {
        // ⚠️ LÍNEA CRÍTICA: Cambia '<' por '>' si se requiere orden DESCENDENTE
        if (L[j] < pivote) { 
            i++;
            swap(L[i], L[j]);
        }
    }
    swap(L[i + 1], L[fin]); // Sitúa el pivote en su posición final real
    return i + 1; // Devuelve el índice del pivote
}

Función Principal Recursiva

void quickSort(vector<int>& L, int ini, int fin) {
    if (ini < fin) {
        int x = pivotar(L, ini, fin); // 'x' es la posición final del pivote

        quickSort(L, ini, x - 1); // Ordenar sección izquierda
        quickSort(L, x + 1, fin); // Ordenar sección derecha
    }
}