あるデータ列を整列したら状態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
正答3
解説
正解は3です。
整列の途中経過から、どのアルゴリズムを使ったかを見分ける問題です。
状態0から状態1で最大値9が末尾へ移り、状態2で次に大きい6が末尾から2番目へ移っています。
【計算】
状態0の3、5、9、6、1、2で、隣り合う2つを左から比べ、左が大きければ交換します。
3と5、5と9は交換しません。
9と6を交換し、続けて9と1、9と2を交換します。
結果は3、5、6、1、2、9で、状態1と一致します。
同様に状態1で比べると、6と1、6と2が交換され、3、5、1、2、6、9となり状態2と一致します。
【選択肢別解説】
1：× クイックソートは、基準値（ピボット）を選んで、それより小さい値と大きい値のグループに分けていく方法です。
1回の操作で最大値だけが末尾に移り、ほかの並びがほぼ保たれるという変化にはなりません。
2：× 挿入ソートは、先頭から整列済みの範囲を広げていく方法です。
状態0からは3、5、9が整列済みとなり、次に6を挿入して3、5、6、9、1、2となるはずなので、状態1と一致しません。
3：○ バブルソートは、隣り合う要素の比較と交換を繰り返し、1回の走査で最大値を末尾まで移動させます。
状態1と状態2の変化が、この手順をたどった結果と一致します。
4：× ヒープソートは、まず全体をヒープ（親が子以上になる木構造）に組み直してから最大値を末尾に移します。
残りの部分はヒープの順に並び替わるので、元の並びが保たれた状態1にはなりません。
【ポイント】
「1回ごとに最大値（または最小値）が端に確定し、残りの相対的な順序がほぼ保たれる」のがバブルソートの特徴です。
挿入ソートは先頭側から、バブルソートは末尾側から整列済みの範囲が広がると対比して覚えます。