問 題
次の要素 S[1]〜S[5] に格納されたデータを図のアルゴリズムを用いて並び替えた。このとき、要素間でデータの交換を行った回数はいくらか。
1. 3 回
2. 4 回
3. 5 回
4. 6 回
5. 7 回
正解 (4)
解 説
いわゆる「バブルソート」です。
まず S[1] と S[2] の比較、左側の方が大きかったら交換という操作を行います。i が 4 までなので S [4] と S [5] の比較まで行っています。その後 j が 減っているため、i が 3 までとなるため、また S[1] と S[2] の比較をしていって、今度は S[3]とS[4]までの比較します。以下、交換するものがなくなるまで操作を繰り返し、大きいものを右へ右へと押しやっていくようなアルゴリズムです。
結果として
交換1:「70 ↔ 40」 50,40,70,80,20
交換2:「80 ↔ 20」 50,40,70,20,80
交換3:「50 ↔ 40」 40,50,70,20,80
交換4:「70 ↔ 20」 40,50,20,70,80
交換5:「50 ↔ 20」 40,20,50,70,80
交換6:「40 ↔ 20」 20,40,50,70,80
という流れを経て、データが小さい順に並びます。交換回数は 6 回です。
以上より、正解は 4 です。
コメント