対話式で記憶に残る応用情報：バブルソート

こんにちは、おゆかよです。
この記事では、バブルソートがどのようなアルゴリズムか、具体的な挙動を会話形式で学ぶことができます＾＾

前回の記事：

試験の問題と解答

問題：

問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回ずつの操作で大きい数字が左から右に「ぷか〜」と浮かんでいく感じ？

博士

そう、そのイメージばっちりだよ！この問題でも最初の状態0では「3, 5, 9, 6, 1, 2」だね？
9が最後に行って、次は6が9の前に行って…って、右側が徐々に整っていってるんだ。

わたし

なるほど！クイックソートやヒープソートみたいに「パッと並び替えた感じ」がないのは、バブルソートだからなんだね！

博士

その通り。バブルソートは、データの移動がじわじわ進むから、「交換の様子が見える」のが特徴だよ。

わたし

動きが地味だけど、見ててわかりやすい。私にもできそう！

博士

ちなみに、ソートが終わった状態を見て「これはどのソートかな？」って当てる問題、たまに出るから、動きの特徴は覚えておこうね！

出典：
応用情報技術者試験令和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

ア：クイックソート
イ：挿入ソート
ウ：バブルソート
エ：ヒープソート

答え：ウ