【基本情報】ソートアルゴリズム完全攻略｜主要な整列方法をまとめて理解
整列の前に、交換後の配列を追ってみる：隣同士の交換を1周ずつ追う無料演習へ。比較回数と交換回数を分け、書き換えた後の値を使う練習ができます。この下では主要な整列方法を学べます。
「バブルソート・選択ソート・挿入ソートの違いが分からない…😇」
「アルゴリズムの名前は覚えたけど、実際にどう並び替わるの？」
「科目Bで擬似言語になると急に難しく感じる…」
基本情報技術者試験のアルゴリズム分野で、ぜひ押さえておきたいのが、
ソート（整列）アルゴリズム
です。
ソートとは簡単にいうと、
データを決められた順番に並べ替える処理
のこと。
例えば、
30 10 50 20 40
というデータを、
10 20 30 40 50
と並べ替える処理です。
科目Bでは、単にソートの名前を覚えるだけではなく、
「プログラムを実行すると、配列がどう変化するのか」
を追えることが重要です。
この記事では、
ソートの基本 → バブルソート → 選択ソート → 挿入ソート → 計算量 → 擬似言語 → トレース問題
の順番で、初心者向けに解説します🔥
⸻
1．そもそもソートとは？
ソート（Sort）とは、
複数のデータを一定の規則に従って並べ替えること
です。
例えば、
data = [40, 10, 30, 20]
を小さい順にすると、
10 20 30 40
になります。
これを、
昇順
といいます。
反対に、
40 30 20 10
のように大きい順に並べることを、
降順
といいます。
まずは、
を覚えましょう。
⸻
2．なぜソートするの？
「別にバラバラでもデータは使えるのでは？」
と思うかもしれません。
しかし、データを整列すると、
その後の処理を効率化できる場合があります。
例えば前回の記事で解説した、
二分探索
です。
二分探索は、
10 20 30 40 50 60 70
のような整列済みデータに対して、中央の値を確認しながら探索範囲を半分ずつ絞ります。
つまり、
ソート
↓
整列済みデータ
↓
二分探索
というつながりがあります。
探索とソートはセットで理解しておくのがおすすめです。
⸻
3．基本情報で押さえたい代表的なソート
まずは次の3つを理解しましょう。
この3つは、処理方法がかなり違います。
一言で覚えるなら、
バブル → 隣と比べる
選択 → 一番小さいものを探す
挿入 → 正しい場所へ差し込む
です。
⸻
4．バブルソートとは？
バブルソート（Bubble Sort）は、
隣り合うデータを比較して、必要なら交換する
という処理を繰り返すソートです。
例えば、
4 2 3 1
を昇順に並べてみましょう。
最初に、
[4 2] 3 1
を比較します。
4 > 2なので交換。
2 4 3 1
次に、
2 [4 3] 1
を比較。
4 > 3なので交換。
2 3 4 1
さらに、
2 3 [4 1]
を比較。
交換すると、
2 3 1 4
になります。
ここで注目したいのは、
最大値の4が一番右まで移動した
ことです。
⸻
5．バブルソートのイメージ
1回目の走査では、
4 2 3 1
↓
2 4 3 1
↓
2 3 4 1
↓
2 3 1 4
となりました。
最後の、
4
は位置が確定します。
次は残りの部分を同じように処理します。
2 3 1 | 4
↓
2 3 1 | 4
↓
2 1 3 | 4
さらに、
2 1 | 3 4
↓
1 2 | 3 4
最終的に、
1 2 3 4
となります。
⸻
6．バブルソートのポイント
バブルソートで覚えたいのは、
隣接する要素を比較する
ことです。
例えば、
A[i]
A[i+1]
を比較し、
A[i] > A[i+1]
なら交換する、といった処理になります。
つまり、
隣を見る
のが最大の特徴です。
⸻
7．交換処理を理解する
ソートでは、
値の交換
が頻繁に登場します。
例えば、
x = 10
y = 20
の値を交換したい場合。
単純に、
x ← y
y ← x
とすると正しく交換できません。
そこで、一時的に値を保存する変数を使います。
temp ← x
x ← y
y ← temp
これで、
x = 20
y = 10
となります。
この、
tempを使った交換処理
は科目Bでも重要です。
⸻
8．交換処理をトレース
最初に、
x = 10
y = 20
とします。
最終的に、
x = 20
y = 10
となります。
ソート問題で交換処理が出てきたら、
temp・A[i]・A[j]を表にする
と追いやすくなります。
⸻
9．バブルソートの擬似言語
考え方を簡略化すると、次のようになります。
for i = 0 to n - 2
for j = 0 to n - 2 - i
if data[j] > data[j + 1]
temp ← data[j]
data[j] ← data[j + 1]
data[j + 1] ← temp
endif
endfor
endfor
一気に見ると難しく感じますが、
重要なのは、
data[j]
data[j + 1]
です。
つまり、
隣同士を比較している
ことが分かります。
⸻
10．バブルソートは二重ループ
先ほどのコードには、
for i
の中に、
for j
があります。
つまり、
二重ループ
です。
イメージすると、
i = 0
├ j = 0
├ j = 1
└ j = 2
i = 1
├ j = 0
└ j = 1
i = 2
└ j = 0
のようになります。
ソート問題では、
iとjを同時に追う
場面が多いため注意しましょう。
⸻
11．選択ソートとは？
選択ソート（Selection Sort）は、
未整列部分から最小値などを探し、先頭と交換する
方法です。
例えば、
4 2 3 1
があります。
最初に、
全体から最小値を探します。
最小値は、
1
ですね。
そこで、先頭の4と交換します。
1 2 3 4
これで、
1
の位置が確定します。
⸻
12．選択ソートの流れ
もう少し分かりやすい例を使います。
5 3 4 1 2
1回目
未整列部分：
5 3 4 1 2
最小値：
1
先頭の5と交換。
1 | 3 4 5 2
2回目
未整列部分：
3 4 5 2
最小値は、
2
3と交換。
1 2 | 4 5 3
3回目
4 5 3
最小値は3。
1 2 3 | 5 4
4回目
5と4を交換。
1 2 3 4 5
完成です。
⸻
13．選択ソートのポイント
選択ソートでは、
未整列部分の最小値を探す
という考え方が重要です。
つまり、
確定済み | 未整列
という2つの領域を意識します。
処理が進むと、
1 | 3 4 5 2
↓
1 2 | 4 5 3
↓
1 2 3 | 5 4
↓
1 2 3 4 | 5
のように、
左側から確定していく
イメージです。
⸻
14．選択ソートの擬似言語
簡略化すると、
for i = 0 to n - 2
min ← i
for j = i + 1 to n - 1
if data[j] < data[min]
min ← j
endif
endfor
temp ← data[i]
data[i] ← data[min]
data[min] ← temp
endfor
となります。
ここで重要なのが、
min
です。
minには、
現在見つかっている最小値の位置
を保存します。
⸻
15．minは「値」ではなく「添字」
ここはかなり間違えやすいポイントです。
例えば、
で、
min = 2
だった場合、
「最小値が2」
とは限りません。
この場合のminは、
添字2
を表しています。
したがって、
data[min]
は、
data[2] = 2
です。
変数に、
値が入っているのか、添字が入っているのか
を確認するクセをつけましょう。
⸻
16．挿入ソートとは？
挿入ソート（Insertion Sort）は、
データを適切な位置へ挿入していく
ソートです。
イメージとしては、
トランプを手札に並べる
感覚に近いです。
例えば、
5 3 4 1
を考えます。
最初の、
5
は整列済みと考えます。
次の3を、
5
と比較。
3の方が小さいので、
3 5
となります。
⸻
17．挿入ソートの流れ
続いて4を見ます。
現在、
3 5 | 4 1
です。
4を適切な位置に入れると、
3 4 5 | 1
となります。
最後に1。
3 4 5 | 1
1を適切な位置まで移動すると、
1 3 4 5
です。
つまり挿入ソートは、
整列済み部分 | 未処理部分
と考え、
未処理データを、
整列済み部分の正しい場所へ挿入
します。
⸻
18．挿入ソートのイメージ
例えば、
3 5 8 | 4
という状態。
4を挿入したい場合、
まず8を右へずらします。
3 5 _ 8
次に5も右へ。
3 _ 5 8
空いた場所へ4を入れます。
3 4 5 8
この、
大きいデータを右へずらして、空いた場所へ挿入する
という動きを理解しておきましょう。
⸻
19．挿入ソートの擬似言語
簡略化すると、
for i = 1 to n - 1
key ← data[i]
j ← i - 1
while j >= 0 and data[j] > key
data[j + 1] ← data[j]
j ← j - 1
endwhile
data[j + 1] ← key
endfor
ここで、
key
は、
今回挿入したい値
です。
⸻
20．挿入ソートで追う変数
挿入ソートでは主に、
i
j
key
を追います。
例えば、
data = [3, 5, 8, 4]
で4を挿入するとき、
key = 4
です。
そして、
8 > 4
なので8を右へ。
5 > 4
なので5も右へ。
3 > 4
は成立しないので停止。
その位置へ4を挿入します。
⸻
21．3つのソートを比較
ここまでを整理します。
※実装や入力状態によって実際の処理量は変わりますが、基本情報ではまず代表的なオーダとして理解しておきましょう。
⸻
22．なぜO(n²)になるの？
例えばバブルソートでは、
for i
for j
という二重ループが登場しました。
データ数をnとすると、単純なイメージでは、
n × n
に近い回数の処理が発生します。
つまり、
n²
です。
そのため、
O(n²)
と表します。
⸻
23．O(n²)の増え方
例えば単純化すると、
データ数が10倍になると、
n²は100倍
になります。
そのため、大量データではO(n²)のアルゴリズムが不利になりやすいことが分かります。
⸻
24．探索アルゴリズムと計算量を比較
前回の探索アルゴリズムと合わせると、
ここはまとめて覚えておくと便利です。
ただし、
計算量だけを暗記するのではなく、なぜそうなるのか
まで理解するのがおすすめです。
⸻
25．ソート問題は「途中経過」が重要
科目Bでは、
「最終的に何順になるか」
だけではなく、
途中で配列がどう変化するか
を追う問題に対応できるようにしましょう。
例えば、
4 2 3 1
というデータ。
バブルソートなら、
4 2 3 1
↓
2 4 3 1
↓
2 3 4 1
↓
2 3 1 4
となります。
この途中経過を、
1処理ずつ書き出す
のがポイントです。
⸻
26．よくある間違い① 3つのソートが混ざる
最もありがちなミスです。
覚え方はシンプルに、
バブル
→ 隣同士
選択
→ 最小値を選ぶ
挿入
→ 正しい位置へ入れる
でOKです。
まずはこの違いを即答できるようにしましょう。
⸻
27．よくある間違い② 昇順・降順を見落とす
問題文に、
昇順
と書かれているのか、
降順
と書かれているのかを必ず確認しましょう。
昇順なら、
1 2 3 4 5
降順なら、
5 4 3 2 1
です。
同じアルゴリズムでも比較条件が変わることがあります。
⸻
28．よくある間違い③ 添字と値を混同する
例えば、
で、
i = 2
なら、
data[i] = 30
です。
つまり、
i
は添字、
data[i]
は値。
ソート問題でもこの区別は非常に重要です。
⸻
29．よくある間違い④ 交換後の配列を更新しない
例えば、
4 2 3
で4と2を交換したら、
2 4 3
になります。
次の比較は、
元の、
4 2 3
ではなく、
交換後の配列
を使います。
つまり、
4 2 3
↓
2 4 3
↓
2 3 4
です。
処理が行われるたびに、
現在の配列を書き直す
ようにしましょう。
⸻
30．よくある間違い⑤ 二重ループを頭だけで追う
ソートでは、
i
j
が同時に動くことがあります。
頭だけで追うと混乱しやすいため、
のような表を書くのがおすすめです。
⸻
31．バブルソート練習問題
次の配列をバブルソートで昇順に並べます。
3 1 2
最初に比較するのは、
3 と 1
です。
3 > 1なので交換。
1 3 2
次に、
3 と 2
を比較。
交換して、
1 2 3
となります。
⸻
32．選択ソート練習問題
次の配列があります。
4 3 1 2
1回目に選択する最小値は？
答えは、
1
です。
先頭の4と交換して、
1 3 4 2
となります。
次の未整列部分は、
3 4 2
です。
⸻
33．挿入ソート練習問題
次の状態があります。
2 5 7 | 4
左側、
2 5 7
は整列済みとします。
4を挿入すると、
2 4 5 7
になります。
ポイントは、
7 → 右へ
5 → 右へ
2 → 4より小さいので停止
です。
⸻
34．どのソートか見抜く方法
問題文や擬似言語を見たら、次を探します。
隣同士を比較している
data[j]
data[j+1]
→ バブルソートの可能性
最小値の位置を探している
min ← i
→ 選択ソートの可能性
keyを保存して前方へ挿入している
key ← data[i]
→ 挿入ソートの可能性
この特徴を知っていると、擬似言語を見た瞬間に処理を予想しやすくなります。
⸻
35．科目Bでの解き方
ソートの擬似言語が出たら、次の順番がおすすめです。
STEP1：昇順か降順か確認
↓
STEP2：配列に添字を書く
↓
STEP3：i・j・min・keyなどの意味を確認
↓
STEP4：比較対象を確認
↓
STEP5：交換・移動があれば配列を書き直す
↓
STEP6：次のループへ進む
重要なのは、
一気に答えを出そうとしないこと
です。
⸻
36．配列には添字を書く
例えば、
data = [40,10,30,20]
なら、
と書きます。
これだけで、
data[2]
と出てきたとき、
30
だとすぐ分かります。
科目Bではかなり有効です。
⸻
37．変数表を作る
例えば選択ソートなら、
のように書くと整理しやすくなります。
挿入ソートなら、
i
j
key
を追います。
アルゴリズム問題では、
変数を可視化する
だけで難易度がかなり下がります。
⸻
38．さらに知っておきたい高速なソート
基本的な3つを理解したら、
より高速なソートアルゴリズム
も名前と特徴を押さえておくと理解が広がります。
代表例は、
クイックソート
マージソート
ヒープソート
などです。
⸻
39．クイックソート
クイックソート（Quick Sort）は、
基準となる値を使ってデータを分割し、再帰的に整列する
考え方です。
基準となる値は、
ピボット（pivot）
と呼ばれます。
イメージは、
データ
↓
pivotを決める
↓
小さいグループ | pivot | 大きいグループ
↓
それぞれをさらに分割
です。
平均的な計算量として、
O(n log n)
が知られています。
ただし、分割のされ方によっては最悪計算量がO(n²)になることがあります。
⸻
40．マージソート
マージソート（Merge Sort）は、
データを分割してから、整列しながら結合する
アルゴリズムです。
イメージは、
8 3 6 1
↓
[8 3] [6 1]
↓
[8][3][6][1]
↓
[3 8] [1 6]
↓
[1 3 6 8]
です。
代表的な計算量は、
O(n log n)
です。
⸻
41．ヒープソート
ヒープソート（Heap Sort）は、
ヒープというデータ構造を利用して整列する方法
です。
ヒープは、
木構造を利用したデータ構造
です。
ヒープソートの代表的な計算量も、
O(n log n)
です。
まずは、
クイック
マージ
ヒープ
↓
O(n log n)が代表的
くらいから整理しておきましょう。
※クイックソートについては平均的な計算量です。
⸻
42．ソートアルゴリズムまとめ
まずは、
バブル・選択・挿入の処理を自分でトレースできる状態
を目指すのがおすすめです。
⸻
43．重要キーワードまとめ
⸻
44．試験直前チェックリスト
試験前に確認してみてください👇
☐ 昇順・降順の違いが分かる
☐ バブルソートの動きを説明できる
☐ 選択ソートの動きを説明できる
☐ 挿入ソートの動きを説明できる
☐ バブル＝隣同士と覚えている
☐ 選択＝最小値などを選ぶと分かる
☐ 挿入＝正しい位置へ入れると分かる
☐ tempを使った交換処理を追える
☐ 添字と値を区別できる
☐ i・jをトレースできる
☐ minの意味を理解している
☐ keyの意味を理解している
☐ 配列の途中状態を書き出せる
☐ O(n²)の意味が分かる
☐ O(n log n)との違いが分かる
☐ クイックソートのpivotを知っている
☐ マージソートの考え方を知っている
⸻
45．最後にこれだけ覚える
時間がない人は、
この表だけでも押さえてください👇
特に科目Bでは、
名前の暗記だけで終わらせない
ことが重要です。
例えば、
data[j] と data[j+1]
を比較していたら、
「隣同士だからバブルソートっぽい」
と考えられる状態を目指しましょう🔥
⸻
まとめ
ソートアルゴリズムは種類が多いため、最初は難しく感じます。
ただし、まずは次の3つを区別できればかなり整理できます。
バブルソート
隣同士を比較
↓
必要なら交換
選択ソート
最小値を探す
↓
先頭と交換
挿入ソート
値を取り出す
↓
適切な位置へ挿入
そして科目Bでは、
「コードを暗記する」のではなく「配列の変化を追う」
ことが大切です。
問題が出たら、
添字を書く → 変数を書く → 比較する → 交換・移動後の配列を書く
という順番でトレースしてみてください。
探索アルゴリズムと合わせて、
探索 → ソート → データ構造
までつながると、科目Bのアルゴリズム問題がかなり読みやすくなります🔥
⸻
📚 基本情報技術者試験を勉強している方へ
このnoteでは、基本情報の科目A・科目Bについて、
「暗記だけではなく、図と処理の流れで理解する」
ことを意識して解説しています。
前回の「線形探索・二分探索」と合わせて読むと、探索とソートの違いも整理しやすくなります。
試験前に見返せるよう、保存して活用してください📌
役に立ったら、スキ・フォローしてもらえると嬉しいです🙌
