Quick Sort es el algoritmo de ordenamiento más rápido en la práctica. Funciona eligiendo un pivote, particionando el arreglo en menores y mayores, luego recursando en cada lado.

Su O(n log n) promedio y excelente localidad de caché lo hacen el favorito de las bibliotecas estándar (C++ std::sort, Java Arrays.sort()). El peor caso O(n²) es raro con pivotes aleatorios o mediana-de-3.

Cómo Funciona

1. Elige un pivote (primer elemento, aleatorio, mediana-de-3).
2. Particiona el arreglo: mueve todos los elementos menores al pivote a la izquierda, todos los mayores a la derecha.
3. Coloca el pivote en su posición final (el índice de partición).
4. Recursa en los subarreglos izquierdo y derecho.

Idea Clave

El pivote determina todo. Si eliges un pivote bueno (cercano a la mediana), divides el problema por la mitad y obtienes O(n log n). Si eliges un pivote terrible (siempre el mínimo o máximo), degeneras a O(n²).

En la práctica, el peor caso casi nunca ocurre: pivotes aleatorios o mediana-de-3 evitan entradas degeneradas. Además, Quick Sort es in-place y tiene excelente localidad de caché, por lo que constantemente supera a Merge Sort.

Ejemplo Trabajado

Ordena [8, 3, 5, 1, 7, 2, 6, 4] con pivote = último elemento:

Partición 1 (pivote=4):

• “Menores: 3, 1, 2 → [3, 1, 2, 4, ...]”
• “Mayores: 8, 5, 7, 6 → [..., 4, 8, 5, 7, 6]”
• Pivote 4 en posición 3

Izquierda [3, 1, 2] (pivote=2):

• “Menores: 1 → [1, 2, 3]”

Derecha [8, 5, 7, 6] (pivote=6):

• “Menores: 5 → [5, 6, 8, 7]”
• Luego [5, 6, 7, 8]

Resultado: [1, 2, 3, 4, 5, 6, 7, 8]. Observa el visualizador mostrar particiones y el árbol de recursión.

Casos Extremos y Trampas

• “Arreglo ya ordenado — peor caso con pivote=primer/último elemento: O(n²). Solución: pivote aleatorio.”
• Muchos duplicados — partición de Lomuto (< y >) se degrada. Usar 3-way partition (Dutch National Flag).
• “Estabilidad — Quick Sort típico es inestable: intercambios durante la partición cambian el orden relativo.”
• “Stack overflow — recursión en O(n) niveles con pivote terrible. Solución: recursar primero en el lado más pequeño.”

Comparación con Merge Sort

Aplicaciones

• Bibliotecas estándar — C++, Java, Python (para objetos primitivos)
• Ordenamiento general — cuando no necesitas estabilidad y quieres velocidad
• Big data — in-place, bajo overhead de memoria
• Enseñanza — ejemplo clásico de divide y vencerás con trade-offs

Trayectoria de Práctica

1. Implementa QuickSort con partición de Lomuto; traza en [5, 2, 4, 6, 1, 3].
2. Cambia a pivote aleatorio; compara comportamiento en arreglo ordenado.
3. Implementa 3-way partition y prueba en [3, 1, 3, 2, 3, 1].
4. Explica por qué QuickSort es in-place pero requiere O(log n) stack.
5. Investiga Introsort: ¿cómo combina QuickSort + HeapSort para evitar O(n²)?