Ordenamiento Rápido (Quick Sort)

El algoritmo de ordenamiento rápido se basa en la técnica de divide y vencerás. La idea principal consiste en seleccionar un elemento como pivote y reorganizar el array de manera que todos los elementos menores al pivote queden a su izquierda, mientras que los mayores queden a su derecha.

[!NOTA] Concepto fundamental El pivote es el elemento de referencia que permite dividir el array en dos partes. La elección del pivote afecta directamente el rendimiento del algoritmo.

Implementación del Algoritmo

Problema típico: Dado un conjunto de n enteros, ordenarlos de manera ascendente.

**Formato de entrada:**Primera línea: número n (1 <= n <= 100000) Segunda línea: n enteros separados por un espacio

**Formato de salida:**Los números ordenados de menor a mayor, separados por un espacio

Ejemplo de entrada:

5
4 2 1 3 5

Ejemplo de salida:

1 2 3 4 5

#include <iostream>
using namespace std;

int datos[1000000];

void ordenamientoRapido(int inicio, int fin) {
    if (inicio >= fin) return;
    
    int punteroIzquierdo = inicio;
    int punteroDerecho = fin;
    int pivote = datos[inicio];
    
    while (punteroIzquierdo < punteroDerecho) {
        // Buscar desde la derecha un elemento menor o igual al pivote
        while (punteroIzquierdo < punteroDerecho && datos[punteroDerecho] > pivote) {
            punteroDerecho--;
        }
        if (punteroIzquierdo < punteroDerecho) {
            datos[punteroIzquierdo] = datos[punteroDerecho];
        }
        
        // Buscar desde la izquierda un elemento mayor al pivote
        while (punteroIzquierdo < punteroDerecho && datos[punteroIzquierdo] < pivote) {
            punteroIzquierdo++;
        }
        if (punteroIzquierdo < punteroDerecho) {
            datos[punteroDerecho] = datos[punteroIzquierdo];
        }
    }
    
    // Colocar el pivote en su posición final
    datos[punteroIzquierdo] = pivote;
    
    // Aplicar recursión a las particiones
    ordenamientoRapido(inicio, punteroIzquierdo - 1);
    ordenamientoRapido(punteroIzquierdo + 1, fin);
}

int main() {
    int cantidad;
    cin >> cantidad;
    
    for (int idx = 0; idx < cantidad; idx++) {
        cin >> datos[idx];
    }
    
    ordenamientoRapido(0, cantidad - 1);
    
    for (int idx = 0; idx < cantidad; idx++) {
        cout << datos[idx] << " ";
    }
}

Puntos Importantes

Consideraciones clave para la implementación:

1. Elección del pivote: Cuando se selecciona el primer elemento como pivote, es esencial comenzar la búsqueda desde el lado derecho del array. Esto se debe a que necesitamos encontrar un elemento menor al pivote para intercambiarlo.
2. Diferenciación de índices: Mantener clardiad entre:

• Índices del array
• Punteros móviles (izquierdo y derecho)
• Límites inicial y final de la partición

3. Proceso iterativo: El bucle externo while(punteroIzquierdo < punteroDerecho) contiene dos búsquedas internas. La búsqueda desde la derecha siempre debe ejecutarse primero cuando el pivote está en la posición inicial izquierda.
4. Colocación del pivote: Una vez finalizadas las búsquedas, se debe asignar el valor del pivote en la posición donde se encuentran los punteros.
5. Llamadas recursivas: Los límites se actualizan correctamente para evitar procesamientos repetidos y asegurar que cada elemento sea ordenado exactamente una vez.

Análisis de Complejidad Computacional

La eficiencia del algoritmo depende directamente de cómo se realiza la división del array:

• Caso promedio: La complejidad es O(n log n), ya que el pivote divide el array en partes aproximadamente iguales, reduciendo el problema a la mitad en cada nivel de recursión.
• Peor caso: La complejidad degenera a O(n²) cuando el pivote resulta ser siempre el elemento más pequeño o más grande, creando particiones de tamaño muy dispares.

Ampliación: Encontrar el K-ésimo Elemento

Utilizando los principios del ordenamiento rápido, es posible encontrar el k-ésimo elemento más pequeño sin ordenar completamente el array. Esto se logra modificando la función de partición y deteniendo la recursión cuando el pivote ocupa la posición deseada.

Conclusión

El ordenamiento rápido representa una de las técnicas más eficientes para ordenar elementos, ofreciendo un rendimiento promedio excelente. Sin embargo, la elección del pivote y la implementación correcta de la partición son fundamentales para evitar el degradamiento del rendimiento. Comprender thoroughly cómo funciona la partición y el movimiento de los punteros es esencial para dominar este algoritmo.