Visualizador de algoritmos de ordenamiento en Canvas 2D

Un visualizador de ordenamiento no debería limitarse a mover barras hasta que parezcan ordenadas. Su trabajo es revelar por qué un algoritmo compara, intercambia, escribe, divide o reserva memoria, y permitir que esas decisiones se midan sin confundirlas con la velocidad de la animación.

La arquitectura más útil separa cuatro piezas: el algoritmo produce una traza de eventos, un reducer aplica esos eventos al estado visual, un scheduler decide cuándo avanzar y Canvas 2D dibuja el resultado.

El algoritmo determina el trabajo; el scheduler solo determina cuánto tarda el usuario en verlo.

01. Separar cálculo, traza y reproducción

Hay tres tiempos distintos:

Tres relojes independientes: cálculo, traza de eventos y reproducción visual

Los frames no son una medida del algoritmo. Dos ejecuciones idénticas pueden durar uno o veinte segundos según la velocidad seleccionada. Para comparar algoritmos, ejecuta el cálculo sin pausas; para enseñar, reproduce la misma traza a una velocidad legible.

También conviene conservar identidad, no solo valor:

type SortItem = {
  id: string;
  value: number;
};

type SortMetrics = {
  comparisons: number;
  swaps: number;
  writes: number;
  auxiliaryPeak: number;
};

El id permite comprobar estabilidad. Si dos elementos tienen el mismo value, un algoritmo estable debe conservar su orden relativo aunque sus barras tengan la misma altura.

02. Un contrato de eventos que todos puedan hablar

El algoritmo no debe conocer Canvas, colores ni duración. Trabaja sobre una copia y emite hechos discretos que otra capa puede reproducir.

Arquitectura dirigida por eventos desde el algoritmo hasta el scheduler y Canvas

type SortEvent =
  | { type: "compare"; indices: [number, number] }
  | { type: "swap"; indices: [number, number] }
  | { type: "write"; index: number; item: SortItem }
  | { type: "bufferWrite"; index: number; item: SortItem }
  | { type: "pivot"; index: number }
  | { type: "range"; start: number; end: number }
  | { type: "markSorted"; index: number };

Este vocabulario cubre intercambios locales, escrituras desde un buffer, pivotes y subrangos. El renderer puede mostrar una segunda fila para memoria auxiliar sin obligar a Merge Sort a dibujarla.

Una traza grabada permite pausar, retroceder, saltar al final o reproducir varias veces sin volver a ejecutar el algoritmo. Para arrays enormes, puede transmitirse de forma incremental y conservar solo checkpoints periódicos.

03. Instrumentar una línea base y comparar con justicia

Bubble Sort es una buena prueba del pipeline porque alterna comparaciones y swaps locales de forma fácil de verificar.

function* bubbleSort(input: SortItem[]): Generator<SortEvent> {
  const values = input.map((item) => ({ ...item }));

  for (let end = values.length - 1; end > 0; end -= 1) {
    for (let index = 0; index < end; index += 1) {
      yield { type: "compare", indices: [index, index + 1] };

      if (values[index].value > values[index + 1].value) {
        [values[index], values[index + 1]] = [
          values[index + 1],
          values[index],
        ];
        yield { type: "swap", indices: [index, index + 1] };
      }
    }

    yield { type: "markSorted", index: end };
  }

  if (values.length > 0) yield { type: "markSorted", index: 0 };
}

Para una comparación válida, todos los algoritmos deben recibir clones del mismo dataset. El preset, el tamaño y la semilla aleatoria deben permanecer visibles. Si cambias los datos entre ejecuciones, la tabla de métricas deja de explicar el algoritmo y empieza a mezclar dos problemas.

Las métricas también necesitan reglas consistentes:

• una comparación cuenta cuando se evalúan dos claves;
• un swap cuenta como intercambio y normalmente implica varias escrituras;
• una escritura cuenta cada posición del array principal modificada;
• la memoria auxiliar registra su pico, no el número de frames que estuvo visible;
• el tiempo de benchmark excluye animación, layout y pintura.

04. Hacer visible la firma de cada algoritmo

No todos los algoritmos deben verse como una secuencia de swaps.

Firmas visuales de Bubble Sort, Merge Sort y Quick Sort sobre el mismo dataset

Merge Sort necesita un ejemplo completo: además de comparar las dos mitades, debe copiar sus restos y escribir todo el buffer de vuelta.

function* mergeRange(
  values: SortItem[],
  start: number,
  middle: number,
  end: number,
): Generator<SortEvent> {
  const buffer: SortItem[] = [];
  let left = start;
  let right = middle;

  while (left < middle && right < end) {
    yield { type: "compare", indices: [left, right] };
    buffer.push(
      values[left].value <= values[right].value
        ? values[left++]
        : values[right++],
    );
  }

  while (left < middle) buffer.push(values[left++]);
  while (right < end) buffer.push(values[right++]);

  for (let offset = 0; offset < buffer.length; offset += 1) {
    const index = start + offset;
    yield { type: "bufferWrite", index: offset, item: buffer[offset] };
    values[index] = buffer[offset];
    yield { type: "write", index, item: buffer[offset] };
  }
}

La comparación usa <= para tomar primero el elemento izquierdo cuando los valores empatan; esa pequeña decisión conserva estabilidad y se puede demostrar usando los id.

05. Canvas nítido y un scheduler independiente de FPS

Canvas debe usar el tamaño CSS para el layout y escalar su buffer por devicePixelRatio. Redimensionarlo en cada frame borra el contexto y desperdicia trabajo; hazlo solo cuando cambie el contenedor o el DPR.

function resizeCanvas(canvas: HTMLCanvasElement, width: number, height: number) {
  const dpr = window.devicePixelRatio || 1;
  canvas.width = Math.round(width * dpr);
  canvas.height = Math.round(height * dpr);
  canvas.style.width = `${width}px`;
  canvas.style.height = `${height}px`;

  const context = canvas.getContext("2d")!;
  context.setTransform(dpr, 0, 0, dpr, 0, 0);
  return context;
}

Consumir una cantidad fija de eventos por frame hace que una pantalla de 120 Hz reproduzca el doble de rápido que una de 60 Hz. La velocidad debe depender del tiempo transcurrido:

Scheduler basado en tiempo a 60 y 120 Hz y escalado HiDPI del buffer de Canvas

let lastTime = performance.now();
let budget = 0;

function tick(now: number) {
  const elapsed = Math.min(now - lastTime, 100);
  lastTime = now;
  budget += (elapsed * eventsPerSecond) / 1000;

  while (budget >= 1 && playback.isRunning()) {
    playback.applyNext();
    budget -= 1;
  }

  renderer.draw();
  requestAnimationFrame(tick);
}

El límite de tiempo evita una avalancha de eventos al volver de una pestaña inactiva. El botón “paso” aplica exactamente un evento; el benchmark, en cambio, ejecuta la traza sin requestAnimationFrame.

06. Controles, validación y definición de terminado

El lab necesita presets que expongan comportamientos distintos: aleatorio con semilla, ordenado, inverso, casi ordenado y pocos valores únicos. Quick Sort revela su estrategia de pivote con datos ordenados; Insertion Sort destaca con pocos desplazamientos; la estabilidad se ve mejor con duplicados.

Los controles mínimos son algoritmo, tamaño, preset, velocidad, pausa, paso, reinicio y cancelación. Una nueva ejecución debe invalidar la anterior mediante un identificador o AbortController, para que eventos atrasados no modifiquen el dataset recién creado.

Una ejecución solo está terminada si cumple tres condiciones:

1. Los valores están en orden no decreciente.
2. El resultado contiene exactamente los mismos id que la entrada.
3. Si el algoritmo promete estabilidad, los id con valores iguales conservan su orden relativo.

El panel debe separar métricas algorítmicas —comparaciones, swaps, escrituras y memoria auxiliar— de métricas de presentación —FPS, duración de reproducción y eventos por segundo—. Así el usuario puede aprender lentamente y comparar honestamente con los mismos datos.

La implementación práctica empieza con un contrato pequeño, Bubble Sort y un renderer sencillo. Cuando la traza, la reproducción y las pruebas son confiables, Merge, Quick, Heap o Radix se convierten en nuevas narrativas sobre el mismo motor, no en visualizadores independientes y frágiles.