QuickSort implementación

Planteamiento del problema

Dado un conjunto desordenado de elementos (números, cadenas u objetos), necesitamos ordenarlos:

• De forma ascendente o descendente
• Con una clave de ordenación personalizada (por ejemplo, ordenar por “edad” en una lista de diccionarios)
• Con buen rendimiento para tamaños grandes y bajo consumo de memoria

Cómo funciona QuickSort (visión de alto nivel)

1. Elegir un pivote de la lista.
2. Particionar los elementos en torno al pivote: menores a la izquierda, mayores a la derecha.
3. Aplicar recursivamente el proceso a las sublistas izquierda y derecha.

La clave del rendimiento está en una buena elección del pivote y en un particionado eficiente. Verás ambas cosas en el código.

Implementación optimizada in-place con particionado Hoare

Esta versión modifica la lista en sitio, minimizando memoria adicional y realizando menos intercambios que el esquema de Lomuto. Incluye:

• Particionado Hoare
• Mediana de tres para pivotear (reduce peores casos)
• Inserción para subarreglos pequeños (mejora cache y rendimiento práctico)

# quicksort_inplace.py
from typing import List, Callable, Optional, TypeVar
import sys
T = TypeVar("T")
def _insertion_sort(a: List[T], lo: int, hi: int, key: Callable[[T], object], reverse: bool) -> None:
    # Ordena a[lo:hi+1] por inserción
    for i in range(lo + 1, hi + 1):
        x = a[i]
        kx = key(x)
        j = i - 1
        if not reverse:
            while j >= lo and key(a[j]) > kx:
                a[j + 1] = a[j]
                j -= 1
        else:
            while j >= lo and key(a[j]) < kx:
                a[j + 1] = a[j]
                j -= 1
        a[j + 1] = x
def _median_of_three(a: List[T], lo: int, mid: int, hi: int, key: Callable[[T], object]) -> int:
    # Retorna el índice de la mediana entre a[lo], a[mid], a[hi]
    trio = [(key(a[lo]), lo), (key(a[mid]), mid), (key(a[hi]), hi)]
    trio.sort(key=lambda x: x[0])
    return trio[1][1]
def _hoare_partition(a: List[T], lo: int, hi: int, key: Callable[[T], object], reverse: bool) -> int:
    # Elige pivote con mediana de tres para reducir peores casos
    mid = (lo + hi) // 2
    p_idx = _median_of_three(a, lo, mid, hi, key)
    pivot_key = key(a[p_idx])
    i, j = lo - 1, hi + 1
    if not reverse:
        while True:
            i += 1
            while key(a[i]) < pivot_key:
                i += 1
            j -= 1
            while key(a[j]) > pivot_key:
                j -= 1
            if i >= j:
                return j
            a[i], a[j] = a[j], a[i]
    else:
        while True:
            i += 1
            while key(a[i]) > pivot_key:
                i += 1
            j -= 1
            while key(a[j]) < pivot_key:
                j -= 1
            if i >= j:
                return j
            a[i], a[j] = a[j], a[i]
def quicksort_inplace(
    a: List[T],
    key: Optional[Callable[[T], object]] = None,
    reverse: bool = False,
    _lo: Optional[int] = None,
    _hi: Optional[int] = None,
    _depth: int = 0
) -> None:
    """
    Ordena la lista 'a' en sitio usando QuickSort (Hoare + mediana de tres).
    - key: función de clave (como en sorted)
    - reverse: True para descendente
    Nota: QuickSort no es estable. Para estabilidad, usa sorted() (Timsort).
    """
    if key is None:
        key = lambda x: x
    lo = 0 if _lo is None else _lo
    hi = len(a) - 1 if _hi is None else _hi
    if lo >= hi:
        return
    # Umbral para usar inserción (optimización práctica)
    INSERTION_THRESHOLD = 16
    if hi - lo + 1 <= INSERTION_THRESHOLD:
        _insertion_sort(a, lo, hi, key, reverse)
        return
    # Partición Hoare: divide y conquista
    p = _hoare_partition(a, lo, hi, key, reverse)
    # Recur en el lado más pequeño primero para limitar profundidad (optimización tail-recursion-like)
    if p - lo < hi - (p + 1):
        quicksort_inplace(a, key, reverse, lo, p, _depth + 1)
        quicksort_inplace(a, key, reverse, p + 1, hi, _depth + 1)
    else:
        quicksort_inplace(a, key, reverse, p + 1, hi, _depth + 1)
        quicksort_inplace(a, key, reverse, lo, p, _depth + 1)
if __name__ == "__main__":
    data = [29, 10, 14, 37, 13, 5, 88, 1, 2, 0, 7]
    quicksort_inplace(data)
    print("Asc:", data)
    quicksort_inplace(data, reverse=True)
    print("Desc:", data)
    # Objetos
    products = [{"sku": "A1", "price": 19.9}, {"sku": "B2", "price": 5.5}, {"sku": "C3", "price": 12.0}]
    quicksort_inplace(products, key=lambda p: p["price"])
    print("Por precio:", products)

Paso a paso: trazado simple

Ejemplo con [8, 3, 5, 4] y pivote 5:

1. Particionar: menores que 5 → [3, 4], iguales [5], mayores [8]
2. Recur izquierda [3,4] → particiona con pivote 4: [3] + [4]
3. Recur derecha [8] → ya ordenada
4. Resultado final: [3, 4, 5, 8]

Rendimiento, complejidad y escalabilidad

Troubleshooting y mejores prácticas

• RecursionError en listas grandes: asegúrate de usar un buen pivote y recurrir primero en el subarreglo más pequeño. Si tu dataset puede generar profundas recursiones, considera una versión iterativa o introsort (cambiar a heapsort al exceder cierta profundidad).
• Tipos heterogéneos: define key para comparar consistentemente. Evita mezclar números con None o tipos no comparables sin normalizar.
• Estabilidad: si necesitas mantener el orden relativo de elementos iguales, usa sorted() que es estable. QuickSort no lo es.
• Micro-optimizaciones: para Python puro, reducir llamadas repetidas a key() en bucles internos mejora el rendimiento (como se ve en el código).
• Pruebas: valida con casos vacíos, repetidos, todos iguales, ya ordenados y reverso-ordenados.

Pruebas rápidas (sanity checks)

# tests_quicksort.py
import random
from quicksort_functional import quicksort
from quicksort_inplace import quicksort_inplace
def is_sorted(a, key=lambda x: x, reverse=False):
    pairs = zip(a, a[1:])
    if not reverse:
        return all(key(x) <= key(y) for x, y in pairs)
    return all(key(x) >= key(y) for x, y in pairs)
def test_random_lists():
    for _ in range(50):
        arr = [random.randint(-1000, 1000) for _ in range(200)]
        expect = sorted(arr)
        got = quicksort(arr)
        assert got == expect
def test_inplace():
    arr = [5, 1, 4, 2, 8, 0, 2, 2]
    quicksort_inplace(arr)
    assert is_sorted(arr)
def test_key_and_reverse():
    items = [{"v": v} for v in [3, 1, 4, 1, 5]]
    out = quicksort(items, key=lambda x: x["v"], reverse=True)
    assert is_sorted(out, key=lambda x: x["v"], reverse=True)

¿Cuándo usar QuickSort y cuándo no?

• Úsalo cuando: necesitas alto rendimiento promedio, bajo uso de memoria y no requieres estabilidad.
• Evítalo cuando: la estabilidad es crítica, trabajas con datos que podrían gatillar peores casos (casi ordenados sin pivote robusto), o si ya puedes usar sorted() de Python que suele ser la mejor opción general.