基本情報のソートアルゴリズム一覧｜種類・特徴・覚え方を解説

基本情報技術者試験のアルゴリズムで、ソートが出てくると急に苦手意識が出る人は多いです。バブルソート、選択ソート、挿入ソート、クイックソートなど名前が似ていて、どれがどんな動きをするのか混ざりやすいですよね。

ただ、基本情報のソートアルゴリズムは、すべてを細かいコードで丸暗記するよりも、何を比べて、どこを確定させて、配列がどう変わるかを見れば整理しやすくなります。科目Bでも、名前の暗記だけでなく、途中経過を手で追えることが大切です。

この記事では、基本情報で押さえたいソートの種類、特徴、覚え方、問題での見分け方をまとめます。アルゴリズム全体が苦手な人でも、まずは「隣を見る」「最小を選ぶ」「正しい位置へ差し込む」という動きから押さえていきましょう。

基本情報のソートの種類

ソートは整列の処理

ソートとは、複数のデータを決まった順番に並べ替える処理です。基本情報では「整列」と書かれることもあります。たとえば、点数を小さい順に並べる、商品を価格順に並べる、日付を古い順に並べる、といった処理がソートです。アルゴリズムの問題では、配列の中身をどう並べ替えるか、途中でどの要素を比べるか、交換後にどんな順番になるかが問われます。

IPAの基本情報技術者試験シラバスでも、アルゴリズム分野には整列・併合・探索のアルゴリズムが含まれ、用語例として選択ソート、バブルソート、マージソート、挿入ソート、シェルソート、クイックソート、ヒープソートなどが挙げられています。出題範囲そのものを確認したい場合は、IPA公式の基本情報技術者試験シラバスも見ておくと安心です。

最初に押さえるべきなのは、ソートの名前ではなく「何を確定させる処理なのか」です。バブルソートなら隣同士を比べて大きい値を後ろへ送る、選択ソートなら未整列部分から最小値を選ぶ、挿入ソートなら整列済み部分へ値を差し込む、という見方ですね。名前からいきなり暗記しようとすると混ざりますが、動きで分けるとかなり覚えやすくなります。

基本情報のソート問題では、「昇順」「降順」「未整列部分」「整列済み部分」「交換」「挿入」という言葉を先に拾うと、どの処理を追えばよいか判断しやすくなります。

また、ソートは探索や配列操作とも一緒に出やすい論点です。単独の用語暗記で終わらせず、配列の添字、ループ回数、交換後の値までセットで確認すると、科目Bの問題にもつなげやすくなります。

用語	意味	見るポイント
昇順	小さい値から大きい値へ並べる	左から小さくなるか
降順	大きい値から小さい値へ並べる	左から大きくなるか
交換	2つの要素の位置を入れ替える	一時変数や代入順
挿入	値を正しい位置に差し込む	ずらす範囲

バブルソートの動き

バブルソートは、隣り合う要素を比べて、順序が逆なら交換していくソートです。昇順に並べるなら、左から右へ隣同士を比べ、大きい値を少しずつ右側へ送ります。泡が水面に浮かぶように値が移動するので、バブルソートと呼ばれます。基本情報の問題では、1回の走査が終わった時点で、最大値が右端に確定するイメージを持つと追いやすいですね。

たとえば、配列が「5, 2, 4, 1」だったとします。5と2を比べると順序が逆なので交換し、「2, 5, 4, 1」になります。次に5と4を比べて交換し、「2, 4, 5, 1」になります。さらに5と1を比べて交換すると、「2, 4, 1, 5」になります。この時点で最大値5は右端に移動しました。次の走査では、右端の5を除いた範囲で同じことを繰り返します。

バブルソートの覚え方は、「隣を見る」「逆なら交換」「端が確定」です。隣同士を何度も比べるので、比較回数は多くなりやすく、効率はあまり良くありません。ただ、処理の流れは単純なので、科目Bで途中経過を問われたときには出題しやすいソートです。問題文に「隣り合う要素」「交換を繰り返す」「末尾から確定する」といった表現があれば、バブルソートを疑いましょう。

• 隣り合う2つを比較する
• 順序が逆なら交換する
• 1周ごとに端の要素が確定する
• 処理は単純だが比較回数は多くなりやすい

バブルソートを追うときは、すべての値を頭の中で動かすより、1回の走査ごとに配列を1行ずつ書くとミスが減ります。

なお、問題によっては左から右へ最大値を送る形だけでなく、右から左へ最小値を送るような書き方もあります。方向が違っても、隣同士を比較して順序が逆なら交換するという本質は同じです。向きだけで判断せず、比較している要素の関係を確認しましょう。

選択ソートの動き

選択ソートは、未整列の部分から最小値または最大値を選び、先頭側へ置いていくソートです。昇順なら、まず配列全体から最小値を探して先頭に置きます。次に、先頭を除いた未整列部分から最小値を探して2番目に置きます。この流れを繰り返すことで、左側から順に整列済みの範囲が広がっていきます。

バブルソートとの違いは、隣同士をその場で何度も交換するのではなく、「未整列部分の中で一番小さい値を探す」点です。比較は多く発生しますが、交換は各回で基本的に1回です。問題文に「最小値を探す」「最小値の位置を記録する」「先頭要素と交換する」といった流れがあれば、選択ソートの可能性が高いです。

科目Bで選択ソートを読むときは、未整列部分の開始位置を丸で囲むと分かりやすいです。i番目を確定させる回なら、iから最後までを調べ、その中の最小値の位置を覚えておきます。調査が終わったら、i番目と最小値の位置を交換します。この「探す段階」と「交換する段階」を分けて読むことが、選択ソートのミスを減らすコツです。

見る場所	選択ソートでの意味	試験での注意点
未整列部分	まだ確定していない範囲	開始位置が1つずつ右へ動く
最小値	先頭へ置く候補	値だけでなく位置も見る
交換	先頭と最小値を入れ替える	最後に1回だけ交換する形が多い

選択ソートは「今の先頭に置く値を選ぶ」ソートです。隣同士の交換ではなく、未整列部分の最小値探しに注目しましょう。

選択ソートでありがちなミスは、最小値を見つけた瞬間にすぐ交換したつもりで読んでしまうことです。多くの実装では、内側ループで最後まで調べてから交換します。minの位置がいつ更新され、交換がどのタイミングで行われるかを分けて見ると、途中経過を間違えにくくなります。

挿入ソートの動き

挿入ソートは、整列済みの部分に新しい要素を差し込んでいくソートです。手札を数字順に並べる場面を考えると分かりやすいですね。左側はすでに整列済みとして扱い、右側から1枚ずつ取り出して、左側の正しい位置へ入れます。入れる場所を作るために、必要な要素を右へずらすのが特徴です。

たとえば「2, 5, 4, 1」という配列で、左から「2, 5」までが整列済みだとします。次の値4を取り出すと、5より小さく2より大きいので、5を右へずらして、2と5の間に4を入れます。その結果、「2, 4, 5, 1」になります。次に1を取り出すと、5、4、2を右へずらして先頭に入れるので、「1, 2, 4, 5」になります。

挿入ソートは、データがある程度整っていると速く終わりやすいのが特徴です。すでにほぼ昇順に並んでいる場合、ずらす回数が少なくなるからです。一方、逆順に近いデータでは、毎回多くの要素をずらす必要があり、時間がかかります。基本情報では、計算量の細かい証明よりも、「整列済み部分に差し込む」「ずらして場所を作る」という動きを押さえましょう。

• 左側を整列済みとして扱う
• 次の要素を一時的に取り出す
• 大きい要素を右へずらす
• 空いた位置へ取り出した要素を入れる

科目Bでは、tmpやworkのような一時変数が出てきたら挿入ソートを疑う価値があります。取り出した値をどこかに退避し、条件に合う間だけ前の要素を右へずらし、最後に退避した値を空いた場所へ入れる流れは、挿入ソートの典型です。値を上書きしないための退避だと理解すると、代入順も追いやすくなります。

高速なソートの特徴

基本情報では、バブルソート、選択ソート、挿入ソートのような単純なソートだけでなく、クイックソート、マージソート、ヒープソート、シェルソートといった高速なソートも用語として押さえておきたいです。すべてを同じ深さで実装できる必要はありませんが、どんな考え方で速くしているのかを知っておくと、計算量や特徴を問われたときに対応しやすくなります。

クイックソートは、基準となる値を決め、それより小さいグループと大きいグループに分けていく考え方です。分けたグループに対して同じ処理を繰り返すため、再帰の考え方とも関係します。マージソートは、データを分割してから整列済みの列として併合していきます。どちらも、単純に隣同士を何度も比べるより効率よく並べ替えようとする方法です。

ヒープソートは木構造、シェルソートは間隔を空けた挿入ソートのような考え方が関係します。最初から細かい実装まで覚えようとすると重くなりますが、試験対策では「分割して処理する」「木構造を使う」「間隔を変えて整える」といった大きな特徴を押さえるだけでも選択肢を絞りやすくなります。特にクイックソートやマージソートは、O(n log n)の代表として見ておくとよいですね。

ソート	ざっくりした特徴	覚え方
クイックソート	基準値で小さい側と大きい側に分ける	分けて再帰
マージソート	分割してから整列済みの列を併合する	分けて合体
ヒープソート	ヒープという木構造を利用する	木で最大値や最小値を取り出す
シェルソート	間隔を空けて挿入ソートを行う	粗く整えてから細かく整える

高速なソートは、細かいコードを暗記するより、どの考え方で無駄な比較を減らしているかを見ると覚えやすいです。

基本情報のソートの解き方

見分ける順番

基本情報のソート問題で最初にやることは、処理の名前を当てることではありません。まず、問題文や擬似言語の中で、どの範囲を見ているかを確認します。隣同士だけを比べているのか、未整列部分全体から最小値を探しているのか、整列済み部分へ値を差し込んでいるのか。この違いが分かれば、ソート名が書かれていなくても処理を追いやすくなります。

擬似言語で出る場合は、ループ変数にも注目します。外側のループが整列済み範囲を広げ、内側のループが比較や探索を行うことが多いです。たとえば、jとj+1を比べ続けているならバブルソート寄りです。最小値の位置を入れる変数が出てくるなら選択ソート寄りです。取り出した値を退避して、前の要素を右へずらしているなら挿入ソート寄りです。

アルゴリズム全体の読み方がまだ不安な場合は、先に基本情報のアルゴリズム対策で科目Bの全体像を確認し、擬似言語の記法が曖昧な場合は基本情報の擬似言語対策も合わせて読むとつながりやすいです。ソートは配列、ループ、条件分岐がまとまって出るので、前提が抜けていると必要以上に難しく感じます。

この順番で読むと、ソート名を知らない問題にも対応しやすくなります。基本情報では、教科書通りの名前が明記されるとは限らず、少し変形された処理として出ることもあります。だからこそ、名前ではなく、比較対象と確定範囲から判断する癖をつけておくのが大切です。

配列の変化を表にする

ソート問題を安定して解くには、配列の変化を表にするのが一番確実です。頭の中だけで追うと、交換前の値、交換後の値、ループの回数が混ざりやすくなります。特に科目Bでは、問題文が長く、似たような変数名が続くこともあるため、手元に状態を残しておくことが重要です。

表にするときは、すべての処理行を書く必要はありません。比較だけで配列が変わらない行は、慣れてきたら省略しても大丈夫です。ただし、交換が起きた行、挿入のために値を退避した行、要素を右へずらした行、最小値の位置が更新された行は必ず残しましょう。ここを飛ばすと、選択肢の途中経過とズレたときに原因が分からなくなります。

すでにトレース表の作り方を学んでいる人は、ソートでも同じ発想で使えます。列には配列全体を書くか、i、j、min、tmpのような変数だけを書くかを、問題の長さで選びます。詳しい表の作り方は基本情報のトレース表の書き方でも整理しています。ソートでは、配列全体を毎回写すと時間がかかるので、最初は丁寧に、慣れたら変化した部分だけを書くのが現実的です。

列に書くもの	使う場面	目的
i	外側ループ	確定位置を確認する
j	内側ループ	比較している場所を確認する
min	選択ソート	最小値の位置を確認する
tmp	交換や挿入	退避した値を確認する
配列	途中経過問題	選択肢と比べる

配列を毎回すべて書くのが大変なときは、交換後の配列だけを書きます。変化した瞬間を残すだけでも、選択肢の絞り込みにはかなり効きます。

表を作る目的は、きれいなノートを作ることではなく、選択肢と照合できる状態を残すことです。試験本番では時間が限られるので、変化しない値まで丁寧に写し続けるより、交換や挿入で変わった部分に印を付ける方が現実的です。

計算量はざっくり押さえる

基本情報のソートでは、計算量もよく出てくる論点です。計算量とは、データ件数が増えたときに処理量がどれくらい増えるかを表す考え方です。細かい数学の証明まで深く入る必要はありませんが、バブルソート、選択ソート、挿入ソートはだいたいO(n^2)、クイックソートやマージソートは平均的にO(n log n)と押さえておくと選択肢を選びやすくなります。

O(n^2)は、データ数が増えると処理量がかなり増えやすいタイプです。データが10件なら何とか追えても、100件、1000件になると一気に重くなります。一方、O(n log n)は、大量データでも比較的効率よく並べ替えられる考え方です。もちろん実際の速さはデータの並び方や実装にも左右されますが、試験では大まかな分類で十分な場面が多いです。

注意したいのは、「速いソートだから常に問題で答えになる」と決めつけないことです。基本情報では、与えられた擬似言語を正しく追う力が問われます。計算量はあくまで特徴を判断する補助です。問題文がバブルソートの処理を書いているなら、クイックソートの方が一般に速いからといって、答えをクイックソートに寄せてはいけません。まずは処理の流れ、次に計算量という順番で見るのが安全です。

ソート	よく見る計算量	試験対策の覚え方
バブルソート	O(n^2)	隣同士を何度も比較
選択ソート	O(n^2)	未整列部分から最小を探す
挿入ソート	O(n^2)	整列済みへ差し込む
クイックソート	平均O(n log n)	基準値で分割する
マージソート	O(n log n)	分割して併合する

計算量は「試験で選択肢を絞るための地図」です。細かい証明より、どのソートが単純で、どのソートが分割や併合で効率化しているかを押さえましょう。

科目Bでの練習法

ソートを科目B対策として練習するなら、最初から長い問題に挑むより、短い配列で1つずつ動きを確認する方が効果的です。たとえば「4, 1, 3, 2」のような4要素だけで、バブルソートならどう動くか、選択ソートならどう動くか、挿入ソートならどう動くかを別々に追います。同じデータで比べると、ソートごとの違いが見えやすくなります。

次に、擬似言語の形で練習します。変数iとjが何を表しているか、配列の添字が1始まりか0始まりか、交換の順番がどうなっているかを確認しましょう。ソート問題では、ソート名を知っていても、添字を1つ間違えるだけで答えがズレます。特に、内側ループの終了条件、j+1を参照している箇所、最後に交換する箇所は丁寧に見たいところです。

演習では、答え合わせのあとに「なぜそのソートだと判断したか」を一言で書くのがおすすめです。「隣同士を比べていたからバブル」「最小値の位置を保存していたから選択」「tmpへ退避して右へずらしていたから挿入」のように言語化します。これを繰り返すと、初見問題でも処理の特徴を見抜くスピードが上がります。

今すぐ手を動かしたい場合は、基本情報の過去問アプリで無料演習しながら、ソートが出てきた問題だけをノートにまとめるのも効率的です。短い復習を何度も回す方が、長時間悩み続けるより定着しやすいかなと思います。

基本情報のソートまとめ

基本情報のソートアルゴリズムは、名前を丸暗記するよりも、動きで覚えるのが近道です。バブルソートは隣同士を比べて交換し、端を確定させます。選択ソートは未整列部分から最小値を選び、先頭へ置きます。挿入ソートは整列済み部分へ新しい値を差し込みます。まずはこの3つを区別できるだけで、科目Bの読みやすさはかなり変わります。

クイックソートやマージソートなどの高速なソートは、細かいコードよりも「分割」「併合」「再帰」「計算量」のイメージを押さえましょう。問題によっては擬似言語で処理を追う必要がありますが、最初から全部を完璧にしようとしなくて大丈夫です。基本の3つで配列の変化を表にできるようになってから、高速なソートの考え方へ広げる方が安定します。

本番では、ソート名を見た瞬間に焦らず、比較対象、確定する場所、配列の変化を順番に確認してください。隣を見るのか、最小を選ぶのか、正しい位置へ差し込むのか。この判断軸を持っておけば、選択肢の途中経過もかなり絞りやすくなります。基本情報のソートアルゴリズムは、手順を小さく分けて練習すれば、苦手分野から得点源へ変えられます。

復習するときは、間違えた問題を「ソート名を知らなかった」「添字を読み違えた」「交換後の配列を写し間違えた」のどれかに分けてください。原因が分かれば、次にやる練習も決めやすくなります。用語が弱いなら一覧表、添字が弱いなら短い配列のトレース、写し間違いが多いなら表の書き方を優先しましょう。