Ordenamientos elementales: burbuja, inserción, selección

Qué cubre este capítulo

Ordenar es el problema más estudiado de la computación, y empieza justo aquí, con tres ordenamientos tan simples que los puedes escribir de memoria: burbuja, selección e inserción. Los tres son O(n²), lo que suena a pretexto para saltárselos, pero hay dos razones para dedicarles un capítulo. Primero, son la línea base contra la que se miden los ordenamientos rápidos, así que no puedes apreciar O(n log n) sin antes sentir O(n²). Segundo, uno de ellos —el ordenamiento por inserción— sí sirve de verdad: es casi lineal en datos casi ordenados y vive dentro del sort de la librería estándar. En este capítulo construimos los tres y los echamos a correr contra Timsort.

Un poco de historia

Ordenar es tan viejo como el procesamiento de datos: las clasificadoras mecánicas de tarjetas ya corrían versiones de estos algoritmos antes de que existieran las computadoras electrónicas. Los nombres son casi puro folclor; "bubble sort" aparece impreso desde 1962, aunque la técnica es más antigua. Lo que cristalizó el campo fue el volumen de 1973 de Donald Knuth, "Sorting and Searching", que analizó estos y decenas más con un rigor que convirtió al ordenamiento en el ejemplo canónico para enseñar análisis de algoritmos, que es exactamente el papel que juega en este libro. Y los ordenamientos elementales no son puro dato histórico: en 2002 Tim Peters diseñó Timsort para Python combinando merge sort con ordenamiento por inserción, porque inserción es imbatible en los pedazos chicos y casi ordenados en los que se parten los datos reales. El ordenamiento más viejo del capítulo es una pieza viva del más nuevo.

La intuición

Cada uno de los tres tiene una idea de una sola frase. El ordenamiento burbuja recorre el array intercambiando pares adyacentes que estén desordenados; después de cada pasada, el elemento más grande sin ordenar "burbujeó" hasta su lugar al final. El ordenamiento por selección encuentra el elemento más chico de la parte sin ordenar y lo intercambia al frente, y luego repite con el resto. El ordenamiento por inserción hace crecer un prefijo ordenado a la izquierda: toma el siguiente elemento y lo desliza hacia atrás pasando todo lo que sea más grande, hasta dejarlo en su lugar, igual que cuando acomodas una mano de cartas.

Los tres son O(n²) porque cada uno hace como n pasadas con como n trabajo por pasada, pero difieren en temperamento. Selección siempre hace las n² comparaciones completas incluso con entrada ya ordenada, pero solo n intercambios. Burbuja puede salirse antes si una pasada no encuentra nada que intercambiar. E inserción hace el menor trabajo cuando los datos ya están cerca de estar ordenados, porque cada elemento casi no tiene que moverse, que es justo la propiedad que lo hace importante.

Complejidad: cómo escala

Los tres ordenamientos son $O(n^2)$ en promedio y en el peor caso —los ciclos anidados lo delatan, unas $n^2/2$ comparaciones—. Sus mejores casos sí difieren: burbuja e inserción bajan a $O(n)$ con entrada ya ordenada (burbuja por su bandera de salida temprana, inserción porque el ciclo interno nunca corre), mientras que selección se queda en $O(n^2)$ pase lo que pase, porque siempre recorre toda la parte sin ordenar para encontrar el mínimo. Los tres son in-place, con $O(1)$ de espacio extra. La gráfica pone a los tres contra Timsort; los ordenamientos elementales trazan la inconfundible curva ascendente de una cuadrática mientras Timsort se pega al piso:

Con apenas 2000 elementos, el ordenamiento por inserción tardó unos 42 ms contra los 0.08 ms de Timsort —500 veces más lento— y esa razón crece sin límite conforme sube n, porque es una diferencia de clase de complejidad, no una constante. Ese es todo el argumento de los siguientes capítulos.

En qué es bueno y en qué no

Los ordenamientos elementales son la opción correcta en exactamente una situación: arrays chicos o casi ordenados, donde el factor constante bajo y la adaptividad del ordenamiento por inserción le ganan al overhead de un algoritmo más elaborado. Esto no es hipotético: por eso las rutinas de ordenamiento de producción se cambian a inserción cuando un subarray se vuelve chico (normalmente entre 16 y 64 elementos). Además son simples, in-place y (en el caso de inserción y burbuja) estables, o sea que los elementos iguales conservan su orden.

Para cualquier otra cosa —arrays grandes de datos aleatorios— son la herramienta equivocada, sin discusión. O(n²) significa que duplicar la entrada cuadruplica el tiempo, así que pasan de "instantáneo" a "inusable" en un parpadeo. El ordenamiento por selección en particular no tiene ningún mejor caso que lo redima. La regla es simple: usa inserción para lo chico y lo casi ordenado, y un ordenamiento O(n log n) para todo lo demás.

Los datos, o las entradas

El enfrentamiento ordena arrays de enteros aleatorios en tamaños crecientes, para que la curva cuadrática sea imposible de ignorar. Una segunda medición le da al ordenamiento por inserción dos tipos de entrada del mismo tamaño —totalmente aleatoria y casi ordenada— para aislar su adaptividad. Y la animación corre inserción sobre diez elementos, lento como para ver crecer el prefijo ordenado una inserción a la vez.

Constrúyelo, una función a la vez

Ordenamiento burbuja: intercambiar pares adyacentes, pasada tras pasada, con una salida temprana cuando una pasada sale limpia:

def bubble_sort(a):
    """O(n^2): repeatedly walk the array swapping adjacent out-of-order pairs, so
    the largest element 'bubbles' to the end on each pass. The early-exit flag
    makes it O(n) on already-sorted input — a pass with no swaps means done."""
    a = list(a)
    n = len(a)
    for i in range(n):
        swapped = False
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:
            break
    return a

Ordenamiento por selección: encontrar el mínimo del resto e intercambiarlo a su lugar; n intercambios, siempre n² comparaciones:

def selection_sort(a):
    """O(n^2): each pass scans the unsorted part for its minimum and swaps it into
    place. It does only n swaps (good when writes are expensive) but always n^2/2
    comparisons — there's no early exit, sorted input costs the same as random."""
    a = list(a)
    n = len(a)
    for i in range(n):
        lo = i
        for j in range(i + 1, n):
            if a[j] < a[lo]:
                lo = j
        a[i], a[lo] = a[lo], a[i]
    return a

Ordenamiento por inserción —el importante— hace crecer un prefijo ordenado desplazando cada nuevo elemento hasta su lugar:

def insertion_sort(a, probe=None):
    """O(n^2) worst, O(n) best: grow a sorted prefix by taking each next element
    and shifting it left past everything larger, into its slot. On nearly-sorted
    data every element barely moves, so it's close to linear — which is why it's
    the sort of choice for small or almost-ordered arrays."""
    a = list(a)
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]                 # shift the larger element right
            j -= 1
            if probe is not None:
                probe.append({"arr": list(a), "key_pos": j + 1, "sorted_to": i})
        a[j + 1] = key                      # drop the key into its place
        if probe is not None:
            probe.append({"arr": list(a), "key_pos": j + 1, "sorted_to": i})
    return a

Míralo funcionar

Aquí está el ordenamiento por inserción sobre diez barras. Azul es el prefijo ordenado, naranja es el elemento que se está insertando en ese momento, gris es la cola que todavía no se toca. Ve paso a paso y observa cómo la región azul crece desde la izquierda un elemento a la vez: cada frame toma la primera barra gris y la desliza a la izquierda a través de la región azul hasta dejarla en orden. Con esta entrada aleatoria hace bastante desplazamiento, pero imagina las barras ya casi ordenadas y verías cada barra naranja caer casi directo en su lugar, casi sin movimiento. Esa diferencia es la adaptividad:

El código completo

Las dos versiones en un solo lugar; cambia entre ellas. La pestaña "desde cero" tiene los tres ordenamientos elementales. La de librería es sorted, o sea Timsort, y recuerda que Timsort trae el ordenamiento por inserción adentro para los runs chicos, así que no es una pelea del todo justa: construiste una pieza del sort de la librería.

"""The three elementary sorts — bubble, selection, and insertion. All O(n^2), all
short enough to hold in your head, and all worth knowing precisely because they're
where sorting starts and where the O(n log n) sorts earn their keep by contrast.

They differ in character: bubble swaps neighbors, selection finds the minimum each
pass, insertion grows a sorted prefix. Insertion is the one that matters in
practice — it's genuinely fast on nearly-sorted data and is what real libraries use
for small arrays.
"""


# region: bubble
def bubble_sort(a):
    """O(n^2): repeatedly walk the array swapping adjacent out-of-order pairs, so
    the largest element 'bubbles' to the end on each pass. The early-exit flag
    makes it O(n) on already-sorted input — a pass with no swaps means done."""
    a = list(a)
    n = len(a)
    for i in range(n):
        swapped = False
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:
            break
    return a
# endregion


# region: selection
def selection_sort(a):
    """O(n^2): each pass scans the unsorted part for its minimum and swaps it into
    place. It does only n swaps (good when writes are expensive) but always n^2/2
    comparisons — there's no early exit, sorted input costs the same as random."""
    a = list(a)
    n = len(a)
    for i in range(n):
        lo = i
        for j in range(i + 1, n):
            if a[j] < a[lo]:
                lo = j
        a[i], a[lo] = a[lo], a[i]
    return a
# endregion


# region: insertion
def insertion_sort(a, probe=None):
    """O(n^2) worst, O(n) best: grow a sorted prefix by taking each next element
    and shifting it left past everything larger, into its slot. On nearly-sorted
    data every element barely moves, so it's close to linear — which is why it's
    the sort of choice for small or almost-ordered arrays."""
    a = list(a)
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]                 # shift the larger element right
            j -= 1
            if probe is not None:
                probe.append({"arr": list(a), "key_pos": j + 1, "sorted_to": i})
        a[j + 1] = key                      # drop the key into its place
        if probe is not None:
            probe.append({"arr": list(a), "key_pos": j + 1, "sorted_to": i})
    return a
# endregion

"""Python's `sorted` (and `list.sort`) is Timsort — an O(n log n) hybrid of merge
sort and insertion sort, designed by Tim Peters in 2002 for CPython. It finds runs
of already-ordered data and merges them, and it uses insertion sort (this chapter's
insertion_sort) for the small pieces. So the elementary sorts aren't just baselines
to beat — insertion sort is a component inside the library sort.

The face-off is our three O(n^2) sorts against Timsort's O(n log n).
"""


# region: sort_builtin
def sort_builtin(a):
    """Timsort: O(n log n) worst case, adaptive (near-linear on nearly-sorted or
    already-sorted input), stable, implemented in C."""
    return sorted(a)
# endregion

Desde cero vs librería

El titular es la brecha de 500× en n = 2000 —O(n²) contra O(n log n), la razón por la que existe el resto de este nivel—. Pero el número más interesante es el ordenamiento por inserción contra sí mismo. Con 8000 elementos aleatorios tardó unos 710 ms; con 8000 elementos casi ordenados, unos 38 ms: diecinueve veces más rápido con la misma cantidad de datos, puramente porque los datos ya venían casi en orden. Eso es la adaptividad hecha número, y es la razón por la que el ordenamiento por inserción sobrevive dentro de un sort de librería moderno mientras burbuja y selección quedaron como material didáctico. Toda la estrategia de Timsort es encontrar los runs casi ordenados que traen los datos reales y dejar que inserción los termine barato.

Dónde te lo vas a encontrar de verdad

Rara vez vas a llamar uno de estos directamente, pero usas el ordenamiento por inserción todo el tiempo sin saberlo: está dentro de cada llamada a sorted(), terminando los runs chicos. Más allá de eso, inserción es la forma natural de mantener ordenada una lista chica conforme llegan elementos (insertando cada uno en su lugar), que es como mantendrías un leaderboard de los primeros lugares o como mezclarías un lote chico ya ordenado dentro de uno más grande. Y los ordenamientos elementales siguen siendo el primer ejemplo canónico en cualquier curso de algoritmos, porque son donde aprendes a leer un ciclo anidado como una cuadrática, una habilidad que vas a usar en code review muchísimo más de lo que jamás vas a escribir un bubble sort.

Para llevar

Los tres ordenamientos elementales son $O(n^2)$ e in-place: burbuja intercambia vecinos, selección escoge el mínimo en cada pasada, inserción hace crecer un prefijo ordenado. Inserción es el que vale la pena conservar, porque es adaptativo —cerca de $O(n)$ en datos casi ordenados—, lo que lo vuelve el ordenamiento correcto para arrays chicos o casi ordenados y una pieza funcional del Timsort de la librería. Los otros dos son líneas base: conócelos para reconocer una cuadrática cuando la veas.

Ese reconocimiento es el punto del capítulo, porque los siguientes tres ordenamientos existen para escapar de la cuadrática. Merge sort, quicksort y heapsort llegan a $O(n \log n)$ partiendo el problema en lugar de moler cada par: la recursión de divide y vencerás del capítulo pasado, aplicada al ordenamiento. Sigue merge sort.