Implementación y Fundamentos de Algoritmos Clave: Recursividad, Ordenación y Búsqueda

Conceptos Fundamentales de Algoritmia

Algoritmo de la Torre de Hanoi

La Torre de Hanoi es un ejemplo clásico de recursividad y la estrategia de Divide y Vencerás.

Implementación Conceptual de Hanoi

hanoi(origen, destino, auxiliar, int n) {
    if (n == 0) return;
    hanoi(origen, auxiliar, destino, n - 1);
    mover(origen, destino);
    hanoi(auxiliar, origen, destino, n - 1);
}

Recursividad

Un algoritmo recursivo es aquel que expresa la solución de un problema en términos de una llamada a sí mismo. Esta llamada se conoce como llamada recursiva o recurrente. La recursividad es una técnica de programación importante que se utiliza para realizar una llamada a una función desde la misma función.

Como ejemplo útil se puede presentar el cálculo de números factoriales. El factorial de 0 es, por definición, 1. Los factoriales de números mayores se calculan mediante la multiplicación de 1 * 2 * ..., incrementando el número de 1 en 1 hasta llegar al número para el que se está calculando el factorial.

Propiedades de las Definiciones o Algoritmos Recursivos

Un requisito importante para que un algoritmo recursivo sea correcto es que no genere una secuencia infinita de llamadas a sí mismo. Cualquier algoritmo que genere tal secuencia no terminará nunca.

• Una función recursiva f debe definirse en términos que no impliquen a f al menos en un argumento o grupo de argumentos.
• Debe existir una "salida" de la secuencia de llamadas recursivas. Si no existe esta salida, no puede calcularse ninguna función recursiva.
• Cualquier caso de definición recursiva o invocación de un algoritmo recursivo tiene que reducirse a la larga a alguna manipulación de uno o más casos simples no recursivos.

Estrategia Divide y Vencerás

Se dice que un objeto es recursivo si en parte está formado por sí mismo o se define en función de sí mismo. (Fórmula matemática: P = P[S, P]).

La estrategia Divide y Vencerás consiste en:

1. Dividir: El problema se divide en subproblemas de complejidad similar e inferior al original, hasta reducir el problema a un caso trivial.
2. Vencer: La solución al problema original se obtiene mediante la combinación de la solución encontrada a los subproblemas.

Algoritmos de Búsqueda y Ordenación

Búsqueda Binaria (Bipartición)

La búsqueda binaria se realiza en un vector ordenado (requiere de índices). Se busca un valor X en la mitad del sector, y si no es encontrado, se pregunta si es mayor o menor. Luego, se pasa a subdividir los sectores restantes de dicho vector.

Complejidad Temporal: T(n) = log n (o(n) log n).

Implementación de Búsqueda Binaria

int busquedaBinaria (int v[], int clave, int li, int ls) {
    if (ls < li) return -1;
    int mitad = (ls + li) / 2;
    
    if (v[mitad] == clave) {
        return mitad;
    }
    
    if (clave > v[mitad]) {
        return busquedaBinaria(v, clave, mitad + 1, ls);
    } else { 
        return busquedaBinaria(v, clave, li, mitad - 1);
    }
}

Merge Sort (Ordenación por Mezcla)

El algoritmo Merge Sort divide el vector en dos y ordena ambas partes.

Función de Mezcla (Merge)

void merge(int v[], int li1, int ls1, int li2, int ls2) {
    int[] nuevo = new int[ls2 - li1 + 1];
    int m = li1, n = li2;
    
    for (int i = 0; i < (ls2 - li1 + 1); ++i) {
        if (m > ls1) {
            nuevo[i] = v[n];
            n++;
        } else if (n > ls2) {
            nuevo[i] = v[m];
            m++;
        } else if (v[m] > v[n]) {
            nuevo[i] = v[n];
            n++;
        } else {
            nuevo[i] = v[m];
            m++;
        }
    }
    
    for (int i = 0; i < (ls2 - li1 + 1); ++i) {
        v[i + li1] = nuevo[i];
    }
}

Quicksort

El algoritmo Quicksort sigue la estrategia de Divide y Vencerás.

Pasos de Quicksort

• Si la cantidad de elementos (S) es 0 o 1, terminar.
• Sino, seleccionar un pivote V (ver método de selección).
• Partir el conjunto S en dos subconjuntos:
  • S1: Elementos menores a V.
  • S2: Elementos mayores a V.
• Aplicar quicksort(S1).
• Aplicar quicksort(S2).

El pivote queda en su posición final. La condición de fin es cuando queda un elemento solo en el vector.

Implementación de Quicksort

void quicksort(int v[], int Li, int Ls) {
    if (Li < Ls) {
        int pivote = buscarPivote(v, Li, Ls);
        int K = particion(v, Li, Ls, pivote);
        quicksort(v, Li, K - 1); // Se asume que K es la posición final del pivote
        quicksort(v, K + 1, Ls);
    }
}

Comparación de Objetos

Implementación de compareTo

Este método se utiliza para comparar objetos del mismo tipo, generalmente implementando una interfaz de comparación.

Ejemplo de Clase Cliente con compareTo

class Cliente {
    int compareTo(Cliente c) {
        if (this.nombre < c.nombre) {
            return -1;
        } else if (this.nombre > c.nombre) {
            return 1;
        } else {
            return 0;
        }
    }
}