# ソートと探索｜比較ソートの計算量・下界・二分探索・ハッシュ

> 挿入・マージ・クイック・ヒープソートの手順と最悪・平均計算量、比較ソートの下界 log2 n!、クイックソートの平均比較回数、二分探索とハッシュ法の計算量を、比較回数を数えた計算例で解説します。

- HTML版（正規URL）: https://inshihub.com/basics/algorithms/sorting-searching
- 科目: [アルゴリズムとデータ構造](https://inshihub.com/basics/algorithms)（大学基礎課程の数学・物理・化学・生物・情報）
- 最終更新: 2026-11-16
- 先に読む単元: [計算量と漸化式](https://inshihub.com/basics/algorithms/complexity-recurrences)

比較だけで並べ替えるソートは、最悪時に $\lceil \log_2 n! \rceil = \Theta(n \log n)$ 回以上の比較が必要で、マージソートとヒープソートはこの下界を定数倍の範囲で達成する。クイックソートは最悪 $\Theta(n^2)$ だが、入力がランダムな順列なら平均比較回数は $2(n+1)H_n - 4n \approx 1.39\, n \log_2 n$ になる。整列済みの配列は二分探索で $\lfloor \log_2 n \rfloor + 1$ 回以下の比較で探せ、ハッシュ表は負荷率が定数なら期待 $O(1)$ で探索できる。

## 比較ソート・安定性・逆転数の定義

### 定義：比較ソート

要素どうしの大小比較 $a_i \le a_j$ の結果だけを使って並べ替えるアルゴリズムを比較ソートという。挿入・マージ・クイック・ヒープソートは比較ソートである。計数ソートや基数ソートは、キーが $0$ 以上 $k$ 未満の整数であることを使うので比較ソートではない。

### 定義：安定性とその場ソート

キーが等しい要素の相対順序が、整列後も入力と同じに保たれるソートを安定なソートという。入力の配列のほかに $O(1)$（流儀により $O(\log n)$ まで）の作業領域しか使わないものをその場（in-place）ソートという。

### 定義：逆転数

列 $a_1, \dots, a_n$ で $i < j$ かつ $a_i > a_j$ となる組 $(i, j)$ を逆転といい、その個数を逆転数 $\operatorname{inv}(a)$ という。$0 \le \operatorname{inv}(a) \le n(n-1)/2$ で、隣どうしの交換1回で逆転数はちょうど1変わる。

## 代表的なソートの手順と計算量

挿入ソート（配列 $A[1..n]$）の手順は次のとおり。

1. $i = 2, \dots, n$ の順に、$x = A[i]$ を取り出す。
2. $j = i - 1$ から左へ、$A[j] > x$ である間 $A[j+1] \leftarrow A[j]$ と右へずらす。
3. 止まった位置の右 $A[j+1]$ に $x$ を入れる。

マージソートは配列を半分に分けて再帰的に整列し、整列済みの2列を先頭から比べて併合する。長さ $p$ と $q$ の列の併合は $p + q - 1$ 回以下の比較で済む。クイックソートは基準値（ピボット）を1つ選び、それより小さい要素と大きい要素に分割してから、それぞれを再帰的に整列する。ヒープソートは配列を最大ヒープに組み直し（$O(n)$）、根の取り出しと修復（各 $O(\log n)$）を $n - 1$ 回繰り返す。

### 計算量と性質（$n$ 要素、比較回数で数える）

- 挿入ソート

  $$\text{最良 } \Theta(n),\quad \text{最悪・平均 } \Theta(n^2),\quad \text{安定},\ \text{その場}$$

  比較回数は $\operatorname{inv}(a)$ 以上 $\operatorname{inv}(a) + n - 1$ 以下。

- マージソート

  $$\text{最悪・平均 } \Theta(n \log n),\quad \text{安定},\ \text{作業領域 } \Theta(n)$$

  最悪の比較回数は $W(n) = W(\lfloor n/2 \rfloor) + W(\lceil n/2 \rceil) + n - 1$、$n = 2^k$ なら $n \log_2 n - n + 1$。

- クイックソート

  $$\text{最悪 } \Theta(n^2),\quad \text{平均 } \Theta(n \log n),\quad \text{不安定}$$

  最悪は整列済みの入力で先頭をピボットにしたときなどに起き、比較回数は $n(n-1)/2$。

- ヒープソート

  $$\text{最悪・平均 } \Theta(n \log n),\quad \text{不安定},\ \text{その場}$$

- 計数ソート

  $$\Theta(n + k),\quad \text{キーは } 0, \dots, k-1 \text{ の整数},\ \text{安定}$$

  比較を使わないので下界 $\Omega(n \log n)$ の対象外。

## 比較ソートの下界とクイックソートの平均

### 定理・法則：比較ソートの下界

条件：

相異なる $n$ 個のキーを、比較の結果だけを使って並べ替える決定的なアルゴリズム。

主張：

最悪時の比較回数は $\lceil \log_2 n! \rceil$ 以上で、$\log_2 n! = \Theta(n\log n)$ から $\Omega(n \log n)$ である。ランダムな順列に対する平均の比較回数も $\log_2 n!$ 以上になる。

要点：

アルゴリズムを決定木で表すと、$n!$ 通りの入力順はそれぞれ別の葉に着く必要がある。高さ $h$ の二分木の葉は $2^h$ 個以下なので $2^h \ge n!$。キーの範囲を使う計数ソートや基数ソートには当てはまらない。

### 定理・法則：クイックソートの平均比較回数

条件：

相異なる $n$ 個のキーで、入力の $n!$ 通りの順序が等確率（またはピボットを一様ランダムに選ぶ）。分割では、ピボットを残りの $m - 1$ 個と1回ずつ比べる。

主張：

$$C(n) = 2(n+1)H_n - 4n, \qquad H_n = \sum_{k=1}^{n} \frac{1}{k}$$

で、$C(n) = 2n \ln n + O(n) \approx 1.39\, n \log_2 n$。

要点：

整列後に $i$ 番目と $j$ 番目（$i < j$）の要素が比較されるのは、その間の $j - i + 1$ 個から最初にピボットに選ばれるのが両端のどちらかのときで、確率は $2/(j - i + 1)$。これを全組で足すと上の式になる。

## 比較回数を数える計算例

### 計算例：マージソートの比較回数

$(5, 2, 4, 7, 1, 3, 2, 6)$ をマージソートで整列し、比較回数を数えよ。併合では左右の先頭を比べ、等しいときは左を先に出す。

解答：

長さ1の列どうしの併合が4回で、比較は各1回、計4回。$(2,5)$、$(4,7)$、$(1,3)$、$(2,6)$ ができる。

長さ2どうしの併合は2回。$(2,5)$ と $(4,7)$ の併合は $2$ 対 $4$、$5$ 対 $4$、$5$ 対 $7$ の3回で $(2,4,5,7)$。$(1,3)$ と $(2,6)$ も3回で $(1,2,3,6)$。計6回。

最後の併合は、左に $7$ が残るまで比べ続けるので $4 + 4 - 1 = 7$ 回で $(1,2,2,3,4,5,6,7)$。合計 $4 + 6 + 7 = 17$ 回。

検算：

$n = 8$ の最悪の比較回数 $n\log_2 n - n + 1 = 24 - 8 + 1 = 17$ と一致し、下界 $\lceil \log_2 8! \rceil = \lceil \log_2 40320 \rceil = 16$ 以上である。等しい $2$ は入力で前にあったほうが前に残る（安定）。

### 計算例：挿入ソートの比較回数と逆転数

$(5, 2, 4, 6, 1, 3)$ を挿入ソートで整列したときの、比較回数と要素の移動（右へずらす）回数を求めよ。

解答：

逆転は $(5,2), (5,4), (5,1), (5,3), (2,1), (4,1), (4,3), (6,1), (6,3)$ の9個で、右へずらす回数は逆転数に等しく9回。比較は、ずらすたびに1回と、$A[j] \le x$ で止まるときの1回である。左端まで動いて比較なしで止まるのは $2$ と $1$ を入れるときで、止まるための比較は $5 - 2 = 3$ 回。比較回数は $9 + 3 = 12$ 回。

検算：

比較回数は $\operatorname{inv} = 9$ 以上、$\operatorname{inv} + n - 1 = 14$ 以下に入る。実装して数えても比較12回、移動9回になる。

### 計算例：$n = 3$ でのクイックソートの平均

相異なる3要素のランダムな順列を、先頭をピボットとするクイックソートで整列する。平均比較回数を求めよ。

解答：

最初の分割で比較は2回。ピボットが中央値なら（確率 $1/3$）左右が1要素ずつで追加の比較はない。最小か最大なら（確率 $2/3$）残り2要素の整列に1回かかる。平均は

$$2 + \frac{2}{3} \cdot 1 = \frac{8}{3}$$

検算：

公式で $2 \cdot 4 \cdot H_3 - 12 = 8 \cdot \dfrac{11}{6} - 12 = \dfrac{8}{3}$。$3! = 6$ 通りを全部数えても比較回数の合計は16で、平均 $16/6 = 8/3$。$n = 4$ でも全24通りの平均 $29/6$ が公式と一致する。

## 二分探索・二分探索木・ハッシュ法の計算量

整列済み配列 $A[0..n-1]$ から値 $t$ を探す二分探索の手順は次のとおり。

1. $lo = 0$、$hi = n - 1$ とする。
2. $lo \le hi$ の間、$m = \lfloor (lo + hi)/2 \rfloor$ として $A[m]$ と $t$ を比べる。
3. 等しければ $m$ を返す。$A[m] < t$ なら $lo = m + 1$、$A[m] > t$ なら $hi = m - 1$ として2へ戻る。
4. $lo > hi$ になったら「見つからない」を返す。

### 定理・法則：二分探索の比較回数

条件：

長さ $n \ge 1$ の整列済み配列。$A[m]$ と $t$ の三方向の比較（小・等・大）を1回と数える。

主張：

どの $t$ に対しても、比較は $\lfloor \log_2 n \rfloor + 1$ 回以下で終わる。計算量は $\Theta(\log n)$。

要点：

1回の比較で、残る範囲の長さ $\ell$ が $\lfloor \ell/2 \rfloor$ 以下になる。配列が整列していないと使えない。

### 計算例：二分探索の手順を追う

$A = (2, 5, 8, 12, 16, 23, 38, 56, 72, 91)$（添字0から）で $t = 23$ を探せ。

解答：

$(lo, hi) = (0, 9)$ で $m = 4$、$A[4] = 16 < 23$ なので $lo = 5$。$(5, 9)$ で $m = 7$、$A[7] = 56 > 23$ なので $hi = 6$。$(5, 6)$ で $m = 5$、$A[5] = 23$ で見つかる。比較は3回。

検算：

上限 $\lfloor \log_2 10 \rfloor + 1 = 4$ 回以下に収まる。

### 探索のデータ構造

- 二分探索木

  $$\text{探索・挿入・削除 } O(h), \qquad \lfloor \log_2 n \rfloor \le h \le n - 1$$

  $h$ は木の高さ。各節点で、左部分木のキーは節点より小さく、右部分木のキーは大きい。整列済みの順で挿入すると $h = n - 1$ になる。赤黒木などの平衡木は $h = O(\log n)$ を保つ。

- 連鎖法のハッシュ表

  $$\alpha = \frac{n}{m}, \qquad \text{失敗する探索の期待 } \Theta(1 + \alpha)$$

  $m$ はバケット数。各キーが独立に一様なバケットへ写る（単純一様ハッシュ）と仮定する。成功する探索で調べる要素数の期待値は $1 + \alpha/2 - \alpha/(2n)$。

- 開番地法（一様ハッシュ）

  $$\text{失敗する探索の期待探査回数} \le \frac{1}{1 - \alpha} \quad (\alpha < 1)$$

## 答案でよくある誤り

1. 「どんなソートも $\Omega(n \log n)$」と書く。下界は比較ソートについての定理で、キーが小さな整数なら計数ソートは $\Theta(n + k)$ で整列できる。
2. クイックソートの計算量を $O(n \log n)$ とだけ書く。最悪は $\Theta(n^2)$ で、$\Theta(n\log n)$ は平均（ランダムな入力またはランダムなピボット）の評価である。どちらの意味かを書く。
3. マージソートをその場ソートとして扱う。配列の標準的な実装は $\Theta(n)$ の作業領域を使う。
4. 併合で等しいキーのとき右を先に出し、安定性を失う。等しいときは左の列から出す。
5. 二分探索で $m = (lo + hi)/2$ を整数にしない、または $hi = m$ として範囲が縮まらず止まらない。$m$ を切り捨て、$lo = m + 1$、$hi = m - 1$ で必ず範囲を狭める。
6. 二分探索木の探索を常に $O(\log n)$ とする。平衡を保たない木では高さが $n - 1$ になり得るので $O(h)$ と書き、最悪 $\Theta(n)$ を区別する。

## ソートと探索が出た院試の過去問

### [ソートアルゴリズム](https://inshihub.com/exam-themes/sorting-algorithms)（10大学・26問）

- [九州大学大学院 専門科目（情報系4分野） 2026年度 第3問](https://inshihub.com/exam-solutions/kyushu-university/graduate-school-of-information-science-and-electrical-engineering/information-science-specialized-subjects/2026#problem-3): アルゴリズム
- [九州工業大学大学院 専門科目（生命化学情報工学） 2026年度 第3問](https://inshihub.com/exam-solutions/kyushu-institute-of-technology/graduate-school-of-computer-science-and-systems-engineering/life-and-chemical-informatics-engineering/2026#problem-3): 情報科学II
- [東京大学 創造情報学 専門科目 2026年度 第3問](https://inshihub.com/exam-solutions/tokyo-university/information-science/creative-informatics-specialized/2026#problem-3): 情報システム用語の説明
- [東京科学大学 専門科目（数理・計算科学） 2026年度 第3問](https://inshihub.com/exam-solutions/institute-of-science-tokyo/school-of-computing/mathematical-and-computing-science/2026#problem-3): ソートの実行追跡
- [九州工業大学大学院 専門科目（知能情報工学） 2025年度 第2問](https://inshihub.com/exam-solutions/kyushu-institute-of-technology/graduate-school-of-computer-science-and-systems-engineering/intelligent-informatics/2025#problem-2): プログラミング系科目群
- [京都工芸繊維大学大学院 専門科目（情報工学） 2025年度 第3問](https://inshihub.com/exam-solutions/kyoto-institute-of-technology/graduate-school-of-science-and-technology/information-engineering/2025-first#problem-3): プログラミング(2)

解答まで無料で読める演習問題:

- [京都大学 社会情報学コース 2024年度 第2問](https://inshihub.com/exam-solutions/kyoto-university/graduate-school-of-informatics/social-informatics/2024#problem-2): 情報学基礎：マージソート
- [東京大学 専門科目 2023年度 第4問](https://inshihub.com/exam-solutions/tokyo-university/graduate-school-of-engineering/electrical-engineering-and-information-systems/2023#problem-4): 論理回路・アルゴリズム
- [東京大学 学際情報学専攻 先端表現情報学コース 専門科目 2012年度 第2問](https://inshihub.com/exam-solutions/tokyo-university/graduate-school-of-interdisciplinary-information-studies/emerging-design-and-informatics/2012#problem-2): ソートの計算量

### [ハッシュ法](https://inshihub.com/exam-themes/hashing)（5大学・9問）

- [東京大学 創造情報学 専門科目 2025年度 第3問](https://inshihub.com/exam-solutions/tokyo-university/information-science/creative-informatics-specialized/2025#problem-3): 情報システム用語の説明
- [大阪大学 専門科目（情報数理学） 2024年度 第1問](https://inshihub.com/exam-solutions/osaka-university/graduate-school-of-information-science-and-technology/information-and-physical-sciences/2024#problem-1): 情報基礎
- [京都大学 知能情報学コース 2021年度 第3問](https://inshihub.com/exam-solutions/kyoto-university/graduate-school-of-informatics/intelligence-science-and-technology/2021#problem-3): F2-1 アルゴリズムとハッシュ
- [京都大学 社会情報学コース 2021年度 第6問](https://inshihub.com/exam-solutions/kyoto-university/graduate-school-of-informatics/social-informatics/2021#problem-6): T-1：データベースのファイル編成と正規化
- [東京大学 知能機械情報学 2020年度 第1問](https://inshihub.com/exam-solutions/tokyo-university/information-science/mechano-informatics/2020#problem-1): 必答問題：力学・論理回路・基礎用語
- [東京大学 学際情報学専攻 先端表現情報学コース 専門科目 2013年度 第2問](https://inshihub.com/exam-solutions/tokyo-university/graduate-school-of-interdisciplinary-information-studies/emerging-design-and-informatics/2013#problem-2): 集合データ構造

解答まで無料で読める演習問題:

- [東京大学 創造情報学 専門科目 2025年度 第3問](https://inshihub.com/exam-solutions/tokyo-university/information-science/creative-informatics-specialized/2025#problem-3): 情報システム用語の説明
- [大阪大学 専門科目（情報数理学） 2024年度 第1問](https://inshihub.com/exam-solutions/osaka-university/graduate-school-of-information-science-and-technology/information-and-physical-sciences/2024#problem-1): 情報基礎
- [東京大学 創造情報学 専門科目 2023年度 第3問](https://inshihub.com/exam-solutions/tokyo-university/information-science/creative-informatics-specialized/2023#problem-3): 情報システム用語の説明
- [東京大学 学際情報学専攻 先端表現情報学コース 専門科目 2013年度 第2問](https://inshihub.com/exam-solutions/tokyo-university/graduate-school-of-interdisciplinary-information-studies/emerging-design-and-informatics/2013#problem-2): 集合データ構造

### [木構造・二分探索木](https://inshihub.com/exam-themes/tree-structures)（9大学・15問）

- [名古屋大学大学院 複雑系科学 2026年度 第17問](https://inshihub.com/exam-solutions/nagoya-university/graduate-school-of-informatics/complex-systems-science/2026#problem-17): 情3：整列・二分探索木と最短経路法
- [名古屋工業大学 情報工学系 2026年度 第1問](https://inshihub.com/exam-solutions/nagoya-institute-of-technology/graduate-school-of-engineering/information-engineering/2026#problem-1): 計算機ソフトウェア
- [豊橋技術科学大学大学院 情報・知能工学専攻基礎科目 2026年度 第3問](https://inshihub.com/exam-solutions/toyohashi-university-of-technology/graduate-school-of-engineering/information-and-intelligence-engineering/2026-first#problem-3): 二分探索木とC言語
- [静岡大学大学院 情報科学 2025年度 第2問](https://inshihub.com/exam-solutions/shizuoka-university/graduate-school-of-integrated-science-and-technology/computer-science/2025#problem-2): 計算量・再帰・学習
- [京都大学 知能情報学コース 2024年度 第4問](https://inshihub.com/exam-solutions/kyoto-university/graduate-school-of-informatics/intelligence-science-and-technology/2024#problem-4): F2-2 二分探索木と動的計画法
- [大阪大学 専門科目（情報工学） 2024年度 第1問](https://inshihub.com/exam-solutions/osaka-university/graduate-school-of-information-science-and-technology/information-engineering/2024#problem-1): アルゴリズムとプログラミング(挿入ソート)

解答まで無料で読める演習問題:

- [静岡大学大学院 情報科学 2025年度 第2問](https://inshihub.com/exam-solutions/shizuoka-university/graduate-school-of-integrated-science-and-technology/computer-science/2025#problem-2): 計算量・再帰・学習
- [大阪大学 専門科目（情報工学） 2024年度 第1問](https://inshihub.com/exam-solutions/osaka-university/graduate-school-of-information-science-and-technology/information-engineering/2024#problem-1): アルゴリズムとプログラミング(挿入ソート)
- [大阪大学 専門科目（情報数理学） 2023年度 第1問](https://inshihub.com/exam-solutions/osaka-university/graduate-school-of-information-science-and-technology/information-and-physical-sciences/2023#problem-1): 情報基礎