バブルソートの途中経過
出典: 令和5年度 秋期 応用情報技術者試験 午前 問6 (IPA)
あるデータ列を整列したら状態 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 つずつ末尾に移っていくので、バブルソートです。
- エ: ヒープソートは最初にヒープを作るので、1 回目の後の並びがヒープの形になり、この途中経過とは合いません。
ポイント
- 状態 0 → 1 で、最大の 9 が末尾に移動 し、それ以外の並びはほぼそのまま (隣同士の交換で 9 だけが後ろへ) です。
- 状態 1 → 2 で、次に大きい 6 が末尾から 2 番目 に移動しています。
- 隣り合う要素を比べて交換しながら、大きい値を 1 つずつ末尾へ送っていくのは バブルソート の動きです。