¿Qué es Quicksort?

Quicksort es un algoritmo de ordenación de tipo divide y vencerás creado por Tony Hoare en 1960. Su popularidad proviene de su rendimiento práctico superior a otros algoritmos de ordenación comparativa, a pesar de que su complejidad peor‑caso es O(n²). En la práctica, con una buena estrategia de pivote, alcanza O(n log n) en promedio.

Complejidad Temporal y Espacial

• Mejor caso: O(n log n) (pivote siempre divide la lista en mitades).
• Promedio: O(n log n) con pivote aleatorio o mediana de tres.
• Peor caso: O(n²) (lista ya ordenada y pivote malo).
• Espacio adicional: O(log n) (recursión de pila), o O(n) si se usa la versión iterativa con pila explícita.

Implementación Básica en Python (Partición Lomuto)

def quicksort_lomuto(arr):
    """Ordena una lista usando el método de partición Lomuto."""
    def _quicksort(low, high):
        if low < high:
            p = partition(low, high)
            _quicksort(low, p - 1)
            _quicksort(p + 1, high)
    def partition(low, high):
        pivot = arr[high]               # pivote = último elemento
        i = low - 1
        for j in range(low, high):
            if arr[j] <= pivot:
                i += 1
                arr[i], arr[j] = arr[j], arr[i]
        arr[i + 1], arr[high] = arr[high], arr[i + 1]
        return i + 1
    _quicksort(0, len(arr) - 1)
    return arr
# Ejemplo de uso
lista = [33, 10, 55, 71, 29, 3, 18]
print(quicksort_lomuto(lista))

Esta versión es sencilla y se usa frecuentemente en material didáctico. Sin embargo, la partición Hoare suele ser más eficiente en la práctica.

Versión Hoare (más rápida y menos swaps)

def quicksort_hoare(arr):
    """Ordena una lista usando la partición de Hoare."""
    def _quicksort(low, high):
        if low < high:
            p = partition(low, high)
            _quicksort(low, p)
            _quicksort(p + 1, high)
    def partition(low, high):
        pivot = arr[(low + high) // 2]   # pivote = elemento medio
        i = low - 1
        j = high + 1
        while True:
            i += 1
            while arr[i] < pivot:
                i += 1
            j -= 1
            while arr[j] > pivot:
                j -= 1
            if i >= j:
                return j
            arr[i], arr[j] = arr[j], arr[i]
    _quicksort(0, len(arr) - 1)
    return arr
# Ejemplo de uso
lista = [33, 10, 55, 71, 29, 3, 18]
print(quicksort_hoare(lista))

Observa cómo el pivote se elige como el elemento central y la partición devuelve el índice j que separa los sub‑arreglos.

Mejores Prácticas y Optimización

• Elección del pivote: usa mediana de tres (primer, medio y último) o pivote aleatorio para evitar el peor caso.
• Ordenar sub‑arreglos pequeños con inserción: cuando la longitud n <= 10, cambia a insertion sort para reducir la sobrecarga de recursión.
• Recursión en cola: convierte la llamada recursiva al sub‑arreglo más grande en un bucle while para limitar la profundidad de pila a O(log n).
• Versión iterativa: utiliza una pila explícita (lista) para gestionar los rangos y evitar overflow de la pila de Python.

import random
def quicksort_optimized(arr):
    def median_of_three(low, high):
        mid = (low + high) // 2
        a, b, c = arr[low], arr[mid], arr[high]
        if a > b:
            a, b = b, a
        if b > c:
            b, c = c, b
        if a > b:
            a, b = b, a
        return b
    def partition(low, high):
        pivot = median_of_three(low, high)
        i = low - 1
        j = high + 1
        while True:
            i += 1
            while arr[i] < pivot:
                i += 1
            j -= 1
            while arr[j] > pivot:
                j -= 1
            if i >= j:
                return j
            arr[i], arr[j] = arr[j], arr[i]
    def _quicksort(low, high):
        while low < high:
            if high - low < 10:
                # Insertion sort para sub‑arreglo pequeño
                for i in range(low + 1, high + 1):
                    key = arr[i]
                    j = i - 1
                    while j >= low and arr[j] > key:
                        arr[j + 1] = arr[j]
                        j -= 1
                    arr[j + 1] = key
                break
            else:
                p = partition(low, high)
                # Recursión en el sub‑arreglo más pequeño
                if p - low < high - p:
                    _quicksort(low, p)
                    low = p + 1
                else:
                    _quicksort(p + 1, high)
                    high = p
    _quicksort(0, len(arr) - 1)
    return arr

Esta versión combina mediana de tres, inserción para particiones pequeñas y recursión en cola, logrando un rendimiento cercano al de la librería estándar list.sort() en la mayoría de los casos.

Comparativa Rápida: Quicksort vs. Mergesort vs. Heapsort

Problemas Comunes y Soluciones

• Recursión profunda en listas casi ordenadas: habilita sys.setrecursionlimit() o usa la versión iterativa.
• Rendimiento inesperadamente bajo: verifica que el pivote no sea siempre el primer o último elemento; usa aleatorización.
• Ordenación inestable: si necesitas estabilidad, reemplaza Quicksort por sorted() o implementa una variante estable (p.ej., stable quicksort con índices auxiliares).

Conclusión

Quicksort sigue siendo una herramienta esencial en el arsenal del desarrollador por su rendimiento promedio y baja sobrecarga de memoria. Con las optimizaciones modernas (pivote aleatorio, mediana de tres, inserción para sub‑arreglos pequeños) su comportamiento se acerca al de los algoritmos de biblioteca estándar. Sin embargo, es importante conocer sus limitaciones y cuándo preferir alternativas como mergesort o heapsort.