【高校情報Ⅰ大学入学共通テスト対策】探索・整列アルゴリズム／線形探索・二分探索／交換法（バブルソート）・選択法／教科書準拠
線形探索・二分探索／交換法（バブルソート）・選択法
【資料ダウンロード】
PDFの他、パワーポイント、学習指導案 等の原本も無料提供しています。
情報教育の底上げが目的なので、資料を修正して、学校・塾（営利目的含む）の授業等で利用して頂いて問題ありません。私への連絡不要ですが、利用する際には、YouTubeチャンネル・情報Ⅰ動画教科書・IT用語動画辞典を紹介してもらえると嬉しいです。
■PowerPoint資料
https://toppakou.com/info1/download/34_35_探索・整列アルゴリズム/34_35_探索・整列アルゴリズム.pptx
■エクセル表
https://toppakou.com/info1/download/34_35_探索・整列アルゴリズム/探索回数.xlsx
■簡易学習指導案
https://toppakou.com/info1/download/34_35_探索・整列アルゴリズム/【学習指導案】34_35_探索・整列アルゴリズム.docx
【文字おこし】
今回は探索アルゴリズムの線形探索と二分探索
ソートアルゴリズムの交換法、選択法について説明していきます。
まず、探索アルゴリズムから説明していきます。
いままで、プログラミング演習で配列を扱ってきましたが、
配列の中から必要なデータを探し出すことを探索といいます。
探索には線形探索や二分探索などがあります。
まず、線形探索について説明していきます。
線形探索は配列を先頭から順に比較しながら探索値に一致する
データを探し出す探索方法になります。
例えば
このような配列があって、探したい値が82だったとします。
配列の先頭から数値を比較していきます。
まずは６１と８２を比較して不一致なので次の比較に移ります。
つぎに、１５と８２を比較して不一致なので次の比較に移ります。
そして次の比較で８２と一致するので、配列の添字２が該当箇所ということが分かります。
では、今説明したものを、フローチャート（流れ図）であらわすとこのような形になります。。
実際の数値をいれて、フローチャートを確認していきます。
まず探索値の入力で、８２を入れます。
そして、添字を０から１ずつ増やしながら、データの数分繰り返します。
この繰り返し処理で何をやるかというと、先ほどの説明と同じで
まずは６１と８２を比較して不一致なので次の比較に移ります。
つぎに、１５と８２を比較して不一致なので次の比較に移ります
そして次の比較で８２と一致するので Yesの判定に入り一致場所を表示して処理を終了します。
―――――――――――――――
今度は二分探索（にぶんたんさく）について説明していきます。
二分探索は配列の中から探索範囲を半分ずつ狭めながら目的のデータを探し出す探索方法になります。
１～９まで昇順に並べ替えられた配列の例で説明していきます。
二分探索を行う上で前提となるのは、並べ替えていることになりますが。
並べ替えアルゴリズムはのちほど説明します。
今回の探索値は３とします。
まずは、この１～９までの配列の中で真ん中位置するのは５になります。
添字で表すと、一番左側の添字０と一番右側の添字８ を足して２で割った添字４の場所が該当します。
まず、その添字４の要素である５と探索値の３を比較します。
探索値の方が小さいので、添字４より左側に探索値があることが分かり、探索範囲が狭まります。
今度はその狭めた範囲、添字０から３の間での中央を求めます。
先ほどの計算式で言うと、０＋３をして÷２をすると、１．５と中途半端な数になります。
今回は、小数点以下を切り捨てて、添字１である、２を中央値として、比較対象とします。
探索値の３と比較して、探索値の方が大きいので、次の比較対象は添字２から３の範囲となります。そして、次の中央値は添字２の３となり探索値と一致するので、添字２の場所が探索値がある場所となります。
これをフローチャートで表していきます。
実際に数値を当てはめながら処理を追っていきます
比較対象のリストはaとして、探索値は４３とします。
まず、探索値の入力は４３が対象となります。
そして、探索対象のリスト名はaとして定義します。
下限の添字は０になります。
上限の添字はデータ数―１なので、今回はデータ数７から１マイナスして６となります。
下限の添字＜＝上限の添字 となるまで、処理を繰り返します。
そして、探索値と比較する中央値を求める為、（上限の添字＋下限の添字）÷２をします。
小数点以下があった場合は切り捨てをします。
今回は 下限０ 上限は６が入っているので、中央の添字は６÷２で３となります。
添字３には５１が入っているので、その５１と探索値の４３を比較すると、探索値の方が小さいので、中央の添字より左側に探索したいデータがあることが分かります。
範囲を狭めるために上限の添字に今の中央の添字―１をして、それを上限の添字に入れてあげます。
中央の添字は今は３なので、１マイナスして２となります。
ループの初めに戻って、下限の添字０と上限の添字２をプラスして２で割ると、中央の添字は１となります。添字１の要素３３と探索値の４３を比較して探索値の方が大きいので、中央より右側に探索値があることが分かります。
条件分岐のＮＯの条件に入るので 今の中央の添字１に１をプラスした２を下限の添字に入れてあげます。
ループのはじめにもどって、下限の添字は２、上限の添字は２なので （２＋２） その二つを足して ÷２をすると中央の添字は２とります。
添字２の要素は４３で探索値と一致するので、一致場所を表示し処理を終了します。
★見つからない時のはなし
今は、探索値が存在しましたが、今説明したフローですと、最終的に探索値が存在しない場合は何も表示されずに処理を終了するという流れになります。
探索値が見つからなかった時のパターンが無いので、二分探索の流れ図を修正していきます。
探索値は存在するか否かの２択なので、TrueかFalseで表せる、Boolean型を使います。
Boolean型の変数名は〇〇フラグと名付ける場合が多いです。
〇〇の部分を満たせばTrue 真、違えばFalse 偽となります。
例えば、イケメンフラグっていう名前だったら、
「イケメン」というのを満たせば、Trueで真 違えば、Falseとなります。
今回はsonzai_flagという変数名にします。
flagは日本語で「旗」という意味があります。
システム業界では、flagを立てるという言葉が多く使われますが、
条件を満たす場合、True（真）を設定することをいいます。
はじめに、sonzai_flagにFalseを設定しておきます。
この状態はフラグが降りている状態になります。
そして探索値が見つかった場合に、Trueを格納します。
この状態で旗が立つイメージになります。
そして、ループを抜けた後に
sonzai_flagがTrueつまり旗が立っていたら「見つかりました」と一緒に添え字を表示します。
sonzai_flagがFalseつまり旗が降りたままだったらなら 見つかりませんでしたという文言を表示するようにします。
これで、探索値が最終的に配列内に存在しない場合も、見つかりませんでしたと表示されるようになります。
―――――
今度は、線形探索と二分探索のの探索回数を比較していきます。
データ数をｎ個とした場合
線形探索の最小探索回数は１回
最大探索回数は最後まで見つからない場合もあるので、ｎ回
平均探索回数は二分のn＋１回となります。
二分探索の最小探索回数は１回
最大探索回数はlog2底ｎ＋１ 回
平均探索回数はlog2底ｎ回となります。
これだとどんなメリットがあるのか分かりずらいので、データ数が１から３０までの場合
それぞれの最大探索回数と平均探索回数をエクセルの表に表すとこのようになります。
この表をもとに最大探索回数を折れ線グラフで表すとこのようになります。
線形探索はデータ数に比例して探索回数が増えますが、二分探索は線形探索に比べてそれほど増えていないことが分かります。
平均探索回数も同様に折れ線グラフで表すとこのようになります。
こちらも線形探索はデータ数に比例して探索回数が増えますが、二分探索は線形探索に比べてそれほど増えていないことが分かります。
＝＝＝＝＝＝＝＝＝＝
つぎは並べ替えアルゴリズムについて説明していきます。
データを昇順または降順に並べ替えることをソートとも言います。
ソートアルゴリズムには何種類か種類がありますが、今回は交換法と選択法について説明していきます。
まず交換法は別名バブルソートとも言います。
配列の中の隣り合うデータの大小を比較し交換を行う方法になります。
添字を含めるとややこしくなるので、はじめは添字無しで説明していきます
８５、４０、２５、６０ の数字を交換法を使って小さい順つまり昇順に並べ替えていきます。
まず、配列の後ろから隣り合う二つの数字を比較していきます。
２５と６０を比較し左側の25の方が小さいので交換は無しでそのままの順番とします。
つぎに、４０と２５を比較し左側の４０の方が大きいので左側が小さくなるように交換します。
つぎに、８５と２５を比較し左側の８５の方が大きいので左側が小さくなるように交換します。
一番左まで比較が終わったので、２５が一番小さいのが確定しました。
また、右端から同じ処理を繰り返していきます。
４０と６０を比較し左側の４０の方が小さいので交換は無しでそのままの順番とします。
つぎに、８５と４０を比較し左側の８５の方が大きいので左側が小さくなるように交換します。
これで、４０が２番目に小さいことが確定しました。
また、右端から同じ処理を繰り返していきます。
８５と６０を比較し左側の８５の方が大きいので左側が小さくなるように交換します。
これで、並べ替えが完了になります。
★アルゴリズム
交換法をフローチャートで表すとこのような感じになります。
分けわからないと思うので先ほど説明した配列aに添字を含めて流れを説明していきます。
添字０は８５、添字１は４０、添字２は２５、添字３は６０になります。
変数ｎは、要素数を表し、今回は４を固定で設定しています。
スペースの関係でフローチャート上のｎの設定処理は省略しています。
変数iはループのカウントで０番から１ずつカウントアップします。
処理上は配列の左側の添字を表します。
変数ｊは配列の右側の添字になり、数値の比較に利用します。
変数tempは数値入れ替え時の一次領域になります。上書きすると前の値が消えてしまうので、上書きする前の値を保持しておく領域になります。
それでは、処理を追っていきます。
ループの中にループがある２重構造になっています。
まず、変数iに０を代入します。 ループの条件はn-2までつまり要素数は４なのでiが２になるまで続けます。
次にｊにｎ―２のあたいである２を設定します。
aの添字jは２ ｊ＋１は３ なので中の値の２５と６０を比較します。
２５の方が小さいので、条件には合致せずに入れ替え処理は行いません。
次のループを行います。
つぎのｊの値はｎ―３なので４―３で１を設定します。
添え字１の４０と添字２の２５を比較します。
４０の方が大きいので、入れ替え処理を行います。
上書き前の値を保持する必要があるので、添字１の４０を変数tempに代入します。
そして、添字２の２５を添字１の領域に上書きます。
添字２の領域に変数tempの値である４０を代入します。
これで入れ替えが完了したので次のループを行います。
つぎのｊの値はｎ―４なので４―４で０を設定します。
添字０の８５と添字２の２５を比較します。
８５の方が大きいので、入れ替え処理を行います。
上書き前の値を保持する必要があるので、添字０の８５を変数tempに代入します。
そして、添字１の２５を添字０の領域に上書きます。
添字１の領域に変数tempの値である８５を代入します。
これで添字０の２５の場所が確定します。
子ループの継続条件をすべて満たしたので、子ループは抜けて親ループに戻ります。
iに１を代入します。
次にｊにｎ―２のあたいである２を設定します。
aの添字jは２ ｊ＋１は３ なので中の値の４０と６０を比較します。
４０の方が小さいので、条件には合致せずに入れ替え処理は行いません。
次のループを行います。
つぎのｊの値はｎ―３なので４―３で１を設定します。
添字１の８５と添字２の４０を比較します。
８５の方が大きいので、入れ替え処理を行います。
上書き前の値を保持する必要があるので、添字１の８５を変数tempに代入します。
そして、添字２の４０を添字１の領域に上書きます。
添字２の領域に変数tempの値である８５を代入します。
これで２番目に小さい値が確定します。
継続条件をすべて満たしたので子ループを抜けて、親ループに移ります。
iに２を代入します。
次にｊにｎ―２のあたいである２を設定します。
aの添字jは２ ｊ＋１は３ なので中の値の８５と６０を比較します。
８５の方が大きいので、８５をtemp領域に格納します。
そして添字３の６０を添字２の領域に上書きます。
退避した８５を添字３の領域に持って行って交換は完了です。
これで全ての並べ替えが完了しました。
子ループ、親ループ共に継続条件を満たしたためループを抜けて処理を終了します。
フローチャートや擬似言語を理解するコツはこのように具体的な数値を当てはめてシミュレーションしてみることです。
★選択法
次に選択法について説明していきます。
要素の中から最小（または最大）のものを見つけ出し、
先頭に持っていくことを繰り返すアルゴリズムになります。
先ほどと同じように、添字は考えずに具体的な数値でイメージを説明していきます。
先ほどと同じ数字を小さい順に並べ替えます。
一番先頭の数値を基準に比較していきます。
まずは、８５と４０を比較します。
８５は４０より大きいので、小さい数字の方を左側に持ってくるため、数字を入れ替えます。
つぎは先頭の４０と２５を比較します。これも４０は２５より大きいので、小さい数字の方を左側に持ってくるため、数字を入れ替えます。
次に先頭の２５と６０を比較します。
２５の方が小さいので入れ替えは行いません。
この時点で先頭の最も小さい数字が確定します。
次に２番目の数字を基準に同じように順番に比較していきます。
まずは、８５と４０を比較します。
８５は４０より大きいので、小さい数字の方を左側に持ってくるため、数字を入れ替えます。
つぎは４０と６０を比較します。４０の方が小さいので入れ替えは行いません。
右端まで比較が終わったので、２番目に小さい４０が確定します。
次に３番目の数字を基準に同じように順番に比較していきます。
８５と６０を比較します。
これも８５は６０より大きいので、小さい数字の方を左側に持ってくるため、数字を入れ替えます。
これで全ての比較が完了したので昇順の並べ替えが完了したことになります。
★フローチャート説明
選択法をフローチャートで表すとこのようになります。
これも先ほどの交換法と同じように具体的な数値を当てはめながら処理を追っていきます。
変数ｎは要素数なので４を代入します。
フローチャート上はスペースの関係で代入処理を省略しています。
変数iは配列の左側の添字
変数jは配列の右側の添字で比較先になります。
変数tempは先ほどと同じく入れ替え時の一時退避領域になります。
まず、変数iに０を代入します。
つぎは変数ｊはi+1なので１を代入します。
添字０の８５と添字１の４０を比較し８５の方が大きいのでＹｅｓの処理に入ります。
８５を変数tempに代入し退避します。
添字１の４０を添字０の領域に上書きします。
添字１の領域に変数tempの値の８５を代入し、入れ替えが完了します。
つぎに変数ｊにi+2の２を代入します。
添字０の４０と添字２の２５を比較し４０の方が大きいのでＹｅｓの処理に入ります。
４０を変数tempに代入し退避します。
添字２の２５を添字０の領域に上書きします。
添字２の領域に変数tempの値の４０を代入し、入れ替えが完了します。
つぎに変数ｊにi+３の３を代入します。
添字０の２５と添字３の６０を比較し２５の方が小さいので入れ替えは行いません。
これで一番小さい値の添字０の領域は確定しました。
子ループのｊがn-1 つまり３に達したので子ループを抜け親ループに戻ります。
親ループ２ループ目なので、
変数iに１を代入します。
変数ｊはi+1 で２を代入します。
添字１の８５と添字２の４０を比較し、８５の方が大きいのでＹＥＳの処理に入ります。
添字１の８５をtempに退避します。
添字２の４０を添字１の領域に上書きます。
退避した８５を添字２の領域に上書きし、交換が完了します。
子ループの初めに戻り、i+2の３をjに代入します。
添字１の４０と添字３の６０を比較し４０の方が小さいので、入れ替えは行なわれません。
これで２番目に小さい値は確定しました。
これで子ループがn-1の３になったので、子ループを抜け親ループに戻ります。
親の３ループ目はiに２を代入します。
ｊはi+１で３を代入します。
添字２の８５と添字３の６０を比較し８５の方が大きいので入れ替えを行います。
８５をtempに退避します。
６０を添字２の領域に上書きします。
temp領域の８５を添字３に上書きします。
これで全ての並べ替えが完了しました。
子ループ親ループ共に最後の継続条件まで行ったのでループの処理を抜けます。
―――――――――――――――――――
今説明した交換法と選択法の要素間の比較回数について
要素数がｎ個とした場合、
２分のｎ（ｎ―１）回の比較が必要になります。
交換回数の最小は初めから並べ替えが完了している場合で、０回となります。
最大交換回数は比較回数と同じ、２分のｎ（ｎ―１）回になります。
今日の探索とソートアルゴリズムの授業は以上になります。
最後までご視聴ありがとうございました。
【解説重要用語】
探索アルゴリズム、線形探索、二分探索、探索回数比較、ソート（並び替え）アルゴリズム、交換法（バブルソート）
★私の目標
「とある男が授業をしてみた」 の葉一さん
https://www.youtube.com/user/toaruotokohaichi
※Google社に招待頂いた、「YouTube教育クリエイターサミット2020」で
葉一さんと文部科学省・Google役員の対談セッションに感銘を受けて、高校情報講座スタートしています。
【参考サイト・参考文献】
文部科学省 「情報Ⅰ」教員研修用教材
https://www.mext.go.jp/a_menu/shotou/zyouhou/detail/1416756.htm
詳細（情Ｉ703 高校情報Ｉ Python）｜情報｜高等学校 教科書・副教材｜実教出版 (jikkyo.co.jp) 検定通過版
https://www.jikkyo.co.jp/book/detail/22023322
令和4年度新版教科書「情報Ⅰ」｜高等学校 情報｜日本文教出版 (nichibun-g.co.jp)検定通過版
https://www.nichibun-g.co.jp/textbooks/joho/2022_joho01_1/textbook/
この記事が気に入ったらサポートをしてみませんか？