応用情報技術者試験 令和4年度 秋期 午前 問6

【正解】エ

図では、外側のループでiを1からn－1まで増やし、内側のループでjをnからi＋1まで1ずつ減らしています。そして、隣り合うA[j]とA[j－1]を比較し、右側のA[j]の方が小さい場合に両者を交換します。この操作を右端から左方向へ繰り返すと、小さい値が泡のように左へ移動するため、バブルソートに該当します。

例えば、A＝［4、1、3、2］では、i＝1のとき、j＝4で2と3を交換して［4、1、2、3］、j＝3では交換せず、j＝2で1と4を交換して［1、4、2、3］となり、最小値1が先頭に確定します。続いてi＝2では［1、2、4、3］、i＝3では［1、2、3、4］となります。

アのクイックソートは誤りです。基準値を選び、それより小さい値と大きい値に配列を分割して再帰的に整列する方法です。

イの選択ソートは誤りです。未整列部分から最小値などを探し、未整列部分の先頭の要素と交換する方法です。

ウの挿入ソートは誤りです。整列済み部分の適切な位置に、未整列部分から取り出した要素を挿入する方法です。

【ポイント】 バブルソートは隣接要素の比較と交換を繰り返す整列法です。 平均・最悪時間計算量はO（n²）であり、図のように等しい要素を交換しない方式では安定ソートになります。