Abierto día y nocheEntrada gratuitaPuedes tocar las exposiciones

Sala F1 · Computación

Observa seis algoritmos de ordenamiento en carrera.

Ejecuta Bubble, Selection, Insertion, Merge, Quick y Heap Sort lado a lado. Observa cada comparación e intercambio, y entiende por qué algunos escalan a millones de elementos mientras otros se quedan atrás.

Cómo funciona

Ordenar es poner elementos en orden — de menor a mayor, de la A a la Z. Todos los algoritmos siguientes resuelven el mismo problema; solo difieren en la estrategia, y la estrategia es lo que observas. Elige un algoritmo (o el modo carrera para los seis a la vez), elige una entrada y pulsa reproducir. Las barras se iluminan mientras el motor trabaja: el amarillo marca comparación, el rojo marca movimiento o intercambio, el violeta marca el pivote y elverde marca posiciones terminadas.

Los controles recuerdan a un reproductor de video porque el motor lo es: reproducir y pausar con la barra espaciadora, un paso a la vez con la flecha derecha, reiniciar con R, nueva lista conN, mezclar con S y velocidades de 0,25× a 8×. Un panel de código resalta cada línea del pseudocódigo mientras se ejecuta, así la animación y el programa avanzan juntos. Prueba la misma carrera dos veces: una con lista invertida, otra casi ordenada, y mira a Insertion Sort pasar del fondo del pelotón a la cabeza.

Los seis algoritmos

Tres son métodos cuadráticos simples — fáciles de escribir, dolorosos a escala. Tres son métodos eficientes que alcanzan O(n log n) con divide y vencerás o una estructura de datos inteligente. Cada ejemplo siguiente es Python completo y ejecutable, operando sobre una lista común.

Bubble Sort — el intercambio de vecinos

Recorre la lista comparando vecinos e intercambiando pares desordenados. Con cada pasada, el mayor elemento no ordenado «flota» hasta su lugar final, así la pasada siguiente puede ser un paso más corta. Si una pasada completa no hace intercambios, la lista ya está ordenada y el algoritmo se detiene antes — su única virtud redentora, que da O(n) con entradas ya ordenadas.

def bubble_sort(a):
    n = len(a)
    for end in range(n - 1, 0, -1):
        swapped = False
        for i in range(end):
            if a[i] > a[i + 1]:
                a[i], a[i + 1] = a[i + 1], a[i]
                swapped = True
        if not swapped:
            break
    return a

Selection Sort — elige el menor, repite

Divide la lista en frente ordenado y resto sin ordenar. En cada paso, recorre todo el resto en busca de su mínimo y lo intercambia a su lugar. Siempre hace el mismo número de comparaciones — unas n²/2 — por muy ordenada que esté la entrada; por eso sus casos mejor, promedio y peor son todos O(n²). Su virtud es hacer como máximo n intercambios, útil cuando intercambiar era caro.

def selection_sort(a):
    n = len(a)
    for i in range(n):
        m = i
        for j in range(i + 1, n):
            if a[j] < a[m]:
                m = j
        a[i], a[m] = a[m], a[i]
    return a

Insertion Sort — el método del jugador de cartas

Como quien ordena cartas en la mano: toma el siguiente elemento y deslízalo a la izquierda pasando todo lo mayor hasta encajar. Con datos casi ordenados casi nada se mueve, así corre en O(n) — el más rápido de la sala en ese caso, y la razón por la que los ordenamientos híbridos reales lo usan en sublistas pequeñas. Con datos invertidos cada elemento recorre toda la distancia: peor caso O(n²). Es estable y no usa memoria extra.

def insertion_sort(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]
            j -= 1
        a[j + 1] = key
    return a

Merge Sort — divide, vencerás, fusiona

Divide la lista por la mitad, ordena cada mitad igual (la recursión llega a elementos únicos, ordenados por definición) y fusiona las mitades tomando siempre el menor de los frentes. La división siempre es equilibrada, así cada nivel cuesta O(n) y hay log n niveles: O(n log n) garantizado, en todos los casos. El precio es O(n) de memoria extra al fusionar, y es estable — los elementos iguales nunca se cruzan.

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left = merge_sort(a[:mid])
    right = merge_sort(a[mid:])
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    return out + left[i:] + right[j:]

Quick Sort — división por pivote

Elige un pivote y particiona: todo lo menor va a la izquierda, todo lo mayor a la derecha. Ordena cada lado igual. Cuando los pivotes caen cerca del medio, la recursión tiene log n niveles y el total es O(n log n) con constantes minúsculas y solo O(log n) de memoria extra para la recursión — en general el más rápido en la práctica. Cuando caen en un extremo, un lado se queda con casi todo y degrada a O(n²). Este simulador elige pivotes pormediana de tres (primer, medio y último elementos), lo que vuelve raro el caso malo en datos reales. El ejemplo en Python de abajo usa simplemente el último elemento como pivote, para que sea corto.

def quick_sort(a, lo=0, hi=None):
    if hi is None:
        hi = len(a) - 1
    if lo < hi:
        p, i = a[hi], lo
        for j in range(lo, hi):
            if a[j] < p:
                a[i], a[j] = a[j], a[i]
                i += 1
        a[i], a[hi] = a[hi], a[i]
        quick_sort(a, lo, i - 1)
        quick_sort(a, i + 1, hi)
    return a

Heap Sort — una cola de prioridades disfrazada

Convierte la lista en un max-heap: un árbol binario compactado en el vector donde cada padre es mayor que sus hijos, así el máximo queda en la posición cero. Retira el máximo repetidamente, intercámbialo al final, encoge el heap en uno y restaura la propiedad bajando la nueva cima. O(n log n) garantizado con O(1) de memoria extra — pero el acceso saltarín no agrada a los cachés del procesador, así suele perder contra Quick y Merge Sort en el cronómetro, aunque empate en el papel.

def heap_sort(a):
    def sift(lo, n, i):
        while True:
            l, r, m = 2 * i + 1, 2 * i + 2, i
            if l < n and a[lo + l] > a[lo + m]:
                m = l
            if r < n and a[lo + r] > a[lo + m]:
                m = r
            if m == i:
                return
            a[lo + i], a[lo + m] = a[lo + m], a[lo + i]
            i = m
    n = len(a)
    for i in range(n // 2 - 1, -1, -1):
        sift(0, n, i)
    for end in range(n - 1, 0, -1):
        a[0], a[end] = a[end], a[0]
        sift(0, end, 0)
    return a

Cómo leer la tabla

Big-O describe crecimiento, no cronómetro: constantes y hardware se ignoran a propósito para que laforma de la escala aparezca. La tabla siguiente es la referencia estándar (Cormen et al.,Introduction to Algorithms; Diccionario de Algoritmos y Estructuras de Datos del NIST). «Estable» significa que los elementos iguales mantienen el orden original.

AlgoritmoMejorPromedioPeorMemoria extraEstable
Bubble SortO(n)O(n²)O(n²)O(1)Sí
Selection SortO(n²)O(n²)O(n²)O(1)No
Insertion SortO(n)O(n²)O(n²)O(1)Sí
Merge SortO(n log n)O(n log n)O(n log n)O(n)Sí
Quick SortO(n log n)O(n log n)O(n²)O(log n)No
Heap SortO(n log n)O(n log n)O(n log n)O(1)No

Pruébalo en el simulador: enfrenta a los seis con lista invertida y luego con lista casi ordenada. El orden de llegada se invierte — Insertion Sort pasa del fondo del pelotón a la cabeza — y ninguna fórmula enseña eso como verlo suceder.

Tres errores frecuentes

«Quick Sort es siempre el más rápido.» De media está entre los más rápidos, pero un Quick Sort sencillo tiene un peor caso de O(n²), por ejemplo cuando el pivote cae siempre en un extremo de la lista. Merge Sort y Heap Sort se mantienen en O(n log n) sea cual sea la entrada.

«Los métodos cuadráticos sencillos no sirven para nada.» Insertion Sort se usa mucho en listas pequeñas y funciona muy bien en listas casi ordenadas. Las rutinas de ordenamiento que se usan en la práctica suelen ser híbridas y pasan a Insertion Sort en los trozos pequeños.

«Un ordenamiento estable es el que nunca falla.» La estabilidad tiene un sentido preciso: los elementos con claves iguales conservan el orden que tenían antes de ordenar. Merge Sort e Insertion Sort son estables; Quick Sort y Heap Sort, en sus formas habituales, no lo son.

Preguntas de los visitantes

¿Qué algoritmo de ordenamiento debo usar en código real?

Casi siempre el ordenamiento nativo del lenguaje: sorted() de Python, Array.sort() de JavaScript o Arrays.sort() de Java para objetos. Son híbridos de ingeniería (Python y Java usan Timsort) con tiempo O(n log n), estables y probados por millones de usuarios. Los seis algoritmos de esta página enseñan las ideas detrás de esas herramientas, no las reemplazan.

Si Bubble Sort es lento, ¿por qué se sigue enseñando?

Porque es la idea de ordenamiento más simple posible: compara vecinos, intercambia si están desordenados, repite. Verlo sufrir junto a Merge Sort en el modo carrera enseña más sobre el crecimiento O(n²) que cualquier fórmula. La salida anticipada también muestra que el mismo algoritmo puede ser O(n) con una entrada ya ordenada y O(n²) en general.

¿Qué significa que un ordenamiento sea estable?

Un ordenamiento estable conserva los elementos iguales en su orden relativo original. Esto importa al ordenar por más de una clave: ordena una clase por nombre y luego por nota con un algoritmo estable, y los alumnos con la misma nota quedan en orden alfabético. Merge, Insertion y Bubble Sort son estables; Selection, Quick y Heap Sort, tal como se implementan normalmente, no lo son.

¿Por qué Quick Sort no siempre es el más rápido si es O(n log n) en promedio?

Porque su peor caso es O(n²): con pivotes desafortunados, cada partición separa un solo elemento. Las buenas implementaciones lo evitan con pivote por mediana de tres (como en este simulador) o aleatorización. Merge Sort garantiza O(n log n) pero usa O(n) de memoria extra; Heap Sort garantiza O(n log n) en el lugar, pero salta por la memoria, algo que no gusta a los cachés modernos.

¿El simulador ejecuta realmente los algoritmos o es solo animación?

Realmente los ejecuta. Cada algoritmo corre su lógica genuina y emite eventos de paso — comparación, intercambio, sobrescritura, pivote, fusión, heapify — que el gráfico animado reproduce. En el modo carrera, los seis corren la misma entrada lado a lado, así la comparación es justa. El modo de palabras ordena texto sin distinguir acentos ni mayúsculas.

¿Qué cuenta realmente la notación Big-O?

Cómo crece el número de pasos básicos con la entrada, ignorando factores constantes. O(n²) significa que duplicar la entrada casi cuadruplica el trabajo; O(n log n) significa que duplicar poco más que duplica. Con n = 1.000.000, es la diferencia entre cerca de un billón de operaciones y veinte millones — minutos o incluso horas contra una fracción de segundo.

Fuentes y lectura complementaria

Cita esta exposición

Eurekarium. (2026). Laboratorio de ordenamiento. https://eurekarium.com/es/computing/sorting-lab/

Última actualización: