質問: `基本情報技術者` n個のデータをバブルソートを用いて整列するとき、 データ同士の比較回数は幾らか? 【答え】 n(n-1) ─── 2 具体例でバブルソートは隣同士を比較するので、例えばデータが4件なら、6回となるので、選択肢の式のnに4を代入して6になるものを探すとあるのですが、よくわからないため、ご教授ください。
回答: この4月に基本情報を受ける者です。 バブルソートは右端から2つの数字を比較して行き、左端に一番小さな数字を持っていくアルゴリズムになります。(言葉での説明は難しいですね。) 例として 4件のデータをバブルソートする場合、 "4231" と並んでいるとします。 最初に3と1を比較して、1の方が小さいので数字を入れ替えます。 "4213" 次に2と1を比較して、1の方が小さいので数字を入れ替えます。 "4123" 最後に4と1を比較して、1の方が小さいので数字を入れ替えます。 "1423" これで一番小さい数字(1)が左端に来たため、また右端から数字を比較します。 はじめに2と3を比較して、3の方が大きいので数字は入れ替えません。 "1423" 次に4と2を比較して、2の方が小さいので数字を入れ替えます。 "1243" これで2巡目が終わりました。 最後に4と3を比較して、3の方が小さいので数字を入れ替えます。 "1234" バブルソートが完了しました。 以上がバブルソートの基本的な考え方になります。 そのため、データ数がN個の場合は、N未満の数字の合計になります。 データ数が4の場合は、4未満の数字(3+2+1)の合計(6)になります。 ちなみに"n(n-1)/2"と言うのは三角数の表し方になります。 間違った説明をしますと、階乗(4!=4*3*2*1=24等のこと)の足し算verだと思って頂ければ大丈夫かと存じます。 詳しく知りたい場合は「三角数とは」で検索してみてください。 試験勉強頑張ってくださいね。