問題
次の擬似言語プログラムの実行後、配列dataの内容はどれか。
整数型の配列: data ← {4, 1, 3, 2}
整数型: i ← 2
while (i ≦ 4)
整数型: key ← data[i]
整数型: j ← i - 1
while (j ≧ 1 and data[j] > key)
data[j + 1] ← data[j]
j ← j - 1
endwhile
data[j + 1] ← key
i ← i + 1
endwhile
選択肢
- 1{4, 3, 2, 1}
- 2{1, 2, 3, 4}
- 3{2, 3, 4, 1}
- 4{1, 3, 2, 4}
正解
2. {1, 2, 3, 4}
詳しい解説を見る解説を閉じる
解説
このプログラムは挿入ソートであり、i番目の要素をkeyとして取り出し、整列済みの左側部分でkeyより大きい要素を右へ1つずつずらしてから、空いた位置にkeyを挿入する。トレースすると、i＝2でkey＝1を先頭に挿入して{1, 4, 3, 2}、i＝3でkey＝3を4の前に挿入して{1, 3, 4, 2}、i＝4でkey＝2を3の前に挿入して{1, 2, 3, 4}となる。最終的に昇順に整列され、「{1, 2, 3, 4}」が正解である。降順は内側ループの比較条件data[j]＞keyを逆に読んだ場合の誤りであり、ウと「{1, 3, 2, 4}」は途中経過の配列を最終結果と取り違えた誤答である。頻出ポイント：挿入ソートは「左側は常に整列済み」という性質を保って進む点が特徴で、ほぼ整列済みのデータには高速に働くことも併せて問われやすい。
一問一答
科目A 180問+科目B 60問