主要アルゴリズムまるわかりガイド：原理からコードまで徹底解説

はじめに

以下に、代表的なアルゴリズムの「原理」「特徴」「計算量」「使いどころ」を、シンプルなJavaScriptコードと共に解説します。

線形探索法 (Linear Search)

配列の先頭から一つずつ、探している値と一致するかを順番に調べていきます。

どんなときに使う？

データがソートされていない場合や、データ量が非常に少ない場合の探索。実装が最も簡単です。

linearSearch.js

function linearSearch(array, target) {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === target) {
      return i; // 見つかった場合はインデックスを返す
    }
  }
  
  return -1; // 見つからなかった場合
}

const arr = [4, 8, 2, 9, 5];
console.log(linearSearch(arr, 9)); // 出力: 3

• 長所: 実装が非常にシンプルで、データがソートされている必要がありません。
• 短所: データ量が多くなると、探索に時間がかかります。
• 時間計算量: O(n)
• 空間計算量: O(1)

二分探索法 (Binary Search)

配列の中央値と探す値を比較し、大小関係に応じて探索範囲を半分に絞っていく処理を繰り返します。

どんなときに使う？

ソート済みの配列から高速に目的の値を見つけたいとき。辞書のように整列されたデータから探すイメージです。

binarySearch.js

function binarySearch(sortedArray, target) {
  let left = 0;
  let right = sortedArray.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (sortedArray[mid] === target) {
      return mid; // 見つかった場合
    } else if (sortedArray[mid] < target) {
      left = mid + 1; // 右半分を探索
    } else {
      right = mid - 1; // 左半分を探索
    }
  }
  return -1; // 見つからなかった場合
}

const sortedArr = [2, 5, 8, 12, 16];
console.log(binarySearch(sortedArr, 12)); // 出力: 3

• 長所: データ量が多くても、非常に高速に探索できる
• 短所: データが必ずソート済みである必要がある
• 時間計算量: O(log n)
• 空間計算量: O(1)

バブルソート (Bubble Sort)

隣り合う要素を比較して、大小関係が逆なら交換します。これを繰り返すと、最も大きい（または小さい）要素が端に「浮かび上がって」きます。

どんなときに使う？

主に教育用です。アルゴリズムの基本を学ぶのに適していますが、非効率なため実用には向きません。

bubbleSort.js

function bubbleSort(array) {
  for (let i = 0; i < array.length; i++) {
    for (let j = 0; j < array.length - 1 - i; j++) {
      if (array[j] > array[j + 1]) {
        // 要素を交換
        [array[j], array[j + 1]] = [array[j + 1], array[j]];
      }
    }
  }
  return array;
}

console.log(bubbleSort([5, 3, 8, 4, 2])); // 出力: [2, 3, 4, 5, 8]

• 短所: 非常に効率が悪く、データ量が多いと極端に遅くなります。
• 時間計算量: O(n²)
• 空間計算量: O(1)

挿入ソート (Insertion Sort)

手持ちのトランプを整理するように、未ソート部分から要素を1つずつ取り出し、ソート済み部分の適切な位置に「挿入」していきます。

どんなときに使う？

データ量が少ない場合や、ほとんどソート済みのデータに対して高速に動作します。

insertionSort.js

function insertionSort(array) {
  for (let i = 1; i < array.length; i++) {
    let current = array[i];
    let j = i - 1;
    while (j >= 0 && array[j] > current) {
      array[j + 1] = array[j]; // 右に移動
      j--;
    }
    array[j + 1] = current;
  }
  return array;
}

console.log(insertionSort([5, 3, 8, 4, 2])); // 出力: [2, 3, 4, 5, 8]

• 長所: ほぼソート済みの場合に高速で、安定ソート
• 短所: データが逆順に並んでいると遅くなる
• 時間計算量: O(n²) (最悪)、O(n) (最良)
• 空間計算量: O(1)

クイックソート (Quick Sort)

配列内からピボット (pivot) となる基準値を1つ選び、それより小さいグループと大きいグループに分割します。これを再帰的に繰り返します。

どんなときに使う？

一般的に最も高速な汎用ソートアルゴリズムの一つです。

quickSort.js

function quickSort(array) {
  if (array.length <= 1) {
    return array;
  }
  const pivot = array[array.length - 1];
  const left = [];
  const right = [];
  for (let i = 0; i < array.length - 1; i++) {
    if (array[i] < pivot) {
      left.push(array[i]);
    } else {
      right.push(array[i]);
    }
  }
  return [...quickSort(left), pivot, ...quickSort(right)];
}

console.log(quickSort([5, 3, 8, 4, 2])); // 出力: [2, 3, 4, 5, 8]

• 長所: 多くの場合（平均的に）非常に高速です。
• 短所: ピボットの選び方が悪いと性能が悪化し、不安定ソートです。
• 時間計算量: O(n log n) (平均)、O(n²) (最悪)
• 空間計算量: O(log n) (平均)

マージソート (Merge Sort)

配列を最小単位になるまで分割し、それを整列させながら併合 (マージ) していく「分割統治法」に基づきます。

どんなときに使う？

どのようなデータに対しても安定したソート時間が求められる場合や、外部ソート（メモリに乗り切らないデータ）に利用されます。

mergeSort.js

function mergeSort(array) {
  if (array.length <= 1) return array;

  const mid = Math.floor(array.length / 2);
  const left = mergeSort(array.slice(0, mid));
  const right = mergeSort(array.slice(mid));

  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }
  return result.concat(left.slice(i)).concat(right.slice(j));
}

console.log(mergeSort([5, 3, 8, 4, 2])); // 出力: [2, 3, 4, 5, 8]

• 長所: 常に安定した性能 O(n log n) を保ち、安定ソートです。
• 短所: 作業用の配列が必要なため、メモリを多く使います。
• 時間計算量: O(n log n)
• 空間計算量: O(n)

ユークリッドの互除法 (Euclidean Algorithm)

2つの整数 a と b の最大公約数は、「b」と「a を b で割った余り」の最大公約数と等しい、という性質を利用します。

どんなときに使う？

2つの整数の最大公約数 (GCD) を効率的に求めたいときに使います。

eculidean.js

function gcd(a, b) {
  while (b !== 0) {
    let temp = b;
    b = a % b;
    a = temp;
  }
  return a;
}

console.log(gcd(48, 18)); // 出力: 6

• 長所: 非常に効率的に最大公約数を計算できます。
• 短所: 用途が最大公約数の計算に限定されます。
• 時間計算量: O(log min(a, b))

深さ優先探索 (DFS: Depth-First Search)

ある頂点から可能な限り深く（遠く）のノードを探索し、行き止まりになったら手前に戻って別の経路を探索します。（再帰で実装するのが一般的）

どんなときに使う？

連結性の判定や迷路の解など、 「行けるところまで行く」 探索に適しています。

dfs.js

// グラフの表現 (隣接リスト)
const graphDfs = {
  'A': ['B', 'C'],
  'B': ['D'],
  'C': 'E',
  'D': [],
  'E': ['F'],
  'F': []
};

/**
 * 深さ優先探索（DFS）を実行し、探索の過程をログに出力します。
 * @param {object} graph - グラフの隣接リスト
 * @param {string} node - 現在のノード
 * @param {number} depth - 再帰の深さ（インデント用）
 * @param {Set<string>} visited - 訪問済みノードを記録するセット
 */
function dfs(graph, node, depth = 0, visited = new Set()) {
  const indent = '  '.repeat(depth); // 深さに応じたインデントを作成

  // 既に訪問済みの場合は何もしない
  if (visited.has(node)) {
    console.log(`${indent}↪️ ${node} は訪問済みのためスキップ`);
    return;
  }

  console.log(`${indent}➡️ Visiting: ${node}`);
  visited.add(node);

  // 隣接するノードを再帰的に探索
  for (const neighbor of graph[node]) {
    dfs(graph, neighbor, depth + 1, visited);
  }

  console.log(`${indent}⬅️ Backtracking from: ${node}`);
}

console.log("探索開始！");
dfs(graphDfs, 'A');
console.log("探索終了！");

出力結果

探索開始！
➡️ Visiting: A
  ➡️ Visiting: B
    ➡️ Visiting: D
    ⬅️ Backtracking from: D
  ⬅️ Backtracking from: B
  ➡️ Visiting: C
    ➡️ Visiting: E
      ➡️ Visiting: F
      ⬅️ Backtracking from: F
    ⬅️ Backtracking from: E
  ⬅️ Backtracking from: C
⬅️ Backtracking from: A
探索終了！

• 長所: 実装が比較的シンプルです。
• 短所: 最短経路の探索には向きません。
• 計算量: O(V + E) (V: 頂点数, E: 辺数)

幅優先探索 (BFS: Breadth-First Search)

始点から見て「近い」頂点から順番に探索します。波が広がるように探索を進めるため、キューを使って実装します。

どんなときに使う？

重みがないグラフにおける最短経路の探索。SNSの「友達の友達」のように、近い順に探索したい場合に最適です。

bfs.js

// グラフの表現 (隣接リスト)
const graphBfs = {
  'A': ['B', 'C'],
  'B': ['D'],
  'C': ['E'],
  'D': [],
  'E': ['F'],
  'F': []
};

/**
 * 幅優先探索（BFS）を実行し、探索の過程をログに出力します。
 * @param {object} graph - グラフの隣接リスト
 * @param {string} startNode - 探索を開始するノード
 */
function bfs(graph, startNode) {
  // 1. 探索の準備
  const queue = [startNode];
  const visited = new Set([startNode]);

  console.log(`探索開始！ 開始ノード: ${startNode}`);
  console.log(`初期状態 => Queue: [${queue}]`);
  console.log('---');

  // 2. キューが空になるまで探索
  while (queue.length > 0) {
    // 2a. キューの先頭からノードを取り出す
    const currentNode = queue.shift();
    console.log(`Dequeue ➡️: ${currentNode} を処理`);
    
    // 2b. 隣接する未訪問ノードを探索
    for (const neighbor of graph[currentNode]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor); // キューの末尾に追加
        console.log(`  Enqueue ⬅️: ${neighbor}`);
      }
    }
    console.log(`現在の状態 => Queue: [${queue}]`);
    console.log('---');
  }
  console.log("探索終了！");
}

bfs(graphBfs, 'A');

出力ログ

探索開始！ 開始ノード: A
初期状態 => Queue: [A]
---
Dequeue ➡️: A を処理
  Enqueue ⬅️: B
  Enqueue ⬅️: C
現在の状態 => Queue: [B,C]
---
Dequeue ➡️: B を処理
  Enqueue ⬅️: D
現在の状態 => Queue: [C,D]
---
Dequeue ➡️: C を処理
  Enqueue ⬅️: E
現在の状態 => Queue: [D,E]
---
Dequeue ➡️: D を処理
現在の状態 => Queue: [E]
---
Dequeue ➡️: E を処理
  Enqueue ⬅️: F
現在の状態 => Queue: [F]
---
Dequeue ➡️: F を処理
現在の状態 => Queue: []
---
探索終了！

• 長所: 重みなしグラフの最短経路を保証できます。
• 短所: 多くのメモリ（キューのサイズ）を必要とすることがあります。
• 計算量: O(V + E) (V: 頂点数, E: 辺数)

ダイクストラ法 (Dijkstra's Algorithm)

始点からのコストを順次確定させながら、未確定の頂点の中で最もコストが小さいものを選んで探索を進めていきます。

どんなときに使う？

カーナビのルート検索のように、辺に重み（コスト）があるグラフの単一始点からの最短経路を求めたいときに使います。

dijkstra.js

// 以下のコードはダイクストラ法の概念を単純化した実装です。
// 実際には「優先度付きキュー」を使うことで効率化します。
const graphDijkstra = {
  'A': { 'B': 4, 'C': 2 },
  'B': { 'A': 4, 'C': 5, 'D': 10 },
  'C': { 'A': 2, 'B': 5, 'D': 3 },
  'D': { 'B': 10, 'C': 3 }
};

function dijkstra(graph, start) {
  const distances = {};
  const visited = new Set();
  const nodes = Object.keys(graph);

  for (const node of nodes) {
    distances[node] = Infinity;
  }
  distances[start] = 0;

  while (nodes.length) {
    // 未訪問ノードの中から最も距離が短いノードを見つける
    nodes.sort((a, b) => distances[a] - distances[b]);
    const closestNode = nodes.shift();

    if (distances[closestNode] === Infinity) break;
    
    visited.add(closestNode);

    for (const neighbor in graph[closestNode]) {
      const newDist = distances[closestNode] + graph[closestNode][neighbor];
      if (newDist < distances[neighbor]) {
        distances[neighbor] = newDist;
      }
    }
  }
  return distances;
}

console.log(dijkstra(graphDijkstra, 'A')); 
// 出力: { A: 0, B: 4, C: 2, D: 5 }

• 長所: 重み付きグラフの最短経路を効率的に求められます。
• 短所: 辺の重みが負である場合は正しく動作しません。
• 計算量: O(E log V) (優先度付きキュー使用時)