Quicksort (ordenamiento rápido): cómo funciona, código y complejidad

La idea en palabras sencillas

1. Elige un elemento pivote, por ejemplo el último elemento o uno aleatorio.
2. Partición: mueve a su izquierda todos los elementos menores que el pivote y a su derecha todos los mayores. El pivote queda ya en su posición final ordenada.
3. Ordena de forma recursiva la parte a la izquierda del pivote y la parte a su derecha. Después no hace falta combinar nada.

Merge sort divide con facilidad y mezcla con dificultad. Quicksort es lo contrario: la partición hace el trabajo y unir las mitades no cuesta nada, porque ya están en el lugar correcto dentro del mismo arreglo.

Ejemplo resuelto: una partición de Lomuto

Particiona [10, 80, 30, 90, 40, 50, 70] con el último elemento, 70, como pivote. El índice i marca el final de la región de elementos menores que el pivote; j recorre de izquierda a derecha.

70 queda ahora en el índice 4, su posición final. Después quicksort ordena [10, 30, 40, 50] y [90, 80] por separado.

Implementación en Python

import random

def partition(a, lo, hi):
    """Lomuto partition of a[lo..hi] around a random pivot."""
    r = random.randint(lo, hi)
    a[r], a[hi] = a[hi], a[r]       # move the pivot to the end
    pivot = a[hi]
    i = lo - 1
    for j in range(lo, hi):
        if a[j] < pivot:
            i += 1
            a[i], a[j] = a[j], a[i]
    a[i + 1], a[hi] = a[hi], a[i + 1]
    return i + 1

def quicksort(a, lo=0, hi=None):
    """Sort list a in place."""
    if hi is None:
        hi = len(a) - 1
    while lo < hi:
        p = partition(a, lo, hi)
        if p - lo < hi - p:           # recurse on the smaller side
            quicksort(a, lo, p - 1)
            lo = p + 1
        else:
            quicksort(a, p + 1, hi)
            hi = p - 1
    return a

print(quicksort([10, 80, 30, 90, 40, 50, 70]))   # [10, 30, 40, 50, 70, 80, 90]
print(quicksort([3, 3, 3, 1]))                   # [1, 3, 3, 3]

Recursar sobre el lado más pequeño y iterar sobre el más grande mantiene la profundidad de la pila en O(log n) incluso en el peor caso. Una versión corta, no in situ, es popular para explicar la idea, pero reserva listas nuevas en cada nivel:

def quicksort_simple(items):
    if len(items) <= 1:
        return items
    pivot = items[len(items) // 2]
    less = [x for x in items if x < pivot]
    equal = [x for x in items if x == pivot]
    greater = [x for x in items if x > pivot]
    return quicksort_simple(less) + equal + quicksort_simple(greater)

print(quicksort_simple([5, 2, 9, 2, 7]))   # [2, 2, 5, 7, 9]

Complejidad temporal y espacial

El peor caso clásico es un pivote fijo en el primer o el último elemento con una entrada ya ordenada o en orden inverso: cada partición elimina solo el pivote, lo que da n niveles de O(n) de trabajo. Un pivote aleatorio hace esto extremadamente improbable con cualquier entrada.

Cómo se compara quicksort con otros ordenamientos

Quicksort no es estable: un intercambio de la partición puede mover un elemento más allá de otro igual. Normalmente supera a merge sort y a heapsort con arreglos en memoria porque su bucle interno es simple, trabaja in situ y accede a la memoria sobre todo de forma secuencial. Introsort, usado por muchas implementaciones de std::sort en la biblioteca estándar de C++, empieza con quicksort y cambia a heapsort si la recursión se hace demasiado profunda, lo que garantiza O(n log n).

Elección del pivote, variantes y errores comunes

• Elección del pivote: primer o último elemento (simple, pero O(n²) con entradas ordenadas), elemento aleatorio o mediana de tres (primero, central y último).
• Partición de Hoare: dos índices avanzan uno hacia el otro e intercambian los pares que están en el lado equivocado. Hace menos intercambios que Lomuto en promedio.
• Partición en tres vías (bandera nacional holandesa): separa en menores, iguales y mayores. Hace rápidos los arreglos con muchas claves duplicadas; Lomuto simple se degrada a O(n²) cuando todas las claves son iguales.
• Dual-pivot quicksort usa dos pivotes y tres partes; Java lo emplea para ordenar arreglos de tipos primitivos.
• Quickselect usa una sola partición y recursa solo en un lado para encontrar el k-ésimo elemento menor en tiempo promedio O(n).

Cuándo usar quicksort

Quicksort es una buena opción por defecto para ordenar arreglos en memoria cuando no se necesita estabilidad. En Python, usa mejor sorted() o list.sort(); emplean Timsort, que es estable y rápido con datos parcialmente ordenados. Implementar quicksort es una tarea de entrevista muy común, a menudo seguida de preguntas sobre el peor caso, la elección del pivote, la estabilidad o el uso de quickselect para encontrar el k-ésimo elemento mayor.