令和5年度 秋期 午前 問6

✓ これが正解ウバブルソート

解説

右端から順に大きい値が確定していきます。

設問は、整列の途中経過が状態 0 から順に推移した様子を示し、使われた整列アルゴリズムを選ばせています。途中経過から見分けるときは、どちら側から値が確定していくかを見ます。最初の推移では、いちばん大きい 9 が右端へ移り、それ以外の値は元の並びのまま一つずつ左へずれています。次の推移では、残りの中で大きい 6 が右から二番目に収まっています。つまり一回の走査ごとに、右端から順に確定していく形です。これは隣り合う二つを比べて大きいほうを右へ送り出す整列のふるまいで、送り出される値が相手を一つずつ左へ押しやるため、途中の並びが元の順を保ったままずれます。正解はバブルソートです。

ほかの選択肢はなぜ違うのか

• アクイックソート：クイックソートは基準となる値を決めて、それより小さい側と大きい側に振り分けます。一度の分割で値が遠くの位置まで飛ぶので、示された推移のように隣へ一つずつ寄っていく形にはなりません。
• イ挿入ソート：挿入ソートでは、整列済みの部分が左から一つずつ伸びていきます。示された推移では最初の段階で右の端が先に定まっているため、確定していく向きが反対です。
• エヒープソート：ヒープソートは、いったんデータを木の構造に組み替えてから最大の値を取り出します。組み替えの段階で元の順序の面影が失われるので、途中の状態が示されたような形で残りません。