はじめに

先日、「コンピュータはなぜ動くのか」という書籍を読み返していました。その中の第5章で「アルゴリズム」について触れられており、プログラマのたしなみとして知っておくべき「定番アルゴリズム」がいくつか紹介されていました。

私自身、普段の業務ではライブラリやフレームワークの便利な機能に頼りきりで、こうした基礎的なアルゴリズムを意識して実装する機会はそう多くありません。しかし、基礎を疎かにしては応用も効きません。そこで今回は、自身の知識の整理と定着、そして基礎を振り返りたいエンジニアの方への共有を目的として、紹介されていた定番アルゴリズムを実際にPythonで実装しながら解説してみたいと思います。

そもそもアルゴリズムとは

JIS（日本産業規格）では、アルゴリズムを以下のように定義しています。

明確に定義された有限個の規則の集まりであって、有限回適用することにより問題を解くもの

書籍「コンピュータはなぜ動くのか」では、これをより噛み砕いて「問題を解く手順を、もれなく、文書や図で表したもの」と説明しています。重要なのは、手順が明確であり、かつ有限回で終了するということです。

それでは、さっそく定番のアルゴリズムを見ていきましょう。

1. ユークリッドの互除法

概要

ユークリッドの互除法は、2つの整数の最大公約数（GCD: Greatest Common Divisor）を効率的に求めるためのアルゴリズムです。紀元前300年頃に記された「ユークリッド原論」に登場する、世界最古のアルゴリズムの一つと言われています。

手順は非常にシンプルです。

大きい数を小さい数で割る。
その「余り」で、先ほどの「割る数（小さい方の数）」を割る。
これを余りが0になるまで繰り返す。
余りが0になった時の「割る数」が最大公約数となる。

図解

ユークリッドの互除法のイメージ

具体例

1071 と 1029 の最大公約数を求めてみましょう。

$1071 \div 1029 = 1$ 余り $42$
$1029 \div 42 = 24$ 余り $21$
$42 \div 21 = 2$ 余り $0$

余りが0になったので、この時の割る数である 21 が最大公約数です。

実装（Python）

def gcd(a: int, b: int) -> int:
    """ユークリッドの互除法を用いて最大公約数を求める"""
    while b != 0:
        a, b = b, a % b
    return a

# 実行例
print(f"GCD of 1071 and 1029 is: {gcd(1071, 1029)}")
# 出力: GCD of 1071 and 1029 is: 21

2. エラトステネスのふるい

概要

エラトステネスのふるいは、指定された整数以下の全ての素数を発見するためのアルゴリズムです。
「ふるい」という名前の通り、数値を順番にチェックして、素数ではない数（合成数）をふるい落としていくイメージです。

手順：

2から指定された数までの整数を並べる。
最小の数（最初は2）を素数として残し、その倍数を全て消す。
次に残っている最小の数を素数として残し、その倍数を全て消す。
これを繰り返す。

具体例

30までの素数を求めてみます。

2を残し、2の倍数（4, 6, 8...）を消す。
次に残った3を残し、3の倍数（9, 15, 21...）を消す。
次に残った5を残し、5の倍数（25...）を消す。
これを繰り返すと、2, 3, 5, 7, 11, 13, 17, 19, 23, 29 が残ります。

実装（Python）

def sieve_of_eratosthenes(n: int) -> list[int]:
    """エラトステネスのふるいを用いてn以下の素数リストを返す"""
    if n < 2:
        return []
    
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    
    limit = int(n**0.5)
    
    for i in range(2, limit + 1):
        if is_prime[i]:
            for j in range(i * i, n + 1, i):
                is_prime[j] = False
                
    return [i for i, prime in enumerate(is_prime) if prime]

# 実行確認
print(f"Primes up to 30: {sieve_of_eratosthenes(30)}")

3. 線形探索（リニアサーチ）と番兵法

概要

線形探索は、データの集まり（配列など）の中から目的のデータを探し出す最も基本的なアルゴリズムです。
先頭から順に「これは目的のデータか？」と確認していきます。

単純ですが、データ量が増えると計算時間が比例して増えるため（計算量 $O(n)$ ）、大量のデータには向きません。

番兵法（Sentinel Method）

線形探索のループ処理では、毎回2つの条件をチェックしています。

配列の末尾に到達していないか？
現在の要素が目的の値か？

この「1. 配列の末尾チェック」を省略して高速化するテクニックが番兵法です。
配列の最後に目的の値を「番兵」として追加しておきます。こうすることで、必ずどこかで目的の値が見つかるため、末尾チェックが不要になります。

図解（線形探索）

線形探索のイメージ

実装（Python）

def linear_search_sentinel(data: list[int], target: int) -> int:
    """番兵法を用いた線形探索（副作用を安全に管理する版）"""
    # 番兵を追加（コピーはせず、直接追加して高速化）
    data.append(target)
    
    try:
        i = 0
        while data[i] != target:
            i += 1
            
        # iが元のリストの長さと同じなら、見つけたのは番兵
        if i == len(data) - 1:
            return -1
        else:
            return i
            
    finally:
        # 【重要】途中でエラーが起きても、returnしても、必ず最後に番兵を削除する
        data.pop()

# 実行例
nums = [5, 2, 8, 3, 9]
print(f"Index: {linear_search_sentinel(nums, 8)}") 
print(f"Data check: {nums}") # 中身が [5, 2, 8, 3, 9] のまま（番兵が消えている）ことを確認

4. 2分探索（バイナリサーチ）

概要

2分探索は、ソート済み（整列済み）のデータに対して使える高速な探索アルゴリズムです。
データの中央の値を見て、探している値がそれより大きいか小さいかで探索範囲を半分に絞り込んでいきます。
「High & Low」ゲームで、1〜100の数字を当てる時に「50より上？下？」と聞いていくのと同じ戦略です。計算量は $O(\log n)$ となり、非常に高速です。

図解

2分探索のイメージ

実装（Python）

def binary_search(data: list[int], target: int) -> int:
    """2分探索。見つかればインデックスを、なければ-1を返す"""
    left = 0
    right = len(data) - 1
    
    while left <= right:
        mid = (left + right) // 2
        if data[mid] == target:
            return mid
        elif data[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
            
    return -1

# 実行例（ソート済みである必要がある）
sorted_list = [1, 3, 5, 7, 9, 11, 13, 15]
print(f"Index of 7: {binary_search(sorted_list, 7)}")   # 出力: 3
print(f"Index of 4: {binary_search(sorted_list, 4)}")   # 出力: -1

5. ハッシュ表探索法

概要

ハッシュ表探索法は、ハッシュ関数を使ってデータを格納する場所（アドレス）を直接計算し、そこにデータを保存・検索する方法です。
理想的な状態では、データの量に関わらず一発でデータにアクセスできるため、計算量は $O(1)$ となります。

Pythonの dict や set もこの仕組みを利用しています。

図解

ハッシュ表探索のイメージ

実装（Python）

ここでは、簡易的なハッシュ関数（除算ハッシュ法）を使った実装例を示します。

class SimpleHashTable:
    def __init__(self, size: int):
        self.size = size
        # 衝突（コリジョン）に対応するため、各バケットをリストにする（チェイン法）
        self.table = [[] for _ in range(size)]
    
    def _hash(self, key: int) -> int:
        return key % self.size
    
    def insert(self, key: int, value: str):
        index = self._hash(key)
        # 同じキーがあれば更新、なければ追加
        for i, (k, v) in enumerate(self.table[index]):
            if k == key:
                self.table[index][i] = (key, value)
                return
        self.table[index].append((key, value))
        
    def search(self, key: int) -> str | None:
        index = self._hash(key)
        # バケット内のリストを探索
        for k, v in self.table[index]:
            if k == key:
                return v
        return None

# 実行例
hash_table = SimpleHashTable(10)
hash_table.insert(1, "User A")
hash_table.insert(11, "User B") # 1と11はハッシュ値が同じ（衝突）するが、共存できる

print(hash_table.search(1))  # -> User A
print(hash_table.search(11)) # -> User B

6. バブルソート

概要

バブルソートは、隣り合う要素の大小を比較し、順序が逆であれば入れ替えるという操作を繰り返して整列させるアルゴリズムです。
大きい値が泡（バブル）のようにポコポコと右側（あるいは上）へ浮き上がっていく様子から名付けられました。
実装は簡単ですが、計算量は $O(n^2)$ となり、データ量が多いと非常に遅くなります。

実装（Python）

def bubble_sort(data: list[int]) -> list[int]:
    """バブルソート（最適化版）"""
    n = len(data)
    sorted_data = data.copy()
    
    for i in range(n):
        swapped = False
        for j in range(0, n - 1 - i):
            if sorted_data[j] > sorted_data[j + 1]:
                sorted_data[j], sorted_data[j + 1] = sorted_data[j + 1], sorted_data[j]
                swapped = True
        
        # 一度も交換が起きなければ、既に整列済みなので終了
        if not swapped:
            break
                
    return sorted_data

# 実行例
print(f"Sorted: {bubble_sort([5, 3, 8, 1])}")
# 出力: Sorted: [1, 3, 5, 8]

7. クイックソート

概要

クイックソートは、その名の通り非常に高速なソートアルゴリズムです（平均計算量 $O(n \log n)$ ）。
「分割統治法」という考え方を使います。

基準となる値（ピボット）を一つ選ぶ。
ピボットより小さいグループと、大きいグループに分ける。
分かれた各グループに対して、同様の操作を再帰的に繰り返す。

図解

クイックソートのイメージ

実装（Python）

def quick_sort(data: list[int]) -> list[int]:
    """クイックソート（リスト内包表記を用いた実装）"""
    if len(data) <= 1:
        return data
    
    # ピボットを中央の値にすることで、整列済みデータに対するパフォーマンス低下を防ぐ
    pivot = data[len(data) // 2]
    
    left = [x for x in data if x < pivot]
    middle = [x for x in data if x == pivot] # ピボットと同じ値もここで処理
    right = [x for x in data if x > pivot]
    
    return quick_sort(left) + middle + quick_sort(right)

# 実行例
print(f"Sorted: {quick_sort([5, 3, 8, 1, 9, 2])}")
# 出力: Sorted: [1, 2, 3, 5, 8, 9]

まとめ

今回はプログラマのたしなみとして、7つの定番アルゴリズムをPythonで実装してみました。
普段は意識せずに使っているソートや検索機能も、裏側ではこうしたロジックが動いていることを理解すると、より効率的なコードを書くヒントになるかもしれません。

特に「番兵法」のようなちょっとした工夫で計算量を減らすテクニックや、クイックソートのような「分割統治」の考え方は、複雑な問題を解決する際にも役立つはずです。

ぜひ皆さんも、自分の得意な言語で一度実装してみてはいかがでしょうか。

参考リンク

Discussion