応用情報技術者試験 令和５年秋期 問６
あるデータ列を整列したら状態0から順に状態1，2，・・・，Nへと推移した。整列に使ったアルゴリズムはどれか。
状態0 3，5，9，6，1，2
状態1 3，5，6，1，2，9
状態2 3，5，1，2，6，9
・
・
状態N 1，2，3，5，6，9ア：クイックソート イ：挿入ソート
出典 IPA公開[過去問題]：https://www.ipa.go.jp/shiken/mondai-kaiotu/ps6vr70000010d6y-att/2023r05a_ap_am_qs.pdf
ウ：バブルソート エ：ヒープソート
クイックソートとは
データ列の中で基準値(多くは中間値)を決めて、それよりも「小さいグループ」と「大きいグループ」を作って分割します。それぞれのグループの中に複数の値があれば、同じようにグループの中で基準値を決めてそれよりも「小さいグループ」と「大きいグループ」に再度分割します。これをグループのデータ列数が１になるまで続けることで並び替えを行います。
挿入ソートとは
データ列を「整列済」と「未整列」に分割して、「未整列」エリアの先頭データを取り出して、「整列済」エリアの適切な場所に挿入していくことで「整列済」エリアを徐々に拡大させていく方法です。
この方法で整列した場合、データ列の最後まで１週した段階で正しい並び[１，２，３，５，６，９]になるかと思います。
バブルソートとは
データ列の隣り合うデータ同士を比較して入れ替えて整列する方法です。先頭から始めて最後まで比較すると２週目は先頭から２番目の位置から始めて最後まで比較して整列していきます。３週目は先頭から３番目の位置から同様に比較して整列していくのをデータ列の最後の１つ手前位置まで繰り返します。
この方法で整列した場合、複数周回整列を行うことになるので１週目が終わったであろう状態１では「３，５，６，１，２，９」になります。
ヒープソートとは
未整列のデータ列を木構造で整列(親値≦子値もしくは親値≧子値)して根の値を順番に取り出すことで整列する方法です。
状態０と状態１を見ると「３，５」はそのままですが、「９，６，１，２」の順番が「６，１，２，９」になっています。バブルソートを実行すると次のようにデータ列の中身が整列されていきます。
※黄色で塗りつぶした部分が入替対象になる箇所です。
正解は「ウ：バブルソート」となります。