高度情報処理技術者試験・情報処理安全確保支援士試験 令和5年度 秋期 午前I 問3

【正解】ウ

図の状態0は「3、5、9、6、1、2」です。バブルソートで左から隣接要素を比較し、左側の方が大きければ交換すると、9と6、9と1、9と2が順に交換され、1回目の走査後は「3、5、6、1、2、9」となります。これは状態1と一致し、最大値9が右端に確定しています。次の走査では6と1、6と2を交換して「3、5、1、2、6、9」となり、状態2と一致します。このように、各走査で未整列部分の最大値が右端へ泡のように移動して確定するので、使用されたアルゴリズムはバブルソートです。

アのクイックソートは誤りです。基準値であるピボットを選び、それより小さい要素と大きい要素に分割して、各部分を再帰的に整列する方式です。図のように右端から一要素ずつ確定するとは限りません。

イの挿入ソートは誤りです。未整列部分から要素を一つ取り出し、既に整列済みの左側部分の適切な位置へ挿入する方式です。通常は左側から整列済み範囲が広がります。

エのヒープソートは誤りです。要素をヒープ構造にして最大値又は最小値を取り出し、末尾と交換しながら整列する方式です。状態1への隣接交換の並びとは異なります。

【ポイント】 バブルソートは隣接要素の比較と交換を繰り返す単純な整列法です。 昇順で左から走査する場合、1回の走査ごとに未整列部分の最大値が右端に確定します。