Quicksort es uno de los algoritmos más eficientes y utilizados en la historia de la computación. Su estrategia "Divide y Vencerás" consiste en seleccionar un elemento llamado "pivote" y particionar el arreglo: los menores a la izquierda, los mayores a la derecha.

Imagen 19. Representación del particionado en Quicksort

Esquema del proceso de particionado: observa cómo el pivote busca su posición final definitiva dividiendo el problema en dos sublistas.

5.1 (Parte 1) Quicksort: La lógica del "Divide y Vencerás"

Mirar en YouTube

main.cpp

// Función partición
int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

// Función principal recursiva
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// Función partición
int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

// Función principal recursiva
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

5.1 (Parte 2) Implementando Quicksort en C

Mirar en YouTube

Aunque su promedio es O(n log n), Quicksort puede degradarse a O(n²) si el pivote es malo (ej. lista ya ordenada). Sin embargo, es preferido sobre Merge Sort en muchos casos porque no requiere memoria extra (trabaja "in-place") y tiene constantes muy bajas.

Merge Sort adopta un enfoque más predecible. Divide recursivamente la lista por la mitad hasta tener elementos individuales y luego los "fusiona" (merge) en orden ascendente. Es como barajar dos mazos de cartas ordenados en uno solo.

Imagen 20. Proceso de división y mezcla en Merge Sort

El árbol de llamadas recursivas: primero se divide todo (fase de división) y luego se reconstruye ordenadamente (fase de conquista/mezcla).

5.2 (Parte 1) Merge Sort: Concepto y Recursividad

Mirar en YouTube

main.cpp

// Función para mezclar dos subarreglos
void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    int L[n1], R[n2]; // Arrays auxiliares

    for (int i=0; i<n1; ++i) L[i] = arr[l + i];
    for (int j=0; j<n2; ++j) R[j] = arr[m + 1 + j];

    // Mezcla lógica
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

// Función para mezclar dos subarreglos
void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    int L[n1], R[n2]; // Arrays auxiliares

    for (int i=0; i<n1; ++i) L[i] = arr[l + i];
    for (int j=0; j<n2; ++j) R[j] = arr[m + 1 + j];

    // Mezcla lógica
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

5.2 (Parte 2) Implementando Merge Sort y arrays auxiliares

Mirar en YouTube

A diferencia de Quicksort, Merge Sort es "estable" (mantiene el orden relativo de iguales) y garantiza O(n log n) incluso en el peor caso. Su desventaja es el coste espacial O(n) por los arreglos auxiliares, pero es ideal para ordenar listas enlazadas o datos externos.

Heap Sort utiliza una estructura llamada "Montículo Binario" (Binary Heap). Aunque conceptualmente es un árbol binario completo, se almacena eficientemente en un arreglo lineal sin usar punteros, calculando la posición de los hijos mediante aritmética de índices.

5.3 (Parte 1) Heap Sort: ¿Cómo ver un Árbol en un Arreglo?

Mirar en YouTube

Imagen 21. Representación de un Heap en memoria contigua

Esquema de índices: Observa cómo el elemento en la posición 0 es la raíz, y sus hijos se distribuyen matemáticamente en el arreglo.

main.cpp

// Función para mantener la propiedad de montículo (Max-Heap)
void heapify(int arr[], int n, int i) {
    int largest = i;   // Inicializar el más grande como raíz
    int l = 2 * i + 1; // Izquierda
    int r = 2 * i + 2; // Derecha

    // Si el hijo izquierdo es mayor que la raíz
    if (l < n && arr[l] > arr[largest])
        largest = l;

    // Si el hijo derecho es mayor que el más grande actual
    if (r < n && arr[r] > arr[largest])
        largest = r;

    // Si el más grande no es la raíz
    if (largest != i) {
        swap(&arr[i], &arr[largest]);
        // Recursivamente hacer heapify en el subárbol afectado
        heapify(arr, n, largest);
    }
}

// Función para mantener la propiedad de montículo (Max-Heap)
void heapify(int arr[], int n, int i) {
    int largest = i;   // Inicializar el más grande como raíz
    int l = 2 * i + 1; // Izquierda
    int r = 2 * i + 2; // Derecha

    // Si el hijo izquierdo es mayor que la raíz
    if (l < n && arr[l] > arr[largest])
        largest = l;

    // Si el hijo derecho es mayor que el más grande actual
    if (r < n && arr[r] > arr[largest])
        largest = r;

    // Si el más grande no es la raíz
    if (largest != i) {
        swap(&arr[i], &arr[largest]);
        // Recursivamente hacer heapify en el subárbol afectado
        heapify(arr, n, largest);
    }
}

5.3 (Parte 2) Heap Sort: Heapify y Ordenamiento

Mirar en YouTube

Una vez que tenemos los datos ordenados (gracias a Quicksort o Mergesort), podemos dejar de usar la búsqueda lineal O(n). La Búsqueda Binaria reduce el espacio de búsqueda a la mitad en cada paso, logrando una velocidad logarítmica O(log n).

Imagen 22. Búsqueda Lineal vs Búsqueda Binaria

Comparativa visual: Mientras la búsqueda lineal revisa uno por uno, la binaria descarta la mitad de los datos instantáneamente.

main.cpp

int binarySearch(int arr[], int l, int r, int x) {
    while (l <= r) {
        int m = l + (r - l) / 2;

        // Verificar si x está presente en el medio
        if (arr[m] == x) 
            return m;

        // Si x es mayor, ignorar la mitad izquierda
        if (arr[m] < x) 
            l = m + 1;

        // Si x es menor, ignorar la mitad derecha
        else 
            r = m - 1;
    }
    // Si llegamos aquí, el elemento no estaba presente
    return -1;
}

int binarySearch(int arr[], int l, int r, int x) {
    while (l <= r) {
        int m = l + (r - l) / 2;

        // Verificar si x está presente en el medio
        if (arr[m] == x) 
            return m;

        // Si x es mayor, ignorar la mitad izquierda
        if (arr[m] < x) 
            l = m + 1;

        // Si x es menor, ignorar la mitad derecha
        else 
            r = m - 1;
    }
    // Si llegamos aquí, el elemento no estaba presente
    return -1;
}

5.4 Búsqueda Binaria: O(log n)

Mirar en YouTube

Hemos analizado algoritmos básicos O(n²) como Bubble Sort y avanzados O(n log n) como Quicksort. La diferencia teórica es enorme, pero en la práctica intervienen factores como el caché del procesador, la estabilidad y la memoria disponible.

5.5 El "Torneo" de Algoritmos: Comparativa Final

Mirar en YouTube

Resumen Rápido: - Quicksort: El más rápido generalmente, pero inestable y O(n²) en peor caso. - Merge Sort: Estable y seguro O(n log n), pero usa mucha memoria. - Heap Sort: Seguro O(n log n) y bajo uso de memoria, pero más lento que Quicksort por la falta de localidad de referencia. - Bubble/Insertion: Solo útiles para listas minúsculas (n < 50).

Estructuras de Datos

Ordenamiento Eficiente

Quicksort

Merge Sort

Heap Sort

Búsqueda binaria

Comparativa teórica y experimental