1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@sen-ltd

4つのソートをブラウザでアニメーション — JavaScript Generator でアルゴリズムロジックと DOM を完全分離

1
Posted at

ソートビジュアライザはよくあるテーマ。このツールが他と異なるのは アルゴリズムコードが DOM を一切知らない という点。Bubble / Insertion / Merge / Quick Sort はすべて、比較・スワップごとに yield する Generator 関数として実装されている。アニメーションドライバはタイマーで .next() を呼んで棒を再描画するだけ。

🌐 Demo: https://sen.ltd/portfolio/sort-visualizer/
📦 GitHub: https://github.com/sen-ltd/sort-visualizer

なぜ Generator を使うか

よくあるアプローチは async/await + sleep() でアルゴリズムと DOM を同一関数に書くやり方:

// よくあるパターン — DOM がアルゴリズムに混在
async function bubbleSort(bars) {
  for (let i = 0; i < bars.length - 1; i++) {
    for (let j = 0; j < bars.length - 1 - i; j++) {
      bars[j].style.background = "yellow";  // アルゴリズムの中に DOM 操作
      await sleep(delay);
      if (height(bars[j]) > height(bars[j + 1])) {
        swap(bars[j], bars[j + 1]);
        await sleep(delay);
      }
      // ...
    }
  }
}

問題点:

  • DOM なしでソートロジックをテストできない
  • 途中停止に cancelled フラグが必要
  • アルゴリズムを追加するたびに sleep + 色変更のコードをコピペする

Generator を使うと関心事が分離できる:

// sorters.js — DOM もタイマーも一切なし
export function* bubbleSort(arr, colors, stats) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    for (let j = 0; j < n - 1 - i; j++) {
      stats.comparisons++;
      colors[j] = colors[j + 1] = "comparing";
      yield;                               // ← ここで一時停止
      if (arr[j] > arr[j + 1]) {
        stats.swaps++;
        colors[j] = colors[j + 1] = "swapping";
        yield;
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
      colors[j] = colors[j + 1] = "default";
    }
    colors[n - 1 - i] = "sorted";
  }
  colors[0] = "sorted";
}

アニメーションドライバ (index.html 側):

function startAnimation() {
  const gen = ALGO_MAP[currentAlgo](array, colors, stats);

  function step() {
    const { done } = gen.next();  // 1ステップ進める
    render();                      // 状態を描画
    if (!done) animId = setTimeout(step, delay());
    else finishAnimation();
  }

  animId = setTimeout(step, delay());
}

delay() はスライダーの値をその都度読む — ソート中にスピードを変更しても次のステップから即反映される。

停止は clearTimeout(animId) だけ。cancelled フラグ不要。

各アルゴリズムの yield パターン

Bubble Sort

2 ポインタで隣接要素を比較・交換。パス i 後、末尾 n-1-i 番目が確定済みになる。

各パス i:
  j = 0 から n-2-i まで:
    [j, j+1] を comparing にして yield
    逆順なら [j, j+1] を swapping にして yield → swap
    [j, j+1] を default にリセット
  [n-1-i] を sorted に

O(n²) 比較、O(n²) スワップ (最悪)。既ソート入力でもスワップ 0 だが比較は O(n²)。

Insertion Sort

各要素を「整列済みの先頭部分」に挿入していく。

export function* insertionSort(arr, colors, stats) {
  const n = arr.length;
  for (let i = 1; i < n; i++) {
    const key = arr[i];
    colors[i] = "comparing";
    yield;
    let j = i - 1;
    while (j >= 0) {
      stats.comparisons++;
      colors[j] = "comparing";
      yield;
      if (arr[j] > key) {
        stats.swaps++;
        colors[j + 1] = "swapping";
        arr[j + 1] = arr[j];      // 右にシフト
        yield;
        colors[j + 1] = "default";
        colors[j] = "default";
        j--;
      } else {
        colors[j] = "sorted";
        break;
      }
    }
    arr[j + 1] = key;
    for (let k = 0; k <= i; k++) colors[k] = "sorted";  // ← ポイント
    yield;
  }
}

色管理の落とし穴: シフト中に個々の位置を "sorted" にしてしまうと、最終値が確定していない状態で色だけ sorted になる。解決策は key を置いたあとにソート済みの先頭部分 [0..i] をまとめて "sorted" に塗り直す こと。

O(n²) 最悪、ほぼソート済み入力には O(n) — 実用的。

Merge Sort

分割統治 + 一時バッファでのマージ。

function* _merge(arr, colors, stats, l, m, r) {
  const left  = arr.slice(l, m + 1);   // 一時コピー
  const right = arr.slice(m + 1, r + 1);
  let i = 0, j = 0, k = l;

  while (i < left.length && j < right.length) {
    stats.comparisons++;
    colors[k] = "comparing";
    yield;
    if (left[i] <= right[j]) { arr[k] = left[i++]; }
    else { stats.swaps++; arr[k] = right[j++]; }
    colors[k] = "swapping";
    yield;
    colors[k++] = "default";
  }
  // 残りをコピー ...
}

Generator からの再帰呼び出しには yield* が必要:

function* _mergeHelper(arr, colors, stats, l, r) {
  if (l >= r) return;
  const m = (l + r) >> 1;
  yield* _mergeHelper(arr, colors, stats, l, m);      // 委譲
  yield* _mergeHelper(arr, colors, stats, m + 1, r);  // 委譲
  yield* _merge(arr, colors, stats, l, m, r);         // 委譲
}

yield* は再帰 Generator の各 yield をそのまま呼び出し元に伝播させる。アニメーションドライバには "1つのフラットな Generator" に見える。

常に O(n log n)、追加空間 O(n)。

Quick Sort

Lomuto パーティション (末尾要素をピボットにする方式):

function* _partition(arr, colors, stats, low, high) {
  const pivot = arr[high];
  colors[high] = "pivot";   // オレンジ = ピボット
  let i = low - 1;

  for (let j = low; j < high; j++) {
    stats.comparisons++;
    colors[j] = "comparing";
    yield;
    if (arr[j] <= pivot) {
      i++;
      if (i !== j) {
        stats.swaps++;
        colors[i] = colors[j] = "swapping";
        [arr[i], arr[j]] = [arr[j], arr[i]];
        yield;
        colors[i] = "default";
      }
    }
    colors[j] = "default";
  }
  // ピボットを i+1 に配置 ...
  return i + 1;
}

ピボットをオレンジで表示することで「どの要素が仕切り役か」が一目でわかる。パーティション確定後、ピボット位置をすぐ "sorted" (緑) にする — この位置は二度と動かない。

平均 O(n log n)、Lomuto 方式では既ソート・全同値入力が O(n²) の最悪ケース。

DOM なしでテスト

Generator が素の配列を操作するだけなので、テストは簡潔:

import { bubbleSort, insertionSort, mergeSort, quickSort, runSort } from "../sorters.js";

function run(algo, input) {
  const arr    = [...input];
  const colors = new Array(arr.length).fill("default");
  const stats  = { comparisons: 0, swaps: 0 };
  runSort(algo(arr, colors, stats));
  return { arr, colors, stats };
}

test("bubbleSort でランダム配列がソートされる", () => {
  const { arr } = run(bubbleSort, [5, 3, 8, 1, 9, 2, 7, 4, 6]);
  assert.deepEqual(arr, [1, 2, 3, 4, 5, 6, 7, 8, 9]);
});

test("すべての棒が最終的に sorted になる", () => {
  for (const algo of [bubbleSort, insertionSort, mergeSort, quickSort]) {
    const { colors } = run(algo, [3, 1, 4, 1, 5, 9, 2, 6]);
    assert.ok(colors.every(c => c === "sorted"));
  }
});

runSort は Generator を最後まで消費するだけ:

export function runSort(gen) {
  while (!gen.next().done) {}
}

46 テスト、モックなし、jsdom 不要。node --test で完結。

ビジュアライザで見えること

スピード 1 (最低速) でゆっくり見ると:

  • Bubble: 緑の sorted 領域が右から1要素ずつ伸びる
  • Insertion: 緑が左から伸びつつ、key が適切な位置にスライドしていく
  • Merge: 大きなオレンジ帯がマージ境界に現れ、その中でイエローの比較が走る
  • Quick: オレンジのピボットが動き、パーティション確定後にその位置だけ緑になって固定

スピード 5 (最高速) で 120 要素を動かすと Bubble は霧の中、Merge と Quick は一瞬で終わる — O(n²) と O(n log n) の差がそのまま視覚化される。

まとめ

  • Generator + yield でアルゴリズムと DOM を完全分離 — ソートコードに DOM なし、アニメーションドライバにソートロジックなし
  • yield* で再帰 Generator の yield を透過的に伝播
  • スピード変更はコールバックで delay() を読み直すだけで即反映
  • 停止は clearTimeout だけ、フラグ不要
  • Insertion Sort の色管理 は key を置いた後に先頭部分をまとめて再塗りする
  • テストは Node.js で DOM なしに動く

ソース: https://github.com/sen-ltd/sort-visualizer — MIT、ソートロジック ~200 行 + UI ~150 行、46 ユニットテスト、依存なし、ビルドステップなし。

1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?