解説

整列の状態遷移から使用したアルゴリズムを特定する問題です。図（[DIAGRAM_HERE]）の状態遷移を見ると、各ステップで隣接する要素との比較・交換が行われているのではなく、ある位置に要素が「挿入」されていく様子が示されていると推測されます。挿入ソート（Insertion Sort）は「整列済み部分に新しい要素を適切な位置に挿入していく」アルゴリズムで、左から右に向かって整列済み領域が拡大します。各ステップで整列済み部分の末尾に新しい要素が追加され、その要素を適切な位置に移動させます。図の状態遷移のパターンが挿入ソートの特徴と一致します。選択肢 c が正解です。

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

選択肢 ア

クイックソートは基準値（pivot）を選んでグループ分割を行うアルゴリズムです。状態遷移で分割のたびに基準値が確定位置に移動するパターンになりますが、図の遷移とは異なります。

選択肢 エ

ヒープソートはヒープ構造（完全2分木）を使ったアルゴリズムです。ヒープ化（Heapify）→最大値抽出のプロセスを繰り返しますが、その状態遷移は挿入ソートとは明確に異なるパターンです。

解くときのポイント

ソートアルゴリズムの状態遷移パターンで識別：挿入ソート＝左から整列済み領域が拡大、バブルソート＝各パスで右端から最大値が確定、クイックソート＝pivot確定→左右のグループ分割、選択ソート＝各パスで最小値が左端に確定。状態変化のパターンを試験で問われる。