応用情報技術者試験 令和４年秋期 問６
未整列の配列Ａ[ｉ](ｉ=1，2，…，ｎ)を，次の流れ図によって整列する。ここで用いられる整列アルゴリズムはどれか。
ア：クイックソート イ：選択ソート
ウ：挿入ソート エ：バブルソート
出典 IPA公開[過去問題]：https://www.ipa.go.jp/shiken/mondai-kaiotu/gmcbt80000008smf-att/2022r04a_ap_am_qs.pdf
クイックソートとは
複数のデータを整列するアルゴリズムの１つです。複数あるデータの中から基準値を決めて、小さいグループと大きいグループに分割する作業をグループの中のデータが１つになるまで繰り返していく方法です。
次のような手順で整列を行っていきます。
- データの中から基準値を決めます
- 複数のデータを基準値に対して小さいグループ(基準値未満)と大きいグループ(基準値以上)に分割します
- 分割したグループにあるデータが1つになるまで手順1・手順2を繰り返します。
- 分割が終わったグループをつなげていきます。
分割の流れを下図に表しています(※各グループの基準値は黄色で表しています)。
フローチャートなどでクイックソートを表す場合は配列に対して左右からデータをチェックしていき、基準値と比べていきます。例えば昇順に並べたい場合、左からチェックして行ったときは基準値より小さいデータであれば無視して次のデータをチェックし、基準値より大きいデータであれば交換対象とします。また、右からチェックして行ったときは基準値より大きいデータであれば無視して次のデータをチェックし、基準値より小さいデータであれば交換対象とします。左右からチェックして行ったデータの交換対象となったデータを入れ替えるのを繰り返すことで基準値に対して小さいグループ・大きいグループを分割していきます。
選択ソートとは
複数のデータを整列するアルゴリズムの１つです。複数あるデータの中から最小値を探して未整列範囲の先頭と入れ替えるのを最後の１つ手前のデータまで繰り返していく方法です。
次のような手順で整列を行っていきます。
- 先頭の1つ目以降にあるデータの中から最小値を見つけます。
- 見つけた最小値を先頭にあるデータと入れ替えます(ここで先頭が最小値だと決まります)。
- 先頭から2つ目以降にあるデータの中から最小値を見つけます。
- 見つけた最小値を先頭から2つ目にあるデータと入れ替えます。
- 先頭から3つ目以降にあるデータの中から最小値を見つけます。
- 見つけた最小値を先頭から3つ目にあるデータと入れ替えます。
- 前の手順と同じように1つずつ範囲を狭めながら最後の1つ手前のデータになるまで最小値を見つけてはデータを入れ替えていきます。
下図のように最小値との入れ替え対象になる位置を１つずつ動かしていきます。
フローチャートなどで選択ソートを表す場合は最小値と入れ替える先頭位置を１つずつ動かしていき、これをデータの一番最後の1つ手前まで動かしていきます(一番最後のデータは比較も何も対象データが1つしかないので入れ替える必要はありません)。
※降順に並び替える場合は、最大値と入れ替えることになります。
挿入ソートとは
複数のデータを整列するアルゴリズムの１つです。複数あるデータを整列済みエリアと未整列エリアに分けて管理して未整列エリアにあるデータを１つずつ整列済みエリアに動かすと同時に整列する方法です。
次のような手順で整列を行っていきます。
- 未整列エリアの先頭データと整列済み範囲のデータを比較します。
- (昇順の場合は)整列済みエリアから取り出したデータの方が未整列エリアの先頭データより大きければ入れ替え、(降順の場合は)整列済みエリアから取り出しデータの方が未整列エリアの先頭データより小さければ入れ替えます。
- 手順1～2を未整列エリアを1つずつ後ろに狭めながら最後まで繰り返し行います。
もう少し詳しく流れを言うと、未整列エリアの先頭データを整列済みエリアの最後尾から順に前方向にデータを比較して入れ替えていきます。例えば上図の４段目の処理の動きだと下図のように未整列エリアの先頭である「２」を整列済みエリアの最後尾から前方向にバブルソートをしていきます。入れ替えられなくなったら未整列エリアの先頭位置を１つ動かして同様の処理をしていきます。
フローチャートなどで挿入ソートを表す場合は、未整列エリアの先頭位置にあるデータを、未整列エリアの最後尾からチェックして行き、入れ替えられなくなるまで繰り返し入れ替えていきます。入れ替えられなくなったら未整列範囲の先頭位置を１つ動かして同様の作業を行っていきます。
バブルソートとは
フローチャートなどでバブルソートを表す場合は必ず現在位置のデータを次のデータを比べる作業を行います。※ただし処理の方法によっては現在位置に対して「次のデータ」と比較する場合と、「手前のデータ」と比較する場合がありますが、どちらにしても現在位置と隣り合うデータを比較しているのは同じです。
先ほど説明したように整列アルゴリズムや並び替えアルゴリズムにはそれぞれに特徴があります。本問で注目すべきは比較部分です。
比較部分を見ると「Ａ[ｊ]：Ａ[ｊ－１]」となっており、常に隣り合う２つの値を比較しているのがわかります。このように隣り合う値同士を比較するのはバブルソートの特徴です。
また、この問題よりオーソドックスな方法として変数ｊのループ条件を「ｊ：ｉ＋１，１，ｎー１」にして、比較部分を「Ａ[ｊ]：Ａ[ｊ＋１]」とするものもあります。ただ、どちらの方法であったとしても必ず隣り合う値同士を比較していることに変わりありません。
さらに余談にはなりますが、万が一、科目Ｂでバブルソートが出題された場合で比較部分が空欄になっている場合はループ条件がどういった書き方をしているかに注目して下さい。
正解は、「エ：バブルソート」です。