情報処理安全確保支援士試験 情報処理安全確保支援士試験 令和5年度秋期 午前Ⅰ 問3: あるデータ列を整列したら状態 0 から順に状態 1，2，・・・，N へと推移した。整列に使ったアルゴリズムはどれか。 状態 0 3，5，9，6，1，2 状態 1

問題本文

あるデータ列を整列したら状態 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

選択肢

• ア.クイックソート
• イ.挿入ソート
• ウ.バブルソート
• エ.ヒープソート

正解

ウ. バブルソート

解説

状態遷移を見ると、最大値9が末尾へ、次に大きい6がその手前へと、大きい値が後方に1つずつ確定していく。これは隣接要素を比較交換して最大値を端へ押し出すバブルソートの動きでウが正しい。挿入ソートは先頭側が整列済みになり、クイックソートは基準値で分割、ヒープソートはヒープから最大を取り出す挙動で、いずれもこの段階的な末尾確定とは異なる。

選択肢ごとの解説

• ア.クイックソートは基準値で大小に分割するため、末尾から順に確定する遷移にならない。
• イ.挿入ソートは先頭側から整列済み領域が広がる動きで、末尾確定型の本問とは異なる。
• ウ.大きい値が末尾へ1つずつ確定する隣接交換の挙動はバブルソートそのもので正しい。
• エ.ヒープソートはヒープ構築後に最大値を取り出すため、この比較交換の過程と一致しない。