AP過去問令和5年度秋期午前問6

問6(問題文)

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

ア　クイックソート

イ　挿入ソート

ウ　バブルソート

エ　ヒープソート

　この整列過程から推測されるアルゴリズムは挿入ソートです。

　挿入ソートでは、左側の部分列をすでに整列されたものとみなし、未整列の部分から要素を1つずつ取り出して、整列済み部分に適切な位置に挿入していきます。

　各状態を見てみると、右端の要素が1つずつ整列済み部分に組み込まれていく様子が見て取れます。例えば、

状態0では未整列のままです。

状態1では右端の9が整列済み部分の右端に移動しています。

状態2では6の左に1と2が移動し、6と9が整列済みに追いやられています。

　このように、後ろの要素が1つずつ正しい位置に挿入されているため、挿入ソートであると判断できます。

　したがって

イ

　が答えです。