情報活用編プラス
第3章「コンピュータとプログラミング」
IP02-11
実践プログラム④ 整列アルゴリズム 選択法
5. ✏️極端なデータの並び替えと比較回数 ( 5 / 11 )
学習の目的
1. 同じデータ数で選択法を実行した結果について
2. 極端なデータの並び替え
3. 選択法の比較回数
前のスライドではデータ数が8のときの比較回数と交換回数について調べました。
学習モードも含めて、同じデータ数で4回実行しましたが気づいたことはありましたか？
はい、比較回数は4回とも同じでしたが、交換回数は違うものもありました。
そうそう、俺も同じで比較回数はみんな同じだったけど、交換回数は同じものと違うものがあったな。
そうですね。４回やった結果では、「比較回数は同じ回数」、「交換回数はデータによって異なる」という結果になったということですね。
それがどんなデータでもそうなのか、極端なデータで比較回数と交換回数がどうなるか調べてみましょう。
データを並び替えるときに極端な並びのデータとはどんなデータだと思いますか？
極端って何が極端なんですか？
そうですね。極端なデータとは、整列するときに比較回数が多かったり、交換が毎回発生するなどの処理時間がかかる最悪の並びのデータ、それに対し比較回数が少なく、交換が1回も発生しない一番処理時間がかからない最良の並びのデータのことです。
時間がかかるってことは、実行する命令数が多いってことですか？
いいところに目をつけましたね。
この場合は「実行する命令数が多い＝処理時間がかかる」ということになります。
じゃあ、処理時間がかかる最悪の並びのデータとは、昇順に並び替えている場合は、大きい順に並んでいる場合ですか？
正解です。並び替える順と逆順に並んでいた場合は、一番処理量が多くなります。逆に、並べ替えたい順にすでに並んでいた場合は処理量が少なくなります。
えっ？すでに順番に並んでいるのであれば、何もしなくていいんじゃないの？
人が見れば、順番に並んでいることがわかってもコンピュータは全部を同時に見ることはできないので、順番に並んでいることが確定するまで処理を行います。
それでは次の2つのデータに対して選択法を行ったときの問題について答えましょう。
次の5つのデータが入った配列をデータの昇順に並び替えます。
並び替えが終わるまでの比較回数と交換回数を答えてください。
これは降順に並んでいるデータなので、最悪の場合ってことですね。
比較回数を答えてください。
交換回数を答えてください。
次の5つのデータが入った配列をデータの昇順に並び替えます。
並び替えが終わるまでの比較回数と交換回数を答えてください。
これは昇順に並んでいるデータなので、最良の並びのデータってことね。
比較回数を答えてください。
交換回数を答えてください。
「並べたい順とは逆に並んでいる最悪の並びのデータ」と、「並べたい順にすでに並んでいる最良の並びのデータ」を選択法で並び替えた場合の比較回数と交換回数を比べてわかったことをまとめましょう。
最大 500 文字
選択法の比較回数について考えます。次の図はデータ数と比較回数を求めた図です。
基準が0番目の時に1回比較し条件に応じて交換を行えば並べ替えが完了します。
そのため、データ数が2のときは並べ替えが終わるまでに比較する回数は1回です。
基準が0番目の時に
を行うため比較回数は2回。
基準が1番目の時に
を行うため比較回数は1回。
そのため、データ数が3のときは並べ替えが終わるまでに比較する回数は3回です。
基準が0番目の時に
を行うため比較回数は3回。
基準が1番目の時に
を行うため比較回数は1回。
基準が2番目の時に
を行うため比較回数は1回。
そのため、データ数が4のときは並べ替えが終わるまでに比較する回数は6回です。
データ数と比較回数をまとめていくと次のようになります。
上の計算を見てなにか法則に気づきませんか？
比較回数の合計は、データ数-1から1までを合計していますね。
そうですね。では、データ数が6のときの比較回数は何回でしょうか？
6から1を引けばいいんだから⋯5 + 4 + 3 + 2 + 1 = 15なので、15回ですか？
はい、そうです。比較回数の合計は計算式で求めることもできます。
選択法の比較回数は次の計算式で求めることができます。
データ件数がn件のときの選択法の比較回数の求め方
比較回数 = n × ( n - 1 ) ÷ 2
例えば、データ数が8件のときは次のように比較回数は計算します。
8件のときの比較回数 = 8 × ( 8 - 1 ) ÷ 2 = 8 × 7 ÷ 2 = 28回
ホントだ。同じ28回になった。
でも、なんか見たことのある式だな⋯
バブルソートと同じ計算式ですね。
データ数が100件のとき、選択法での比較回数が何回か答えてください。
※この再現版では提出は行いません（送信先は未接続です）
