Algoritmos de ordenamiento

La idea

Ordenar es la operación más estudiada de la informática, porque habilita todo lo demás: buscar, agrupar, detectar duplicados, calcular medianas. Los métodos cuadráticos son los más intuitivos. La burbuja recorre el arreglo intercambiando vecinos desordenados hasta que una pasada completa no produce intercambios. La selección busca el mínimo del tramo pendiente y lo coloca en su sitio: siempre n(n − 1)/2 comparaciones, pero solo n − 1 intercambios. La inserción mantiene un prefijo ordenado e inserta cada elemento nuevo desplazando los mayores; es la mejor de las tres en datos casi ordenados, donde llega a ser O(n).

Los métodos divide y vencerás rompen la barrera cuadrática. El ordenamiento por mezcla parte el arreglo en dos mitades, las ordena recursivamente y las fusiona en una pasada lineal: su recurrencia T(n) = 2T(n/2) + n da O(n log n) garantizado, es estable y necesita memoria auxiliar O(n). El ordenamiento rápido elige un pivote, reparte los elementos en menores y mayores y recurre sobre cada parte; su promedio es O(n log n) con constantes pequeñísimas, aunque un pivote sistemáticamente malo lo degrada a O(n²), riesgo que se controla eligiendo el pivote al azar o por la mediana de tres.

Existe una cota inferior demostrable: cualquier algoritmo que ordene comparando pares necesita al menos log₂(n!) ≈ n log₂ n − 1,44 n comparaciones, porque debe distinguir entre n! ordenaciones posibles y cada comparación aporta un bit. Por eso O(n log n) es óptimo en ese modelo, y solo se puede mejorar con información extra sobre los datos, como hacen el ordenamiento por conteo o por residuos, que llegan a O(n) cuando las claves son enteros en un rango acotado.

Fórmulas clave

• Comparaciones de burbuja y selecciónC(n) = n(n − 1)/2 → O(n²)
• Inserciónmejor caso n − 1, peor y promedio ≈ n²/4 → O(n²)
• Recurrencia de la mezclaT(n) = 2 T(n/2) + n → T(n) = n log₂ n
• Rápido (promedio)T(n) = 2 T(n/2) + n → O(n log n); peor caso O(n²)
• Cota inferior por comparacionesC(n) ≥ log₂(n!) ≈ n log₂ n − 1,44 n
• Inversionesintercambios de burbuja = número de inversiones del arreglo

Dónde se aplica

Las bibliotecas estándar no eligen un solo algoritmo: Timsort (Python y Java) combina inserción sobre tramos cortos con mezclas de secuencias ya ordenadas, y pdqsort (Rust, C++) usa rápido con pivote inteligente y cambia a otro método si detecta degeneración. En bases de datos, ordenar es el paso previo de las uniones por mezcla y de los GROUP BY, y cuando los datos no caben en memoria se usa mezcla externa por bloques en disco. En ciencia de datos, calcular medianas, cuartiles o cajas de dispersión exige ordenar, y en gráficos por computadora se ordenan los polígonos por profundidad antes de dibujar transparencias.

Con programación (Python)

import random

def burbuja(a, c):
    b = list(a)
    for i in range(len(b) - 1):
        for j in range(len(b) - 1 - i):
            c["comp"] += 1
            if b[j] > b[j + 1]:
                b[j], b[j + 1] = b[j + 1], b[j]
                c["inter"] += 1
    return b

def insercion(a, c):
    b = list(a)
    for i in range(1, len(b)):
        v, j = b[i], i - 1
        while j >= 0:
            c["comp"] += 1
            if b[j] <= v:
                break
            b[j + 1] = b[j]; c["inter"] += 1; j -= 1
        b[j + 1] = v
    return b

def mezcla(a, c):
    if len(a) < 2:
        return list(a)
    m = len(a) // 2
    iz, de = mezcla(a[:m], c), mezcla(a[m:], c)
    r, i, j = [], 0, 0
    while i < len(iz) and j < len(de):
        c["comp"] += 1
        if iz[i] <= de[j]:
            r.append(iz[i]); i += 1
        else:
            r.append(de[j]); j += 1
    return r + iz[i:] + de[j:]

datos = [random.randint(1, 999) for _ in range(200)]
for nombre, f in (("burbuja", burbuja), ("insercion", insercion), ("mezcla", mezcla)):
    c = {"comp": 0, "inter": 0}
    res = f(datos, c)
    ok = res == sorted(datos)
    print(f"{nombre:10} comparaciones={c['comp']:6} correcto={ok}")
print("cota n(n-1)/2 =", 200 * 199 // 2, "   n*log2(n) =", round(200 * 7.6439))

La versión en JavaScript, editable y ejecutable en el navegador, está en la página interactiva del tema.

Temas relacionados

Complejidad y notación O grande · Búsqueda binaria · Recursión y memoización · Cuartiles y diagrama de caja