こんにちは、みっちゃんです。
プログラミングや基本情報技術者試験などのIT学習で必ずと言っていいほど登場するのが、データを順番通りに並べ替える「ソート（整列）アルゴリズム」です。
「名前や数字のデータをきれいに並べたいけれど、アルゴリズムの種類が多すぎて違いがよくわからない……」と悩んでいませんか？
今回の記事では、初心者の方に向けて、代表的な3つの基本ソートアルゴリズムである「交換ソート（バブルソート等）」「選択ソート」「挿入ソート」の仕組みを、具体例と分かりやすい比喩を交えて徹底解説します！
まずは、今回ベースとなる以下の10個のバラバラな数字の配列を、小さい順（昇順）に並び替えるプロセスを考えてみましょう。
| 5 | 6 | 2 | 9 | 4 | 5 | 1 | 4 | 10 | 3 |
1. 交換ソート（隣同士を比べて交換する）
交換ソート（代表例としてバブルソートなど）は、「隣り合う2つの数字を比較して、大小関係が逆であれば交換（スワップ）する」というシンプルな操作を繰り返すアルゴリズムです。
イメージとしては、炭酸水の水中で泡（バブル）がボコボコと軽いものから順番に上へ浮き上がっていく様子に似ています。
具体的な手順（昇順の場合）
- ステップ1： 左端の1番目と2番目の数字（5 と 6）に注目します。右側が大きければそのままでOKです。
- ステップ2： 次に2番目と3番目の数字（6 と 2）に注目します。右側の方が小さいため、ここで位置を入れ替えます。
- ステップ3： この比較と入れ替えの操作を右端まで進めていくと、一番大きな数字が自然と一番右側に追い出されます。
- ステップ4： 端まで到達したら再び左端に戻り、確定した部分を除きながら同じ操作を繰り返します。
2. 選択ソート（最小値・最大値を選んでいく）
選択ソートは、「並び替えの対象となるデータの中から、一番小さい（または大きい）値を探し出して “選択” し、順番に並べていく」というアルゴリズムです。
トランプのカードを手札から低い順に1枚ずつ選んで左から綺麗に並べ直していく作業をイメージすると分かりやすいでしょう。
具体的な手順（昇順の場合）
- ステップ1： 対象の数字の配列全体から、一番小さい数字（今回の場合は 1）を "選択" し、一番左のスペースに移動させます。
- ステップ2： 既に確定した一番左の数字を除いた残りの配列の中から、再び一番小さい数字（今回は 2）を選択し、2番目の位置に移動させます。
- ステップ3： すべてのデータが綺麗に並び終わるまで、この「最小値の探索と移動」の操作を淡々と繰り返します。
3. 挿入ソート（整列済みの適切な場所に差し込む）
挿入ソートは、データを「すでに並び替えが終わっているグループ」と「まだ並び替えていないグループ」に仮想的に分割し、未整理のグループから1枚ずつカードを取り出して、整理済みグループの適切な正しい隙間に「挿入」していくアルゴリズムです。
トランプを配られたときに、手元で1枚ずつ順番を確認しながら正しい位置に差し込んでいく人間の手札整理の方法に最も近いです。
具体的な手順（昇順の場合）
- ステップ1： 配列の左端1番目（5）を、最初の「並び替え済みグループ」とみなします。残りの9個は「まだ並び替えていないグループ」になります。
- ステップ2： 未整理グループの先頭にある数字（6）を取り出し、並び替え済みグループ（5）と比較して、適切な場所に挿入します（今回は5の右隣にそのまま挿入）。
- ステップ3： この確認と挿入の作業を、未整理のデータがなくなるまで順番に繰り返していきます。
4. 3つのソートアルゴリズムの比較まとめ
今回紹介した3つの基本ソートは、いずれも仕組みが直感的で分かりやすい一方で、データ数が数万件以上に増えてくると処理に時間がかかる（計算量が O(N^2) になる）という特徴があります。
| ソート名 | 基本的なアプローチ | 身近な例え |
|---|---|---|
| 交換ソート | 隣り合う数字を比べて順次入れ替える | 水中の泡がボコボコと浮き上がる様子 |
| 選択ソート | 対象から最小値・最大値を選び出す | トランプを低い順に1枚ずつ選んで並べる |
| 挿入ソート | 整列済みの適切な隙間に数字を差し込む | 手札のカードを順番通りに差し込んでいく |
それぞれの特徴や違いをしっかり押さえておくと、基本情報技術者試験などのIT試験対策だけでなく、プログラムを組む際の基礎力アップにも大いに役立ちます！
5. 参考文献
きたみりゅうじ「きたみりゅうじ キタミ式イラストIT塾 応用情報技術者」技術評論社
