Quicksort en Python — explicado paso a paso (con animación)

Quicksort es el algoritmo de ordenación más famoso del mundo, y también el más malinterpretado. Casi todo el mundo te dirá que es “el algoritmo de ordenación más rápido”. La verdad es más interesante: quicksort puro casi ningún lenguaje moderno lo usa tal cual, porque tiene un peor caso O(n²) catastrófico. Lo que usan los lenguajes son híbridos construidos encima (Introsort en C++, pdqsort en Rust y Go, Dual-Pivot Quicksort en Java para primitivos…).

Eso lo hace todavía más importante de entender, porque la idea central de quicksort es la base de toda la ordenación moderna. Esta entrada cubre el algoritmo en serio: cómo funciona paso a paso, implementación en Python, JavaScript y Java, su complejidad real (mejor, medio y peor caso), por qué el peor caso es tan dañino, y cómo los lenguajes se protegen de él en producción.

Si quieres el panorama de los 14 algoritmos del clúster y la tabla completa de qué algoritmo usa de verdad cada lenguaje: Algoritmos de ordenación en Python — los 14 explicados.

Quicksort en una frase

Elige un pivote. Reparte el resto en dos lados: lo menor que el pivote a la izquierda, lo mayor a la derecha. Coloca el pivote en medio. Repite recursivamente en cada mitad. Cuando no queda nada que partir, la lista está ordenada.

Animación sobre 12 valores con sus contadores en vivo:

Antes de seguir: qué quieren decir O, Θ y Ω

En la tabla de complejidad verás los tres símbolos. Idea rápida:

• O(n²) — “O grande”, cota superior (peor caso).
• Ω(n log n) — “Omega”, cota inferior (mejor caso).
• Θ(n log n) — “Theta”: el caso típico, cuando superior e inferior coinciden.

Quicksort es el ejemplo perfecto de por qué importa la diferencia entre los tres. Su caso medio Θ(n log n) es excelente, pero su peor caso O(n²) es catastrófico. La separación entre ambos es lo que obliga a los lenguajes modernos a usar híbridos. Más detalle en el pilar del clúster.

Cómo funciona — traza paso a paso

Ordenamos [3, 7, 1, 5, 4, 2, 6] a mano. Vamos a usar la variante Lomuto (la más fácil de explicar, la más usada en docencia), eligiendo siempre el último elemento como pivote.

Primera llamada: ordena [3, 7, 1, 5, 4, 2, 6], pivote = 6.
Recorremos todo lo demás separando “menores que 6” (a la izquierda) de “mayores o iguales que 6” (a la derecha):

• 3 < 6 → va a la izquierda.
• 7 ≥ 6 → se queda donde está.
• 1 < 6 → va a la izquierda.
• 5 < 6 → va a la izquierda.
• 4 < 6 → va a la izquierda.
• 2 < 6 → va a la izquierda.

Resultado de la partición: [3, 1, 5, 4, 2, | 6 | 7]. El 6 queda en medio.

Ahora aplicamos quicksort recursivamente a [3, 1, 5, 4, 2] y a [7]. El [7] ya está “ordenado” (un solo elemento).

Sobre [3, 1, 5, 4, 2], pivote = 2:

• 3 ≥ 2.
• 1 < 2.
• 5 ≥ 2.
• 4 ≥ 2.

Partición: [1, | 2 | 3, 5, 4]. Recursión sobre [1] (ya ordenada) y sobre [3, 5, 4].

Sobre [3, 5, 4], pivote = 4:

• 3 < 4.
• 5 ≥ 4.

Partición: [3, | 4 | 5]. Ambas mitades de un elemento → ya ordenadas.

Reconstruimos: [1, 2, 3, 4, 5, 6, 7]. Ordenado.

Lo importante de la traza: cada partición fija un elemento (el pivote) en su posición final. Y el árbol de recursión, idealmente, tiene profundidad log n. Por eso quicksort promedia O(n log n) — cada nivel del árbol hace O(n) trabajo y hay log n niveles.

Implementación en Python (Lomuto, in-place)

def ordenar(lista: list[int], lo: int = 0, hi: int | None = None) -> list[int]:
    if hi is None:
        hi = len(lista) - 1
    if lo < hi:
        # particiona y devuelve el índice donde queda el pivote
        i = lo
        pivote = lista[hi]
        for j in range(lo, hi):
            if lista[j] < pivote:
                lista[i], lista[j] = lista[j], lista[i]
                i += 1
        lista[i], lista[hi] = lista[hi], lista[i]
        # recursión sobre cada mitad
        ordenar(lista, lo, i - 1)
        ordenar(lista, i + 1, hi)
    return lista


if __name__ == "__main__":
    print(ordenar([3, 7, 1, 5, 4, 2, 6]))  # [1, 2, 3, 4, 5, 6, 7]

Tres detalles que distinguen a una implementación seria de una de juguete:

1. In-place. No crea listas nuevas, modifica la original. Eso es lo que mantiene la memoria en O(log n) (solo el stack de recursión).
2. Pivote = último elemento. Es la variante más sencilla. No es la más robusta: si la lista ya está ordenada, hace su peor caso. Para producción se usa “mediana de tres” o pivote aleatorio.
3. Recursión doble. Una llamada por cada mitad. Si el pivote queda en el centro, las dos mitades tienen tamaño n/2 — caso ideal.

En entrevistas, después de implementar quicksort, explica de inmediato su peor caso y cómo mitigarlo (pivote aleatorio o mediana de tres). Demuestra que entiendes los problemas reales, no solo el algoritmo.

Variante “pythónica” funcional (NO uses en producción)

Esta es bonita pero NO es quicksort de verdad — usa O(n) memoria extra por las listas auxiliares:

def quicksort(lista):
    if len(lista) <= 1:
        return lista
    pivote = lista[0]
    menores = [x for x in lista[1:] if x < pivote]
    mayores = [x for x in lista[1:] if x >= pivote]
    return quicksort(menores) + [pivote] + quicksort(mayores)

Sirve para demostrar la idea en una entrevista o tutorial, pero pierde la propiedad in-place de quicksort original. En entrevistas serias, implementa la versión in-place.

Implementación en JavaScript

function ordenar(lista, lo = 0, hi = lista.length - 1) {
  if (lo < hi) {
    let i = lo;
    const pivote = lista[hi];
    for (let j = lo; j < hi; j++) {
      if (lista[j] < pivote) {
        [lista[i], lista[j]] = [lista[j], lista[i]];
        i++;
      }
    }
    [lista[i], lista[hi]] = [lista[hi], lista[i]];
    ordenar(lista, lo, i - 1);
    ordenar(lista, i + 1, hi);
  }
  return lista;
}

console.log(ordenar([3, 7, 1, 5, 4, 2, 6])); // [1, 2, 3, 4, 5, 6, 7]

Implementación en Java

public static void ordenar(int[] lista, int lo, int hi) {
    if (lo < hi) {
        int i = lo;
        int pivote = lista[hi];
        for (int j = lo; j < hi; j++) {
            if (lista[j] < pivote) {
                int tmp = lista[i];
                lista[i] = lista[j];
                lista[j] = tmp;
                i++;
            }
        }
        int tmp = lista[i];
        lista[i] = lista[hi];
        lista[hi] = tmp;
        ordenar(lista, lo, i - 1);
        ordenar(lista, i + 1, hi);
    }
}

public static void ordenar(int[] lista) {
    ordenar(lista, 0, lista.length - 1);
}

Complejidad — el cielo y el infierno de quicksort

El mejor y caso medio O(n log n) aparecen cuando el pivote parte la lista en dos mitades balanceadas. El árbol de recursión tiene profundidad log n, cada nivel hace O(n) trabajo → n log n.

El peor caso O(n²) ocurre cuando el pivote elegido es el menor (o el mayor) de la lista cada vez. Entonces una mitad tiene 0 elementos y la otra n-1, el árbol de recursión se degrada a una cadena de longitud n, y haces n*n trabajo total.

¿Cuándo pasa eso en la práctica? Con la variante Lomuto que elige el último como pivote: si la lista ya está ordenada (ascendente o descendente), entras en el peor caso. Sí, has leído bien: quicksort puro es lentísimo con listas ya ordenadas. Es la cara cruel de elegir mal el pivote.

¿Por qué no es estable? Porque el intercambio durante la partición puede separar elementos iguales. Dos valores idénticos pueden cambiar su orden relativo.

Cómo se protegen los lenguajes del peor caso

Esto es lo que casi nadie cubre claro y es lo más interesante:

• C++ (std::sort) usa Introsort: empieza con quicksort, y si la profundidad de recursión supera 2 · log n (señal de mal pivote), se cambia a heapsort que garantiza O(n log n). En el último nivel, cuando los tramos son pequeños, se pasa a insertion sort. Tres algoritmos cosidos.
• Rust (sort_unstable) y Go (sort.Slice) usan pdqsort (pattern-defeating quicksort): detecta patrones que harían colapsar a quicksort (lista ya ordenada, todos iguales, ascendente/descendente perfecto) y reordena el pivote para romperlos.
• Java (para tipos primitivos como int[]) usa Dual-Pivot Quicksort: en vez de un solo pivote, elige dos. Reparte en tres regiones (menores que P1, entre P1 y P2, mayores que P2). En la práctica reduce comparaciones e intercambios sobre la variante de un pivote.
• Python y Java (objetos) usan Timsort, que NO es quicksort en absoluto — es merge + insertion. Es lo que list.sort() ejecuta cuando llamas a sorted() en Python.

Si te pica el gusanillo: en CPython el algoritmo está implementado en C, en Objects/listobject.c. Busca “TimSort”.

Ver en acción — quicksort sobre 10 listas fijas (y el peor caso DE VERDAD)

Todo el clúster usa las mismas 10 listas fijas (n=15) para cruzar honestamente entre algoritmos:

Aplicamos quicksort (variante Lomuto con pivote = último elemento) sobre las 10:

from sortlab import bench_estandar, formato_tabla
print(formato_tabla(bench_estandar("quick", n=15)))

Salida real:

Lista            Comp.  Interc.  Escr.  Tiempo (ms)   Caso  Θ observada
---------------  -----  -------  -----  -----------  -----  -----------
ordenada         105         14     28        0.009   Peor        Θ(n²)
inversa          105         14     28        0.009   Peor        Θ(n²)
casi_ordenada    96          13     26        0.009   Peor        Θ(n²)
muy_desordenada  47          21     42        0.007  Mejor   Θ(n log n)
duplicados       48          22     44        0.006  Mejor   Θ(n log n)
aleatoria_s1     51          20     40        0.007  Mejor   Θ(n log n)
aleatoria_s2     59          19     38        0.007  Mejor   Θ(n log n)
aleatoria_s3     44          25     50        0.007  Mejor   Θ(n log n)
aleatoria_s4     43          21     42        0.006  Mejor   Θ(n log n)
aleatoria_s5     37          20     40        0.006  Mejor   Θ(n log n)

Esta tabla es la prueba del crimen. Lee con atención:

1. ordenada e inversa → 105 comparaciones, Peor, Θ(n²). Esto es el famoso peor caso de Lomuto en cifras: con listas ya ordenadas (¡el caso más común en producción!) quicksort se degrada a O(n²). Hace exactamente las mismas comparaciones que selection o bubble en inversa. Cero ventaja sobre los O(n²) “tontos”.
2. casi_ordenada → 96, también Peor. La degradación ocurre incluso cuando la lista está casi ordenada. Una traición silenciosa: el peor caso aparece justo donde el programador menos lo espera.
3. muy_desordenada, duplicados, todas las aleatorias → Mejor + Θ(n log n). Entre 37 y 59 comparaciones, claramente en el bucket n log n. Quicksort brilla aquí: la mitad o menos del trabajo de los O(n²).
4. Lectura honesta: quicksort es excelente en el caso medio pero catastrófico justo en los casos más predecibles (ordenada, inversa). Por eso los lenguajes reales lo “protegen” — Introsort, pdqsort, Dual-Pivot QuickSort.

Compara con merge sobre las mismas listas (datos reales de sortlab):

Merge sort hace siempre entre 28 y 43 — su determinismo absoluto. Quick varía entre 37 y 105: cuando va bien, es más rápido; cuando va mal, es 3 veces más lento que merge. Esa es la decisión.

¿Y el escalado a n grande? Sobre aleatoria_s1 (entrada favorable):

Frente a bubble (5,4 segundos para n=10.000), quicksort sobre la misma entrada es 335 veces más rápido. Cuando va bien, va MUY bien.

Reproducirlo sin instalar nada

sortlab vive privado en el Python profesional: medir, optimizar y escalar (con la implementación completa, las protecciones del peor caso —mediana de tres, pivote aleatorio—, y la conexión con Introsort y pdqsort explicada). Para reproducir sin la librería, esta es la versión instrumentada inline:

def quick_medido(lista_original: list[int]) -> dict:
    arr = list(lista_original)
    metricas = {"comparaciones": 0, "intercambios": 0}

    def sort(lo: int, hi: int) -> None:
        if lo >= hi:
            return
        i = lo
        pivote = arr[hi]
        for j in range(lo, hi):
            metricas["comparaciones"] += 1
            if arr[j] < pivote:
                if i != j:
                    arr[i], arr[j] = arr[j], arr[i]
                    metricas["intercambios"] += 1
                i += 1
        arr[i], arr[hi] = arr[hi], arr[i]
        metricas["intercambios"] += 1
        sort(lo, i - 1)
        sort(i + 1, hi)

    if arr:
        sort(0, len(arr) - 1)
    return {"ordenada": arr, **metricas}


listas = {
    "ordenada":         list(range(1, 16)),
    "inversa":          list(range(15, 0, -1)),
    "casi_ordenada":    [1, 11, 3, 4, 5, 6, 7, 8, 9, 10, 2, 12, 13, 14, 15],
    "muy_desordenada":  [1, 15, 2, 14, 3, 13, 4, 12, 5, 11, 6, 10, 7, 9, 8],
    "duplicados":       [1, 1, 3, 2, 2, 2, 1, 5, 1, 5, 4, 1, 1, 1, 2],
}
for nombre, lista in listas.items():
    r = quick_medido(lista)
    print(f"{nombre:<16}  comp={r['comparaciones']:>3}  swap={r['intercambios']:>3}")

Verás: ordenada e inversa con 105 comparaciones (el peor caso); las otras con ~40-50. Cuadra con la tabla de sortlab.

Mitos que circulan sobre quicksort

• “Quicksort es el algoritmo más rápido del mundo.” En el caso medio, sí, casi siempre. En el peor caso es O(n²), tan lento como bubble. Lo importante es decir “más rápido en el caso medio” para ser preciso.
• “Python usa quicksort.” Falso. Python usa Timsort. Y JavaScript también. Java usa quicksort solo para tipos primitivos (la variante Dual-Pivot). Para objetos, también Timsort.
• “Quicksort es estable.” No lo es. El intercambio durante la partición puede separar elementos iguales. Si necesitas estabilidad, usa merge sort.
• “Quicksort siempre usa O(log n) memoria.” Es el caso medio. En el peor caso, el stack de recursión llega a O(n). Por eso Introsort impone un límite a la profundidad.

¿Y en la stdlib de Python?

Sí pero no. No tienes quicksort() en la stdlib. Lo que tienes es list.sort() y sorted(), que ejecutan Timsort (más sofisticado y estable). En módulos como heapq o bisect tampoco verás quicksort. Si quieres quicksort puro, te lo implementas tú — y entonces es buena idea preguntarte si realmente lo necesitas, porque casi nunca es la respuesta correcta sobre sorted().

Trivia algorítmica

Quicksort lo inventó Tony Hoare en 1959 mientras intentaba implementar un programa de traducción automática del ruso al inglés en la Universidad de Moscú. Necesitaba ordenar palabras para hacer lookup en un diccionario, y diseñó el algoritmo en su cabeza durante una noche de insomnio. Lo publicó dos años después y se convirtió en uno de los algoritmos más enseñados de la historia. Hoare ganó el Turing Award en 1980, entre otras razones, por esto.

Cuándo usar quicksort (puro)

Sí:

• Como ejercicio para entender el patrón divide-y-vencerás. Es uno de los algoritmos más enseñables del mundo.
• Cuando implementas tu propio sort y quieres una base sólida sobre la que añadir las mitigaciones (pivote aleatorio, mediana de tres, fallback a heapsort).

No:

• Si tienes sorted() o Arrays.sort() disponibles. Es prácticamente seguro que el algoritmo nativo de tu lenguaje (Timsort, Introsort, pdqsort, Dual-Pivot) es mejor opción que tu quicksort casero.

Comparativa rápida

Dónde encaja quicksort dentro del clúster:

La lectura correcta: quicksort puro es incompleto. Su idea (divide-y-vencerás con pivote) es brillante, pero necesita protecciones contra el peor caso. Las versiones de producción que usan Rust, Go, C++ no son quicksort — son híbridos que llevan quicksort dentro.

FAQ rápida

¿Quicksort es el algoritmo más rápido?
En el caso medio sí, casi siempre. En el peor caso es O(n²), tan lento como bubble. Por eso los lenguajes reales lo combinan con heapsort o lo refuerzan con pdqsort.

¿Es recursivo o iterativo?
Naturalmente recursivo. Se puede convertir a iterativo usando una pila explícita, lo cual a veces se hace para evitar overflow del stack con listas muy grandes.

¿Por qué elegir el último como pivote es mala idea?
Porque hace su peor caso con listas ya ordenadas (algo muy frecuente en producción). Mejor pivote aleatorio o mediana de tres (primer, medio y último elemento → coge el mediano).

¿Qué es la “mediana de tres”?
Coger el primer, el del medio y el último elemento del tramo, y usar la mediana de esos tres como pivote. Reduce las probabilidades del peor caso a casi cero en la práctica.

¿Quicksort es estable?
No. El intercambio durante la partición puede separar elementos iguales. Existen variantes “stable quicksort” pero a costa de memoria extra (deja de ser in-place).

En resumen

Quicksort es el algoritmo más enseñado del mundo y, paradójicamente, el menos usado en su forma pura. Su idea (divide y vencerás con pivote) es la base de las ordenaciones modernas, pero su talón de Aquiles (peor caso O(n²)) obliga a combinarlo con otros para producción. Entenderlo bien es entender por qué los lenguajes hacen lo que hacen.

Si quieres aprender a medir el rendimiento real de tu código y elegir bien la estructura para cada problema, ese es el camino del curso de El Pythonista.