JS Algorithm Lab

挿入ソートは「左側は常に整列済み」という不変条件を保ちながら、次の値を正しい位置へ差し込みます。 小さな入力や、ほぼ整列済みの配列で考え方が見えやすいアルゴリズムです。

export function insertionSort(values) {
  const items = [...values];
  for (let i = 1; i < items.length; i++) {
    const key = items[i];
    let j = i - 1;
    while (j >= 0 && items[j] > key) {
      items[j + 1] = items[j];
      j--;
    }
    items[j + 1] = key;
  }
  return items;
}

BFS はキューを使って、近い頂点から順に探索します。 重みのないグラフでは、最初にゴールへ到達した経路が最短経路になります。

const queue = [start];
const visited = new Set([key(start)]);

while (queue.length > 0) {
  const current = queue.shift();
  for (const next of neighbors(current)) {
    if (visited.has(key(next))) continue;
    visited.add(key(next));
    previous.set(key(next), key(current));
    queue.push(next);
  }
}

線形探索は左から順に調べます。二分探索は整列済み配列の中央を見て、探索範囲を半分ずつ捨てます。

while (low <= high) {
  const mid = Math.floor((low + high) / 2);
  if (items[mid] === target) return mid;
  if (items[mid] < target) low = mid + 1;
  else high = mid - 1;
}

スタックは最後に入れたものから取り出す LIFO、キューは最初に入れたものから取り出す FIFO です。

stack.push(item);
stack.pop();     // last item

queue.push(item);
queue.shift();   // first item

DFS は進めるところまで深く進み、行き止まりで戻ります。再帰やスタックで自然に書ける探索です。

function dfs(node) {
  if (visited.has(node)) return;
  visited.add(node);
  for (const next of graph[node]) dfs(next);
}

ダイクストラ法は、未確定の頂点のうち最短距離がいちばん小さいものを確定していきます。 辺の重みが負でないグラフで最短経路を求められます。

dist[start] = 0;
while (unvisited.length) {
  const current = nearest(unvisited);
  relaxEdges(current);
}

入力サイズ n が大きくなるほど、計算量の差は急に見えやすくなります。 同じ n に対する伸び方を横棒で比べます。

O(log n)    binary search
O(n)        linear scan
O(n log n)  efficient sorting
O(n^2)      nested loops