ソートアルゴリズムとは、データを決まった順番に並べるための手順です。
商品を安い順に並べる、点数を高い順に並べる、ファイルを新しい順に並べる。このような処理の裏側では、ソートの考え方が使われています。
基本情報技術者試験でも、ソートは大事なテーマです。ただし、ソート名だけを覚えても得点にはつながりにくいです。
科目B全体の進め方を確認したい方は、基本情報技術者試験の科目B対策も参考にしてください。
大切なのは、どの値を比べているのか、どの値を入れ替えたのか、配列の中身がどう変わったのかを順番に追うことです。
この記事では、バブルソート、選択ソート、挿入ソート、クイックソート、マージソートの考え方を、初心者向けに順番に説明します。
ソートアルゴリズムは何をするもの？
ソートアルゴリズムは、ばらばらに並んだデータを、目的に合った順番に並べる処理です。
たとえば、次のような数字があるとします。
5, 2, 8, 1, 4これを小さい順に並べると、次のようになります。
1, 2, 4, 5, 8このように、データを見やすく、使いやすくするために並べ替える処理がソートです。
ソートはデータを順番に並べる処理
ソートでは、データを一定のルールで並べます。
たとえば、数字なら小さい順、大きい順に並べられます。
小さい順は「昇順」、大きい順は「降順」と呼ばれます。
- 昇順：1, 2, 3, 4, 5
- 降順：5, 4, 3, 2, 1
最初は、昇順と降順という言葉を無理に暗記するよりも、「小さい順」「大きい順」と考えると分かりやすいです。
数字だけでなく文字や日付も並べられる
ソートできるのは数字だけではありません。
文字、日付、名前、価格、点数、更新日時なども並べられます。
- 商品を価格が安い順に並べる
- 記事を更新日が新しい順に並べる
- 名前を五十音順に並べる
- テストの点数を高い順に並べる
つまりソートは、一覧を見やすくするための基本の処理です。
並べ方によって使いやすさが変わる
同じデータでも、並べ方によって使いやすさは変わります。
商品を探す人にとっては、価格順が便利なことがあります。新しい情報を見たい人にとっては、更新日順が便利です。成績を見るときは、点数順が便利なこともあります。
ソートは、ただ見た目を整えるだけではありません。データを探しやすくし、判断しやすくするための処理です。
なぜソートを学ぶの？
ソートを学ぶ理由は、プログラムの中でとてもよく使われる処理だからです。
また、基本情報技術者試験では、ソートの名前を問うだけではなく、途中の配列の状態やループの動きが問われることがあります。
そのため、ソートは暗記ではなく、動きを追えるようにすることが大切です。
アルゴリズム全体の考え方を先に確認したい方は、基本情報技術者試験のアルゴリズム入門も参考になります。
データを見つけやすくするため
データが並んでいると、目的の情報を見つけやすくなります。
たとえば、辞書は五十音順に並んでいるので、目的の言葉を探しやすいです。名簿も名前順に並んでいれば、人を探しやすくなります。
データを並べることで、次の処理もしやすくなります。
- 一番小さい値を見つける
- 一番大きい値を見つける
- 同じ値をまとめて見る
- 必要な範囲だけを取り出す
並んだデータから目的の値を探す考え方は、基本情報技術者試験の探索アルゴリズム入門も参考になります。
ランキングや一覧表示で使われるため
Webサイトやアプリでは、ソートがよく使われます。
ショッピングサイトで「価格の安い順」を押すと、商品が安い順に並びます。動画サイトで「人気順」を選ぶと、よく見られている動画が上に出ます。
このような並び替えは、ソートの考え方で作られています。
ソート方法によって効率が変わるため
ソートには、いくつもの方法があります。
どの方法でも「並べる」という目的は同じです。しかし、処理のしかたは違います。
たとえば、少ないデータでは分かりやすい方法で十分です。一方で、大量のデータでは、同じ方法だと時間がかかりすぎることがあります。
つまり、ソートでは「並べられるか」だけでなく、「どのくらい手間がかかるか」も大切です。
基本情報技術者試験では処理の流れを問われやすいため
基本情報技術者試験では、ソートの途中で配列がどう変わるかを問われることがあります。
たとえば、次のような問題です。
- 次に比較する値はどれか
- 交換した後の配列はどうなるか
- ループが終わった時点で、どこまで並んでいるか
- 空欄に入る処理はどれか
このような問題では、ソート名を知っているだけでは足りません。処理を1つずつ追う力が必要です。
ソートは身近で何に使われる？
ソートは、日常で使う多くのサービスに関係しています。
ソートを学ぶと、Webサイトやアプリの一覧表示が、どのような考え方で動いているのかが分かるようになります。
商品を価格順に並べる
ネット通販で商品を探すとき、「価格の安い順」や「価格の高い順」を選ぶことがあります。
これは、商品の価格データをもとに並べ替えている処理です。
安い商品から見たい人には安い順が便利です。高級な商品から見たい人には高い順が便利です。
レビューを評価順に並べる
レビューサイトでは、評価が高い順に口コミを並べることがあります。
評価順に並べることで、利用者は良い評価を集めている商品やサービスを見つけやすくなります。
この場合も、評価点をもとにソートしています。
ファイルを更新日順に並べる
パソコンのフォルダでは、ファイルを更新日順に並べられます。
最近使ったファイルを探したいときは、新しい順に並べると便利です。
このように、日付もソートの対象になります。
成績やランキングを点数順に並べる
ゲームのランキングやテストの順位表では、点数順にデータを並べます。
点数が高い順に並べると、上位の人がすぐに分かります。
これもソートの考え方です。
名前順や五十音順に並べる
連絡先や名簿では、名前順に並べることがあります。
名前順に並んでいると、目的の人を探しやすくなります。
数字だけでなく、文字も一定のルールで並べられることを押さえておきましょう。
なぜソート方法はいくつもあるの？
ソートには、バブルソート、選択ソート、挿入ソート、クイックソート、マージソートなど、いくつもの方法があります。
どれもデータを並べる方法ですが、得意な場面が違います。
分かりやすい方法と速い方法がある
バブルソートは、隣どうしを比べて入れ替えるため、動きが分かりやすいです。
一方で、大量のデータを並べるには時間がかかりやすいです。
クイックソートやマージソートは、考え方は少し難しくなりますが、多くのデータを速く並べやすい方法です。
このように、ソートには「理解しやすい方法」と「実用で使いやすい方法」があります。
データの並び方で効率が変わる
ソートの効率は、最初のデータの並び方によって変わります。
たとえば、すでにほとんど並んでいるデータなら、挿入ソートが少ない手間で終わることがあります。
一方で、逆順に並んでいるデータでは、入れ替えや移動が多くなることがあります。
そのため、ソートは「いつでもこの方法が一番」とは言い切れません。
交換回数を減らしたい場合がある
ソートでは、値を比べるだけでなく、値を入れ替えることがあります。
この入れ替えの回数を、交換回数といいます。
交換が多いと、その分だけ処理の手間が増えます。データの持ち方によっては、交換を少なくしたい場面もあります。
選択ソートは、最小値を見つけてからまとめて入れ替えるため、交換回数を少なめにしやすい方法です。
安定して速く並べたい場合がある
ソートでは、どんなデータでも大きく遅くなりにくいことが大切な場合があります。
マージソートは、データを分けてから、並んだもの同士を合体する方法です。
考え方は少し長くなりますが、安定して速く並べたい場面で使いやすい考え方です。
また、同じ値のデータの順番を保ちやすいことを「安定」と呼ぶ場合もあります。
初心者のうちは、まず「処理の速さが大きく崩れにくい」「同じ値の扱いも大切になる」と考えると分かりやすいです。
スタートボタンでソートの動きを見る
ここでは、HTMLとJavaScriptのシミュレーターを使って、ソートの動きを見ながら確認します。
シミュレーターでは、ソート方法とデータの種類を選べます。バブルソート、選択ソート、挿入ソート、クイックソート、マージソートを同じ画面で比べられます。
まずは、ソート方法を「バブルソート」、データの種類を「基本データ：5, 2, 8, 1, 4」のままにして、次へボタンを押してみてください。
スタートボタンを押すと、処理が自動で進みます。次へボタンを押すと、1ステップずつ処理を確認できます。
一気に答えを見るよりも、最初は次へボタンで少しずつ進めると分かりやすいです。
初期データは、本文や図解と同じ次のデータです。
5, 2, 8, 1, 4本文や図解と同じ「5, 2, 8, 1, 4」を使って、どの値を比べたか、入れ替えたか、どこまで確定したかを確認できます。
シミュレーターを動かすときは、次の5つを見てください。
- 今どの値を比べているか
- どの値を入れ替えたか、または移動したか
- どこまで並び終わったか
- 比較回数、交換回数、移動回数がどう増えるか
- ソート方法によって、手順の進み方がどう違うか
色の違いにも注目しましょう。
- 黄色：比較している値
- 赤：交換した値
- 緑：並び終わった範囲
- 紫：クイックソートの基準値
- オレンジ：移動した値、または挿入ソートで今持っている値
ソートは、頭の中だけで考えると分かりにくいです。画面で配列の変化を見ながら追うと、どの値を見ているのか、なぜ入れ替えるのかが分かりやすくなります。
配列とくり返し処理の基本に不安がある方は、基本情報技術者試験の配列とループ入門も確認しておくと理解しやすくなります。
比較している2つの値を見る
ソートでは、まず値どうしを比べます。
たとえば、次の配列があるとします。
5, 2, 8, 1, 4バブルソートなら、まず1番目の「5」と2番目の「2」を比べます。
シミュレーターでは、今見ている値が黄色で強調されます。
ここで大切なのは、「配列全体を一気に見ない」ことです。今のステップでは、どの値とどの値を比べているのかだけを見ます。
選択ソートでは、今の最小値と、次の値を比べます。クイックソートでは、基準値とほかの値を比べます。
同じ「比較」でも、ソート方法によって見ている場所が違う点に注目しましょう。
入れ替えた値や移動した値を見る
比較した結果、順番が違っていれば値を入れ替えます。
たとえば、小さい順に並べたいとき、5と2を比べたら、2の方が小さいです。そのため、5と2を入れ替えます。
入れ替え前：5, 2, 8, 1, 4
入れ替え後：2, 5, 8, 1, 4シミュレーターでは、交換や移動をした値が赤やオレンジで強調されます。
バブルソートや選択ソートでは、値を入れ替える場面が多く出てきます。一方で、挿入ソートやマージソートでは、値を別の場所へ移す動きが大切になります。
そのため、このシミュレーターでは「交換回数」だけでなく「移動回数」も表示しています。
比較しただけで、必ず入れ替えるわけではありません。順番が合っていれば、比較しても入れ替えないことがあります。
並び終わった範囲を見る
ソートによっては、処理が進むと「ここまではもう並んだ」と言える範囲ができます。
シミュレーターでは、並び終わった範囲を緑で表示します。
バブルソートでは、小さい順に並べる場合、大きい値がだんだん後ろへ移動します。そのため、後ろの方から確定していきます。
選択ソートでは、一番小さい値を探して先頭に置くため、前の方から確定していきます。
挿入ソートでは、左側の並んだ部分が少しずつ広がります。オレンジで表示される「今持っている値」が、どこに入るのかを見てください。
クイックソートでは、紫で表示される基準値を使って、小さい側と大きい側に分けます。基準値が正しい位置に置かれると、その位置は確定します。
マージソートでは、データを小さく分けて、並べながら合体します。どの範囲を合体しているのかを、メッセージと配列の変化で確認しましょう。
比較回数・交換回数・移動回数を見る
シミュレーターでは、比較回数、交換回数、移動回数を確認できます。
比較回数は、値どうしを比べた回数です。交換回数は、値の場所を入れ替えた回数です。移動回数は、値を別の場所へ移した回数です。
同じデータでも、ソート方法によって回数は変わります。
たとえば、バブルソートは隣どうしを何度も比べるため、比較回数が増えやすいです。選択ソートは、最小値を探すために比較は多くなりやすいですが、交換回数は少なめにしやすいです。
挿入ソートは、ほぼ並んでいるデータでは少ない手間で終わりやすいです。一方で、逆順のデータでは移動回数が増えやすくなります。
マージソートは、値を入れ替えるというより、分けたまとまりを合体しながら値を移していきます。そのため、交換回数よりも移動回数を見ると特徴が分かりやすいです。
回数を見ると、「この方法はなぜ時間がかかりやすいのか」「このデータにはなぜ向いているのか」が見えてきます。
同じデータでソートを比べる
ソートを比べるときは、同じ初期データを使うことが大切です。
データが違うと、比較回数や交換回数だけを見ても、正しく比べにくいからです。
シミュレーターでは、次のようなデータを選べます。データを切り替えると、ソート方法ごとの違いが分かりやすくなります。
- ランダム
- すでに昇順
- 逆順
- ほぼ並んでいる
- 同じ値が多い
- 文字データ
- 自分で入力
ランダムな数字で比べる
ランダムな数字は、ばらばらに並んだデータです。
5, 2, 8, 1, 4最初にソートの違いを見るなら、ランダムな数字が分かりやすいです。
どの値が動くのか、どのくらい比較や交換が起きるのかを見やすいからです。
すでに並んでいる数字で比べる
すでに昇順に並んでいるデータは、最初から完成に近い状態です。
1, 2, 4, 5, 8この場合、ソート方法によっては、ほとんど交換せずに終わります。
一方で、方法によっては、すでに並んでいても比較を多く行うことがあります。
「すでに並んでいるなら、すべてのソートがすぐ終わる」と考えないようにしましょう。
逆順の数字で比べる
逆順は、目標と反対に並んでいるデータです。
8, 5, 4, 2, 1小さい順に並べたい場合、逆順は手間が多くなりやすいです。
特に、入れ替えや移動をくり返す方法では、交換回数や移動回数が増えやすくなります。
ほぼ並んでいる数字で比べる
ほぼ並んでいるデータは、一部だけ順番が違っているデータです。
1, 2, 5, 4, 8このようなデータでは、挿入ソートが少ない手間で終わりやすいです。
なぜなら、すでに並んだ部分に、ずれている値を差し込むだけで済むことが多いからです。
同じ値が多い数字で比べる
同じ値が多いデータでは、比較しても入れ替えが必要ない場面が増えます。
3, 1, 3, 2, 3このときは、「同じ値をどう扱うか」も見るポイントになります。
同じ値の順番を保つかどうかは、ソートの性質に関係します。
最初は深く考えすぎず、「同じ値があると、比較しても交換しない場合がある」と押さえましょう。
文字データで比べる
ソートは文字にも使えます。
りんご, みかん, いちご, ばなな文字データでは、五十音順や辞書順のようなルールで並べます。
教材で文字データを扱う場合は、「数字だけでなく文字も並べられる」と見せることが大切です。
バブルソートとは？
バブルソートは、隣どうしの値を比べて、必要なら入れ替える方法です。
水の中の泡が上にのぼるように、大きい値が少しずつ後ろへ移動していくイメージで考えると分かりやすいです。
隣どうしを比べて入れ替える
バブルソートでは、配列の隣どうしを順番に比べます。
小さい順に並べる場合、左の値が右の値より大きければ入れ替えます。
5, 2, 8, 1, 4まず、1番目の5と2番目の2を比べます。5の方が大きいので入れ替えます。
2, 5, 8, 1, 4次に、2番目の5と3番目の8を比べます。順番は合っているので入れ替えません。
このように、隣どうしを比べながら進みます。
大きい値が後ろへ移動していく
バブルソートでは、1回の大きな流れが終わると、一番大きい値が後ろに移動します。
たとえば、5, 2, 8, 1, 4を小さい順に並べる場合、8が後ろの方へ移動していきます。
後ろに移動した最大値は、もう正しい場所にあります。
教材では、この確定した場所を強調すると、どこまで並んだかが分かりやすくなります。
仕組みは分かりやすい
バブルソートは、ソートの入門として分かりやすい方法です。
理由は、見る場所が「隣どうし」だからです。
1番目と2番目、2番目と3番目、3番目と4番目というように、順番に見ていけばよいので、処理を追いやすいです。
大量データには向きにくい
バブルソートは分かりやすい一方で、大量のデータには向きにくいです。
隣どうしの比較を何度もくり返すため、データが多くなると比較回数や交換回数が増えやすいからです。
基本情報技術者試験の学習では、まずバブルソートで「比較」「交換」「確定範囲」の見方を覚えるとよいです。
選択ソートとは？
選択ソートは、まだ並んでいない範囲から一番小さい値を選び、先頭に置く方法です。
小さい順に並べる場合、まず全体から一番小さい値を探します。そして、それを1番目に置きます。
一番小さい値を探して先頭に置く
次の配列を小さい順に並べるとします。
5, 2, 8, 1, 4まず、全体の中で一番小さい値を探します。
この場合、一番小さい値は1です。
1を先頭の5と入れ替えます。
1, 2, 8, 5, 4これで1番目は確定です。
先頭から順に確定していく
選択ソートでは、先頭から順に場所が確定していきます。
1番目が確定したら、次は2番目以降の中から一番小さい値を探します。
このように、まだ並んでいない範囲を少しずつ小さくしていきます。
教材では、確定済みの範囲と、まだ探す範囲を分けて表示すると分かりやすいです。
交換回数は少なめにしやすい
選択ソートは、一番小さい値を見つけてから入れ替えます。
そのため、隣どうしを何度も入れ替える方法に比べると、交換回数は少なめにしやすいです。
ただし、これは「交換が少ない」という話です。比較が少ないという意味ではありません。
比較回数は多くなりやすい
選択ソートでは、一番小さい値を探すために、まだ並んでいない範囲を最後まで見ます。
そのため、比較回数は多くなりやすいです。
すでにデータが並んでいても、基本的には最小値を探すために比較を行います。
ここが、初心者が間違えやすい点です。
挿入ソートとは？
挿入ソートは、すでに並んでいる部分に、新しい値を正しい場所へ差し込む方法です。
トランプの手札を並べる場面を思い浮かべると分かりやすいです。
並んだ部分に新しい値を差し込む
挿入ソートでは、配列の左側を「すでに並んでいる部分」と考えます。
そこに、次の値を1つずつ差し込んでいきます。
5, 2, 8, 1, 4最初は、1番目の5だけが並んでいると考えます。
次に、2番目の2を、5の前に入れます。
2, 5, 8, 1, 4このように、並んだ部分を少しずつ広げていきます。
トランプの手札整理に近い
挿入ソートは、トランプの手札を整理する動きに似ています。
新しいカードを1枚引いたとき、すでに手元に並んでいるカードの中で、正しい場所に差し込みます。
すべてのカードを毎回並べ直すのではなく、今ある並びの中に1枚ずつ入れていくイメージです。
ほぼ並んでいるデータに向いている
挿入ソートは、ほぼ並んでいるデータに向いています。
なぜなら、差し込む場所が近くにあることが多く、動かす回数が少なくなりやすいからです。
たとえば、次のようなデータです。
1, 2, 5, 4, 8この場合、5と4の位置を直せば、ほとんど並びます。
逆順だと移動が多くなりやすい
挿入ソートは、逆順のデータでは移動が多くなりやすいです。
8, 5, 4, 2, 1小さい値を正しい位置に差し込むために、多くの値を後ろへずらす必要があります。
教材では、比較回数だけでなく、移動回数も見ると、挿入ソートの特徴が分かりやすくなります。
クイックソートとは？
クイックソートは、基準になる値を決めて、それより小さい側と大きい側に分ける方法です。
分けたグループに対して、同じように並べる処理をくり返します。
考え方は少し難しく感じるかもしれませんが、「基準で分ける」と見ると理解しやすくなります。
基準値を決めて小さい側と大きい側に分ける
クイックソートでは、まず基準値を決めます。
この基準値は、ピボットと呼ばれることがあります。ピボットとは、分けるための目印になる値です。
たとえば、4を基準値にしたとします。
5, 2, 8, 1, 44より小さい値は、2と1です。4より大きい値は、5と8です。
このように、基準値より小さい側と大きい側に分けます。
分けたグループをさらに並べる
小さい側と大きい側に分けたら、それぞれのグループをさらに並べます。
大きなデータをいきなり全部並べるのではなく、小さなまとまりに分けながら並べていくイメージです。
教材では、どの値を基準にしたのか、小さい側と大きい側にどの値が入ったのかを表示すると分かりやすいです。
多くの場面で速くなりやすい
クイックソートは、多くの場面で速くなりやすいソートです。
データを分けながら処理するため、単純に隣どうしを何度も入れ替える方法より、効率よく進みやすいからです。
ただし、いつでも必ず一番速いと考えるのは危険です。
基準値の選び方で効率が変わる
クイックソートでは、基準値の選び方によって効率が変わります。
うまく半分くらいに分けられると、効率よく進みます。
反対に、片方にデータがかたよると、処理が重くなりやすいです。
そのため、クイックソートは「速いことが多いが、基準値の選び方が大切」と覚えるとよいです。
マージソートとは？
マージソートは、データを小さく分けてから、並べながら合体する方法です。
マージとは、合体するという意味です。
まず小さく分け、次に小さなまとまりを並べ、最後にそれらを合体して全体を並べます。
データを小さく分ける
マージソートでは、まずデータを小さなまとまりに分けます。
5, 2, 8, 1, 4これを、半分ずつに分けていきます。
5, 2, 8 と 1, 4さらに小さく分けて、1つずつに近づけます。
1つだけのデータは、それだけで並んでいると考えられます。
小さいまとまりを並べる
分けたデータを、少しずつ並べます。
たとえば、5と2を比べて、2, 5の順にします。
このように、小さなまとまりをまず整えます。
並んだもの同士を合体する
次に、すでに並んだまとまり同士を合体します。
たとえば、次の2つのまとまりがあるとします。
2, 5, 8
1, 4先頭どうしを比べながら、小さい順に取り出していきます。
1, 2, 4, 5, 8これがマージソートの基本の動きです。
安定して速く並べやすい
マージソートは、データを分けて合体するため、安定して速く並べやすい方法です。
また、同じ値の順番を保ちやすいソートとして説明されることもあります。
ただし、分けたデータを一時的に置く場所が必要になることがあります。
基本情報技術者試験の学習では、まず「分ける」「並べる」「合体する」の3段階で理解するとよいです。
比較回数・交換回数とは？
ソートを比べるときは、比較回数や交換回数を見ると違いが分かりやすくなります。
ただし、回数だけで良し悪しを決めるのではなく、データの並び方や使う場面もあわせて見ることが大切です。
比較回数は値を比べた回数
比較回数は、値どうしを比べた回数です。
たとえば、5と2を比べたら、比較回数は1回増えます。
比較回数が多いほど、値を調べる回数が多いということです。
交換回数は値を入れ替えた回数
交換回数は、値を入れ替えた回数です。
5と2を比べて、順番が違うため入れ替えた場合、交換回数が1回増えます。
比較しただけで入れ替えなかった場合、比較回数は増えますが、交換回数は増えません。
回数を見ると効率の違いが分かる
比較回数や交換回数を見ると、ソート方法の違いが見えてきます。
たとえば、バブルソートは隣どうしを何度も比べるため、比較回数が増えやすいです。
選択ソートは最小値を探すため比較は多くなりやすいですが、交換回数は少なめにしやすいです。
挿入ソートは、ほぼ並んだデータでは少ない手間で終わりやすいです。
データの並び方によって回数は変わる
同じソート方法でも、データの並び方によって回数は変わります。
ランダム、昇順、逆順、ほぼ並んでいる、同じ値が多いなど、条件によって結果は変わります。
そのため、教材ではデータの種類を選び、同じデータで各ソートを比べることが大切です。
ソートの向き不向きを比べる
ソートには、それぞれ向き不向きがあります。
「速い」「遅い」だけで覚えるのではなく、なぜそのデータに向いているのかを考えることが大切です。
バブルソートは仕組みの理解に向いている
バブルソートは、隣どうしを比べて入れ替えるため、処理の流れを追いやすいです。
比較と交換の基本を学ぶには向いています。
ただし、大量データでは比較や交換が多くなりやすいため、実用では別の方法が使われることも多いです。
選択ソートは交換回数を考える入口に向いている
選択ソートは、最小値を探してから入れ替えます。
そのため、交換回数を少なくする考え方を学ぶ入口になります。
ただし、最小値を探すための比較は多くなりやすいです。
挿入ソートはほぼ並んだデータに向いている
挿入ソートは、並んだ部分に新しい値を差し込む方法です。
ほぼ並んでいるデータでは、差し込む場所が近くにあるため、少ない手間で済みやすいです。
一方で、逆順のデータでは多くの値を移動することがあります。
クイックソートは多くの場面で速くなりやすい
クイックソートは、基準値でデータを分けながら並べます。
多くの場面で速くなりやすい方法です。
ただし、基準値の選び方が悪いと、効率が下がることがあります。
マージソートは安定して並べたい場面に向いている
マージソートは、データを分けて、並べながら合体する方法です。
安定して速く並べやすいのが特徴です。
ただし、合体するときに一時的な作業場所が必要になることがあります。
疑似言語ではどう書く？
基本情報技術者試験では、疑似言語でソート処理が出ることがあります。
疑似言語とは、特定のプログラミング言語ではなく、処理の流れを分かりやすく書くための表し方です。
ここでは、考え方をつかむための簡単な例を見ます。
なお、基本情報技術者試験の疑似言語では、代入を「←」で表します。
「x ← 5」は、「右側の5を、左側のxに入れる」という意味です。
本文では、代入を「=」では説明しません。
バブルソートの疑似言語
バブルソートでは、隣どうしを比べて、必要なら入れ替えます。
配列 A を小さい順に並べる
i を 1 から データ数 - 1 まで 1 ずつ増やす
j を 1 から データ数 - i まで 1 ずつ増やす
もし A[j] が A[j + 1] より大きいなら
一時 ← A[j]
A[j] ← A[j + 1]
A[j + 1] ← 一時
もし終わり
j のくり返し終わり
i のくり返し終わりなお、試験問題では、この3行の入れ替え処理を「A[j] と A[j + 1] を入れ替える」のように、1行の言葉でまとめて書いていることもあります。
その場合も、意味は同じです。A[j]の値とA[j + 1]の値を交換していると考えましょう。
ここでは、A[j]とA[j + 1]が隣どうしの値です。
jが変わるたびに、見ている場所が1つ右へ移ります。
教材では、本文では「1番目」「2番目」と表示すると、初心者でも見やすくなります。
ただし、実際の試験では、問題文で配列番号が何番から始まるかを必ず確認してください。
選択ソートの疑似言語
選択ソートでは、まだ並んでいない範囲から一番小さい値を探します。
配列 A を小さい順に並べる
i を 1 から データ数 - 1 まで 1 ずつ増やす
最小位置 ← i
j を i + 1 から データ数 まで 1 ずつ増やす
もし A[j] が A[最小位置] より小さいなら
最小位置 ← j
もし終わり
j のくり返し終わり
もし 最小位置 が i と違うなら
一時 ← A[i]
A[i] ← A[最小位置]
A[最小位置] ← 一時
もし終わり
i のくり返し終わりこの処理では、最小位置が大切です。
最小位置は、「今のところ一番小さい値がある場所」です。
最後に、A[i]とA[最小位置]を入れ替えることで、i番目が確定します。
挿入ソートの疑似言語
挿入ソートでは、取り出した値を、並んだ部分の正しい位置へ差し込みます。
配列 A を小さい順に並べる
i を 2 から データ数 まで 1 ずつ増やす
挿入値 ← A[i]
j ← i - 1
j が 1 以上 かつ A[j] が 挿入値 より大きい間
A[j + 1] ← A[j]
j ← j - 1
くり返し終わり
A[j + 1] ← 挿入値
i のくり返し終わりここでは、挿入値をどこに入れるかがポイントです。
A[j]が挿入値より大きい間、A[j]を右へずらします。
空いた場所に挿入値を入れると、左側の並んだ範囲が広がります。
ループの入れ子の見方
ソートでは、ループの中にループがある形がよく出ます。
これを入れ子のループといいます。
入れ子のループでは、外側のループが1回進む間に、内側のループが何回も動くことがあります。
初心者は、ここで回数を間違えやすいです。
読むときは、次の順番で見ると分かりやすいです。
- 外側のループが何を表しているかを見る
- 内側のループがどこを見ているかを見る
- 1回の比較で配列がどう変わるかを見る
- 外側のループが1回終わったとき、どこまで確定したかを見る
トレース表でソートを追う
ソートの問題を解くときは、トレース表を使うと分かりやすくなります。
トレース表とは、処理の途中で変数や配列がどう変わるかを書き出す表です。
頭の中だけで追うより、手を動かして書いた方がミスを減らせます。
トレースの基本から確認したい方は、基本情報技術者試験の疑似言語とトレース入門も参考にしてください。
比較している位置を書く
まず、どの位置を比較しているかを書きます。
たとえば、バブルソートなら「1番目と2番目」「2番目と3番目」のように書きます。
| 手順 | 比較する位置 | 比較する値 |
|---|---|---|
| 1 | 1番目と2番目 | 5と2 |
| 2 | 2番目と3番目 | 5と8 |
位置を書くことで、配列のどこを見ているのかが分かります。
交換したかどうかを書く
次に、交換したかどうかを書きます。
| 手順 | 比較する値 | 交換 |
|---|---|---|
| 1 | 5と2 | する |
| 2 | 5と8 | しない |
比較しただけなのか、実際に入れ替えたのかを分けて書くことが大切です。
配列の状態を書く
交換した後は、配列の状態を書きます。
| 手順 | 処理 | 配列の状態 |
|---|---|---|
| 最初 | 開始 | 5, 2, 8, 1, 4 |
| 1 | 5と2を交換 | 2, 5, 8, 1, 4 |
| 2 | 5と8は交換しない | 2, 5, 8, 1, 4 |
配列の状態を書かないと、次の比較でどの値を見るのかを間違えやすくなります。
確定した範囲を書く
最後に、どこまで確定したかを書きます。
バブルソートなら、1回の大きな流れが終わると、後ろの値が確定します。
選択ソートなら、先頭から順に確定します。
確定した範囲を意識すると、もう見なくてよい場所が分かります。
教材でも、確定した範囲を色で分けると、試験問題の読み方につながります。
基本情報技術者試験ではどう出る？
基本情報技術者試験では、ソートの処理を読んで、途中の状態や結果を答える問題が出ることがあります。
特に大切なのは、疑似言語を読んで、配列の中身を正しく追うことです。
どこを比較するかを問う問題
問題文で、ソート処理の途中が示されることがあります。
そのうえで、次に比較する場所を問われることがあります。
このときは、添字や配列の何番目を見ているかを確認します。
本文や教材では「1番目、2番目」と表示していても、試験では配列番号が0から始まる場合や、1から始まる場合があります。
問題文の前提を必ず確認しましょう。
交換後の配列を問う問題
比較したあと、配列がどう変わるかを問われることがあります。
この場合、交換した2つの値だけを入れ替えます。
関係ない場所まで変えないように注意しましょう。
たとえば、5と2を交換するなら、次のようになります。
交換前：5, 2, 8, 1, 4
交換後：2, 5, 8, 1, 4ループ回数を問う問題
ソートでは、ループの回数が問われることもあります。
特に、入れ子のループでは、内側のループが何回動くかを間違えやすいです。
外側のループが1回進むたびに、内側のループの範囲がどう変わるかを見ましょう。
アルゴリズムの特徴を問う問題
ソートの特徴を問う問題もあります。
たとえば、次のような内容です。
- 隣どうしを比べて入れ替えるのはどのソートか
- 最小値を探して先頭に置くのはどのソートか
- ほぼ並んだデータに向いているのはどのソートか
- 分けてから合体するのはどのソートか
特徴を丸暗記するより、動きを思い出せるようにしておくと答えやすくなります。
初心者が間違えやすい点
ソートは、考え方そのものよりも、途中の追い方で間違えやすいです。
ここでは、初心者が特に間違えやすい点を整理します。
比較する場所と交換する場所を混同する
比較したからといって、必ず交換するわけではありません。
比較は、値の大小を調べることです。交換は、値の場所を入れ替えることです。
たとえば、小さい順に並べたいとき、2と5を比べたら順番は合っています。この場合、比較はしますが、交換はしません。
トレース表では、「比較」と「交換」を別の欄にすると間違いにくくなります。
確定した範囲をもう一度見てしまう
ソート方法によって、確定する場所が違います。
バブルソートでは、後ろから確定していくことがあります。
選択ソートでは、前から確定していきます。
確定した範囲をもう一度見てしまうと、余計な比較をしたり、配列の状態を間違えたりします。
入れ子のループで回数を間違える
入れ子のループでは、外側と内側を混同しやすいです。
外側のループは、全体の大きな回数を表すことが多いです。
内側のループは、その中で実際に比較する場所を動かすことが多いです。
読むときは、外側のループを1回だけ固定して、内側がどう動くかを先に見ましょう。
ソートの向き不向きを丸暗記しようとする
ソートの向き不向きは、丸暗記だけでは忘れやすいです。
なぜ向いているのかを、動きとセットで考えましょう。
- バブルソート：隣どうしなので分かりやすい
- 選択ソート：最小値を選ぶので交換回数を考えやすい
- 挿入ソート：並んだ部分に差し込むので、ほぼ並んだデータに強い
- クイックソート：基準値で分けるので、多くの場面で速くなりやすい
- マージソート：分けて合体するので、安定して並べやすい
動きを説明できるようになると、特徴も自然に覚えやすくなります。
確認問題
最後に、ソートの基本を確認しましょう。
答えをすぐ見るのではなく、頭の中で動きを思い出してから確認すると効果的です。
バブルソートは何を比べますか？
バブルソートは、隣どうしの値を比べます。
小さい順に並べる場合、左の値が右の値より大きければ入れ替えます。
たとえば、5と2を比べた場合、5の方が大きいので入れ替えます。
挿入ソートはどんなデータに向いていますか？
挿入ソートは、ほぼ並んでいるデータに向いています。
すでに並んでいる部分に、新しい値を正しい場所へ差し込む方法だからです。
少しだけ順番がずれているデータなら、移動が少なく済みやすいです。
比較回数と交換回数の違いは何ですか？
比較回数は、値どうしを比べた回数です。
交換回数は、値を入れ替えた回数です。
比較しても、順番が合っていれば交換しないことがあります。
そのため、比較回数と交換回数は同じとは限りません。
まとめ
ソートアルゴリズムは、データを目的に合った順番に並べる処理です。
商品を価格順に並べる、ファイルを更新日順に並べる、ランキングを点数順に並べるなど、身近な場面でよく使われています。
基本情報技術者試験では、ソート名を覚えるだけでなく、処理の途中を追う力が大切です。
特に、次の点を意識しましょう。
- どの値を比較しているか
- 交換したかどうか
- 配列の中身がどう変わったか
- どこまで確定したか
- 比較回数、交換回数、移動回数がどう増えたか
バブルソートは、隣どうしを比べて入れ替える方法です。仕組みを理解しやすい反面、大量データには向きにくいです。
選択ソートは、一番小さい値を探して先頭に置く方法です。交換回数は少なめにしやすいですが、比較回数は多くなりやすいです。
挿入ソートは、並んだ部分に新しい値を差し込む方法です。ほぼ並んだデータに向いています。
クイックソートは、基準値で小さい側と大きい側に分ける方法です。多くの場面で速くなりやすいですが、基準値の選び方で効率が変わります。
マージソートは、データを分けて、並べながら合体する方法です。安定して速く並べやすいのが特徴です。
ソートは、暗記だけで理解するものではありません。
スタートボタンや次へボタンで1ステップずつ動きを見ながら、比較、交換、配列の変化を追うことで、基本情報技術者試験の問題にも対応しやすくなります。