Sorting visualizer за 100 рядків JavaScript

1. Основний прийом: генератори як алгоритми з паузою

Звичайна функція JavaScript виконується до кінця миттєво, щойно ви її викликали — немає вбудованого способу призупинити Bubble Sort посеред обміну і відновити його через 16 мілісекунд на наступному кадрі анімації. Функція-генератор (оголошена як function*) розв'язує це точно: виклик yield призупиняє виконання і повертає значення викликачу, який може відновити його пізніше через .next() — продовжуючи з наступного рядка, з усіма локальними змінними в цілості.

function* countUp(n) {
  for (let i = 0; i < n; i++) yield i; // призупиняється тут щоразу
}
const gen = countUp(3);
gen.next(); // { value: 0, done: false }
gen.next(); // { value: 1, done: false }
gen.next(); // { value: 2, done: false }
gen.next(); // { value: undefined, done: true }

Весь візуалізатор побудований на одній ідеї: написати кожен алгоритм сортування як генератор, що виконує yield щоразу, коли порівнює або обмінює два елементи, а потім дати циклу requestAnimationFrame витягувати по одному кроку і перемальовувати масив між кроками.

2. Дані та налаштування Canvas

Дані — це просто масив чисел, що представляють висоти стовпчиків, а рендерер малює кожне число як кольоровий вертикальний стовпчик. Два індекси — compare — підсвічуються, щоб було видно точно, на що дивиться алгоритм на кожному кроці:

const canvas = document.getElementById('sortCanvas');
const ctx = canvas.getContext('2d');
const N = 80;
let arr = Array.from({ length: N }, () => Math.floor(Math.random() * 100) + 5);

function drawBars(highlight = []) {
  const w = canvas.width / arr.length;
  ctx.clearRect(0, 0, canvas.width, canvas.height);
  arr.forEach((val, i) => {
    ctx.fillStyle = highlight.includes(i) ? '#f87171' : '#60a5fa';
    const h = (val / 105) * canvas.height;
    ctx.fillRect(i * w, canvas.height - h, w - 1, h);
  });
}

3. Bubble Sort як генератор

Bubble Sort повторно проходить масив, обмінюючи сусідні елементи, що стоять не в тому порядку. Записаний як генератор, він ідентичний підручниковій версії, за винятком одного доданого yield після кожного порівняння:

function* bubbleSort(a) {
  for (let i = 0; i < a.length - 1; i++) {
    for (let j = 0; j < a.length - i - 1; j++) {
      yield [j, j + 1]; // збираємось порівняти ці два індекси
      if (a[j] > a[j + 1]) {
        [a[j], a[j + 1]] = [a[j + 1], a[j]]; // обмін
        yield [j, j + 1]; // показуємо і стан після обміну
      }
    }
  }
}

4. Insertion Sort як генератор

Insertion Sort вирощує відсортований префікс по одному елементу, зсуваючи більші елементи праворуч, щоб звільнити місце. Виконання yield при кожному зсуві візуально показує «вставку» у сповільненому відтворенні:

function* insertionSort(a) {
  for (let i = 1; i < a.length; i++) {
    const key = a[i];
    let j = i - 1;
    yield [i, j];
    while (j >= 0 && a[j] > key) {
      a[j + 1] = a[j]; // зсув праворуч
      j--;
      yield [j, j + 1];
    }
    a[j + 1] = key; // вставляємо key у своє місце
    yield [j + 1];
  }
}

5. Quick Sort як генератор

Quick Sort рекурсивний, тому його версія-генератор потребує yield* («делегування yield»), щоб передати кожне значення, повернуте рекурсивним викликом, до верхнього викликача — без цього були б видні лише yield із найзовнішнього виклику:

function* quickSort(a, lo = 0, hi = a.length - 1) {
  if (lo >= hi) return;
  const pivot = a[hi];
  let i = lo - 1;
  for (let j = lo; j < hi; j++) {
    yield [j, hi]; // порівнюємо a[j] з опорним
    if (a[j] < pivot) {
      i++;
      [a[i], a[j]] = [a[j], a[i]];
      yield [i, j];
    }
  }
  [a[i + 1], a[hi]] = [a[hi], a[i + 1]]; // ставимо опорний на його остаточне місце
  yield [i + 1, hi];
  yield* quickSort(a, lo, i);       // делегуємо: передаємо кожен yield з лівої половини
  yield* quickSort(a, i + 2, hi); // … і з правої половини
}

6. Merge Sort як генератор

Merge Sort розбиває масив, рекурсивно сортує обидві половини, а потім зливає їх назад за допомогою допоміжного масиву. Виконання yield як під час розбиття, так і під час фази злиття, показує структуру «розділяй і володарюй» прямо на екрані:

function* mergeSort(a, lo = 0, hi = a.length - 1) {
  if (lo >= hi) return;
  const mid = (lo + hi) >> 1;
  yield* mergeSort(a, lo, mid);
  yield* mergeSort(a, mid + 1, hi);

  const left = a.slice(lo, mid + 1), right = a.slice(mid + 1, hi + 1);
  let i = 0, j = 0, k = lo;
  while (i < left.length && j < right.length) {
    a[k] = left[i] <= right[j] ? left[i++] : right[j++];
    yield [k];  // індекс k щойно отримав злите значення
    k++;
  }
  while (i < left.length)  { a[k] = left[i++];  yield [k++]; }
  while (j < right.length) { a[k] = right[j++]; yield [k++]; }
}

7. Цикл рендерингу

Цикл витягує одну пару {value, done} з активного генератора за кадр анімації, перемальовує стовпчики з підсвіченими повернутими індексами і зупиняється, коли done дорівнює true. Витягування кількох кроків за кадр контролює швидкість відтворення, зовсім не торкаючись коду алгоритму:

let sorter = bubbleSort(arr);
let stepsPerFrame = 3; // вище значення = швидше відтворення

function animate() {
  let result;
  for (let s = 0; s < stepsPerFrame; s++) {
    result = sorter.next();
    if (result.done) break;
  }
  drawBars(result.done ? [] : result.value);
  if (!result.done) requestAnimationFrame(animate);
}
requestAnimationFrame(animate);

8. Повний візуалізатор на ~100 рядків

Об'єднавши всі частини в один самодостатній скрипт — робочий, анімований візуалізатор сортування з чотирма алгоритмами на вибір:

// ── Sorting visualizer на ~100 рядків: генератори + Canvas 2D ──
const canvas = document.getElementById('sortCanvas');
const ctx = canvas.getContext('2d');
const N = 80;
let arr = [];
let sorter = null;
const stepsPerFrame = 3;

function resetArray() {
  arr = Array.from({ length: N }, () => Math.floor(Math.random() * 100) + 5);
}

function drawBars(highlight = []) {
  const w = canvas.width / arr.length;
  ctx.clearRect(0, 0, canvas.width, canvas.height);
  arr.forEach((val, i) => {
    ctx.fillStyle = highlight.includes(i) ? '#f87171' : '#60a5fa';
    const h = (val / 105) * canvas.height;
    ctx.fillRect(i * w, canvas.height - h, w - 1, h);
  });
}

function* bubbleSort(a) {
  for (let i = 0; i < a.length - 1; i++)
    for (let j = 0; j < a.length - i - 1; j++) {
      yield [j, j + 1];
      if (a[j] > a[j + 1]) { [a[j], a[j + 1]] = [a[j + 1], a[j]]; yield [j, j + 1]; }
    }
}

function* insertionSort(a) {
  for (let i = 1; i < a.length; i++) {
    const key = a[i]; let j = i - 1;
    yield [i, j];
    while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j--; yield [j, j + 1]; }
    a[j + 1] = key; yield [j + 1];
  }
}

function* quickSort(a, lo = 0, hi = a.length - 1) {
  if (lo >= hi) return;
  const pivot = a[hi]; let i = lo - 1;
  for (let j = lo; j < hi; j++) {
    yield [j, hi];
    if (a[j] < pivot) { i++; [a[i], a[j]] = [a[j], a[i]]; yield [i, j]; }
  }
  [a[i + 1], a[hi]] = [a[hi], a[i + 1]]; yield [i + 1, hi];
  yield* quickSort(a, lo, i);
  yield* quickSort(a, i + 2, hi);
}

function* mergeSort(a, lo = 0, hi = a.length - 1) {
  if (lo >= hi) return;
  const mid = (lo + hi) >> 1;
  yield* mergeSort(a, lo, mid);
  yield* mergeSort(a, mid + 1, hi);
  const left = a.slice(lo, mid + 1), right = a.slice(mid + 1, hi + 1);
  let i = 0, j = 0, k = lo;
  while (i < left.length && j < right.length) { a[k] = left[i] <= right[j] ? left[i++] : right[j++]; yield [k++]; }
  while (i < left.length)  { a[k] = left[i++];  yield [k++]; }
  while (j < right.length) { a[k] = right[j++]; yield [k++]; }
}

const ALGORITHMS = { bubble: bubbleSort, insertion: insertionSort, quick: quickSort, merge: mergeSort };

function start(name) {
  resetArray();
  sorter = ALGORITHMS[name](arr);
  requestAnimationFrame(animate);
}

function animate() {
  let result;
  for (let s = 0; s < stepsPerFrame; s++) {
    result = sorter.next();
    if (result.done) break;
  }
  drawBars(result.done ? [] : result.value);
  if (!result.done) requestAnimationFrame(animate);
}

start('bubble'); // викличте start('quick'), start('merge'), start('insertion'), щоб перемкнутись