📖 このページで覚えること
✅ 最低限ここだけ覚える
- バブルソート: 隣接を入れ替える
- 選択ソート: 最小値を前に
- 標準ライブラリの
qsort
⭐ 余裕があれば読む
- クイックソート・マージソート
- 計算量 O(n²) vs O(n log n)
- 安定性の概念
ソートとは ― データを並び替える
配列のデータを昇順（小さい順）や降順（大きい順）に並べ替える処理をソートと呼びます。検索の高速化やデータ整理の基本技術です。
代表的なソートアルゴリズム
| アルゴリズム | 計算量（平均） | 特徴 |
|---|
| バブルソート | O(n²) | 最も単純。隣同士を比較・交換 |
| 選択ソート | O(n²) | 最小値を探して先頭に置く |
| 挿入ソート | O(n²) | トランプの手札整理と同じ。ほぼ整列済みなら高速 |
| クイックソート | O(n log n) | 実用最速。C標準の qsort() はこれがベース |
初心者はまずバブル→選択→挿入の3つを理解しましょう。どれも二重ループで書けるので、forループの復習にもなります。
バブルソート ― 隣同士を比較して交換
配列の隣り合う要素を比較し、順序が逆なら交換。これを繰り返すと大きい値が「泡のように」後ろに浮かび上がっていきます。
void bubbleSort(int a[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (a[j] > a[j+1]) {
// 交換（swap）
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
}
}
}
}
動きのイメージ
[5 3 8 1 4] → 5>3? swap → [3 5 8 1 4]
[3 5 8 1 4] → 5>8? no → [3 5 8 1 4]
[3 5 8 1 4] → 8>1? swap → [3 5 1 8 4]
[3 5 1 8 4] → 8>4? swap → [3 5 1 4 8] ← 8が確定！
... 以下、残りの要素で繰り返す
計算量
O(n²) — 要素数が増えると急激に遅くなる
選択ソート ― 最小値を見つけて先頭に
未整列部分から最小値を探し、先頭と交換する。これを繰り返す。
void selectionSort(int a[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++) {
if (a[j] < a[minIdx])
minIdx = j; // 最小値の位置を記録
}
// i番目と最小値を交換
int tmp = a[i];
a[i] = a[minIdx];
a[minIdx] = tmp;
}
}
動きのイメージ
[5 3 8 1 4] → 最小=1 → swap(5,1) → [1 3 8 5 4]
[1 3 8 5 4] → 最小=3 → そのまま → [1 3 8 5 4]
[1 3 8 5 4] → 最小=4 → swap(8,4) → [1 3 4 5 8]
[1 3 4 5 8] → 最小=5 → そのまま → [1 3 4 5 8] 完了！
計算量
O(n²) — バブルと同じだが交換回数は少ない
メリット
データの移動回数が最小限。わかりやすいアルゴリズム。
挿入ソート ― トランプの手札整理
左端を「整列済み」とし、右の要素を1つずつ正しい位置に挿入していく。トランプを手札に加えるときの動作と同じ。
void insertionSort(int a[], int n) {
for (int i = 1; i < n; i++) {
int key = a[i]; // 挿入する値
int j = i - 1;
while (j >= 0 && a[j] > key) {
a[j+1] = a[j]; // 右にずらす
j--;
}
a[j+1] = key; // 正しい位置に挿入
}
}
動きのイメージ
[5| 3 8 1 4] → 3を挿入 → [3 5| 8 1 4]
[3 5| 8 1 4] → 8はそのまま → [3 5 8| 1 4]
[3 5 8| 1 4] → 1を先頭に → [1 3 5 8| 4]
[1 3 5 8| 4] → 4を3と5の間に → [1 3 4 5 8] 完了！
| の左が整列済み部分。
計算量
O(n²)（最悪）/ O(n)（ほぼ整列済みなら最速！）
メリット
少量データやほぼソート済みデータに強い。安定ソート。
ソート可視化デモ
アルゴリズムを選んで「開始」を押すと、配列が並び替わる過程をアニメーションで確認できます。
「開始」を押すとアニメーションが始まります。
比較回数: 0
交換回数: 0
🎯 線形探索 vs 二分探索 ― 効率の違いを可視化
ソート済み配列から目的の値を探すとき、先頭から1つずつ見る線形探索と、中央と比較して半分ずつ絞る二分探索。両者を並べて動かして、比較回数の差を体感しましょう。
🎯 二分探索（中央と比較して半分ずつ絞る）
比較回数: 0
範囲 [low, high]: -
状態: -
配列の中から値を探します。「探す値」を変更して実行してみてください。
| 要素数 N | 線形探索（最悪） | 二分探索（最悪） | 差 |
|---|
| 10 | 10回 | 4回 | 2.5倍 |
| 100 | 100回 | 7回 | 14倍 |
| 1,000 | 1,000回 | 10回 | 100倍 |
| 1,000,000 | 1,000,000回 | 20回 | 50,000倍 |
💡 二分探索の前提： 配列がソート済みであることが必須。ソートに O(n log n) かかるため、1回だけの探索ならソート＋二分探索より線形探索のほうが速い。でも同じ配列を何度も探すなら圧倒的に二分探索が有利。計算量 O(log n) は二分探索・二分木・ヒープなど多くのアルゴリズムで登場する基本です。
よくある質問（FAQ）
Q. 結局、最も速いソートアルゴリズムは?
A. 一般的にはQuickSort（クイックソート）が最速です。平均時間計算量は O(n log n) で、実装も効率的です。ただしデータの特性に応じて、MergeSort(マージソート)やHeapSort(ヒープソート)の方が速い場合もあります。プロの実装では用途に合わせて使い分けます。
Q. どのソートアルゴリズムをいつ使う?
A. バブルソートは教育用、挿入ソートはほぼソート済みデータに有効、クイックソートは一般的用途（標準ライブラリqsort()で採用）、マージソートはリスト構造や外部ソートに使います。学習初期はバブルソート→挿入ソート→クイックソートの順に習うのが効果的です。
Q. 安定ソート(stable sort)って何?
A. 安定ソートは「同じ値を持つ要素の相対的な位置が変わらないソート」です。例えば学生を点数でソートする際、同じ点数なら元の順序が保たれるのが安定です。安定: バブル・挿入・マージ ソート。不安定: 選択・クイック・ヒープソート。
Q. O(n log n)とかの時間計算量って何?
A. 時間計算量は「データサイズnに対する処理時間の増加傾向」を表します。O(n²)は n が10倍になると処理時間は100倍、O(n log n)なら約33倍です。O(n)が線形、O(n log n)が実用的な高速、O(n²)以上は小規模向けです。
確認クイズ
この講座の理解度をチェックしましょう！
Q1. バブルソートの時間計算量（最悪）は？
O(n)
O(n log n)
O(n²)
バブルソートは隣接要素を繰り返し比較・交換するため、最悪の場合 O(n²) の時間がかかります。
Q2. クイックソートの平均時間計算量は？
O(n)
O(n log n)
O(n²)
クイックソートはピボットで分割統治するため、平均 O(n log n) で高速です。ただし最悪の場合は O(n²) になります。
Q3. 安定ソート（stable sort）とは？
クラッシュしないソート
同じ値の要素の順序が保たれるソート
常に最速のソート
安定ソートでは、同じキーを持つ要素の相対的な順序がソート後も維持されます。マージソートは安定、クイックソートは不安定です。
この講座の理解を深めるおすすめ書籍
サイトで動きを理解し、書籍で演習量を補うと効果的です
📘
苦しんで覚えるC言語
MMGames 著
初心者向けの定番入門書。丁寧な解説で基礎を固められます。
Amazonで見る
📗
新・明解C言語 入門編
柴田望洋 著
図解が豊富で、演習問題も充実。大学の教科書としても採用多数。
Amazonで見る
📙
プログラミング言語C 第2版
B.W.カーニハン, D.M.リッチー 著
通称K&R。C言語の原典。基礎を終えた後のステップアップに最適。
Amazonで見る
※ 上記リンクはアフィリエイトリンクです。購入によりサイト運営を支援いただけます。