5

4

1

3

6

2

ア	1 3 2 4 5 6
イ	1 3 4 2 5 6
ウ	4 1 5 3 2 6
エ	4 1 5 3 6 2

（出展：平成12年度秋期　（旧）2種情報処理技術者試験より）

解答：　イ

解説：　

　バブルソートに関する問題です。

　並び替えの方法にはさまざまなアルゴリズムがありますが，バブルソートは，その中でも基本的で，かつ最も簡単で単純な方法です。

　バブルソートでは，片側から順に，隣り合う２つの値の大小を比較し，並べ替えを行ないます。 これを，繰り返すことで，すべての要素を並べ替えることができます。 アルゴリズムは簡単ですが，比較，入れ替えの回数が非常に多くなるのが欠点で，最大 n（n − 1）／ 2 となります。

　ちなみに，「バブル」ソートの名称は，要素が泡のように浮かんでくるように見えることに由来しています。

　右にバブルソートが実行される様子をあげます。 3つの要素「5」「1」「3」を，左から小さい順（逆に言うと，右から大きい順）に並べ替えようとしています。 要素数が 3つなので，3 × 2 ／ 2 ＝ 3回の比較で並び替えが完了します。 それぞれの比較・入れ替えの様子を説明すると，
［1回目］
「5」と「1」を比較，右側の要素の方が小さいので，入れ替える。
［2回目］
「5」と「3」を比較，右側の要素の方が小さいので，入れ替える。 先頭から最後の要素まで比較・入れ替えが完了したので，最右の要素「5」は一番大きい値であることが確定する。
［3回目］
「1」と「3」を比較，右側の要素の方が小さいので，そのままにする。 最右の要素「5」はすでに確定しているので，真ん中の「3」が 2番目に大きい要素であることが確定する。 同時に，「1」が最も小さい要素であることも確定する。 以上で並び替え完了。

　では，実際に問題文のデータ列をバブルソートで並べ替えしてみましょう。 比較している要素を緑色，入れ替えしている要素を，オレンジ色の枠線で表します。

バブルソートアルゴリズムは，

特徴 ： 隣り合う2つの値の大小を比較し，泡（バブル）のように入れ替えていく
長所 ： アルゴリズムが単純
短所 ： 計算回数が多い

このアルゴリズムによる計算回数は，n（n − 1）／ 2 となる。 この式を忘れたときは，要素数が少ないケースをシミュレーションして考えること。
　　→ 2要素のソート ： 1回で完了［ 2 × 1 ／ 2 ＝ 1 ］
　　→ 3要素のソート ： 3回で完了［ 3 × 2 ／ 2 ＝ 3 ］
　　→ 4要素のソート ： 6回で完了［ 4 × 3 ／ 2 ＝ 6 ］