高等学校情報/情報I/ソート
アルゴリズムなどの知識

※ 『高等学校情報科「情報I」教員研修用教材 JavaScript 版(第3 章のみ) - 20200716-mxt_jogai01-000001169_001.pdf』などでソートを紹介しています。
アルゴリズムなどの知識

読者の皆さんは、よく
アルゴリズムなどの知識

のような、データ一覧で、「国語の点数の高い順に並べ替えてみたいなあ・・・」とか思ったことはないでしょうか。
アルゴリズムなどの知識

つまり、
アルゴリズムなどの知識

と並べ替えたりとか。
アルゴリズムなどの知識

※ 説明を短くするため、クラスの生徒数が3人だけの学級として設定しています。
アルゴリズムなどの知識

こういうふうに、ある項目の数値の大小順に並べ替えることを情報技術の用語でソートと言います。
アルゴリズムなどの知識

ソートの概念は、単にデータを整理するだけの用途のほかにも、たとえば最短ルートの探索などにも応用できます。(※ 教員向けマニュアルで紹介しているのはコッチ(探索)のほう。)なお、検定教科書で二分探索法などの探索法を教えてるのは偶然ではなく、探索法をする前には前処理としてソートが必要になる場合が多いからです。
アルゴリズムなどの知識

なので、ともかくソートの手法はいろいろ応用されるので、ソートという概念を知っておきましょう。
アルゴリズムなどの知識

ソートの代表的な手法には数種類あります。教員向けマニュアルでは「選択ソート」と「クイックソート」が紹介されています。教科書では、バブルソートなども紹介されているようです。
アルゴリズムなどの知識

時間に余裕があれば、JavaScriptやPython など、普通のプログラミング言語を使って、ソートをプログラムを自力で作ることも可能です。
アルゴリズムなどの知識

どのプログラミング言語にもある、条件分岐の if文 やその条件式の中での不等号( ≦ や ≧ に相当する判定のこと)の利用、繰り返し処理の for文 、そしてソートの処理前および処理後の結果を格納するための「配列」(はいれつ)といわれるデータ構造、などの入門的な機能を組み合わせることで、ソートのプログラムを作ることができます。(教員むけプログラムにも、ソートのコード例があります。)
アルゴリズムなどの知識

バブルソートが、いちばん理解がラクでしょう。バブルソートは、リーグ戦方式の順番で、集団のうちから2つの数を取り出して並べる方法です。
アルゴリズムなどの知識

たとえば、先ほどの 阿部(数学55)、 内村(数学90)、枝野(数学73)の数学の点数をこの順に配列にした(55,90,73)並べ替えるなら、
アルゴリズムなどの知識

この順番で行うだけです。
アルゴリズムなどの知識

バブルソートの比較の回数は、チーム数n個でのリーグ戦の試合の回数と同じなので、比較の回数はおおむね n ( n + 1 ) 2 {\displaystyle {\frac {n(n+1)}{2}}} に比例することが知られています。
アルゴリズムなどの知識

このほか、選択ソートというのもありますが、比較の回数はバブルソートとあまり変わりません。単に、比較の順番が違うだけです。
アルゴリズムなどの知識

選択ソートは配列内のデータから最小値を探索し,最小値から順に取り出すことで並べ替えを実現するアルゴリズムです(文科省の研修用教材にそう書いてある)。
アルゴリズムなどの知識

さて、実際の並び替えでは、おおむね順番に整列されているが、ところどころ順番通りでない列というのもあります。
アルゴリズムなどの知識

そういう、おおむね整列されているものを並び替えるときに、バブルソートよりも短い比較回数で済まそうとするのが、クイックソートや挿入ソートやマージソートなどのソート方法です。
アルゴリズムなどの知識

たとえば、「完全に整列されていたデータ列Aの内部に、あらたなデータをいくつか追加した。元データ列のどこら辺に追加したかは分からない。追加したデータの個数は少なめで、元データ列の個数に比べて、それほど個数が多くは無いことは分かってる。この混ざったデータ列を並びなおして、整列されたデータ列(これを仮にデータ列Bとする)を得たい」みたいな場合です。
アルゴリズムなどの知識

もし元のデータ列が整列されてない場合、必ずしもクイックソートやマージソートなどを使っても、ソートは高速化されません。(出典サイトURLは忘れましたが、文科省の制作支援する勉強会のYouTube動画で、大学教員がそう言っています。) また、後述する文科省の研修用教材でも、似たようなことを言っています。
アルゴリズムなどの知識

さて、そのクイックソートとは、配列内から1つの値を取り出し、それを基準に残りの数値を2分割していくものです。
アルゴリズムなどの知識

たとえば、
アルゴリズムなどの知識

3,7,1,4,2,10
アルゴリズムなどの知識

を並び替える場合、
アルゴリズムなどの知識

3を基準に、それより小さい(1,2)のグループと、それより大きい(7,4,10)のグループを得ます。
アルゴリズムなどの知識

その後、同様に(1,2)を1を基準にして、それより大きい2を得ます。(2)のように1個だけになったら、そこで確定です。
アルゴリズムなどの知識

結果的に、(1,2)が確定し、さらにその前で基準にしていた3より小さいことが確定しているので、(1,2,3)が確定します。
アルゴリズムなどの知識

(7,4,10)のほうも並び替えをします。
アルゴリズムなどの知識

まず、7を基準にそれより小さい4と、それより大きい10が得られます。そして、(4)も(10)もカッコ内に1個しかないので確定です。
アルゴリズムなどの知識

(4,7,10)が確定します。
アルゴリズムなどの知識

あとは、(1,2,3)と(4,7,10)とをこの順番でくっつけるだけです。
アルゴリズムなどの知識

こうして、この場合のクイックソートでは最終的に(1,2,3,4,7,10)で確定します。
アルゴリズムなどの知識

クイックソートは、2分探索法のような考え方をソートに応用したものです(と述べている)。
アルゴリズムなどの知識

運が良ければ、最初に選んだ基準値が最終結果の真ん中のほうに来る値に近ければ、2分探索法のように計算時間が短縮できます。
アルゴリズムなどの知識

事前にある程度、配列の中央値が分かっている場合、クイックソートが価値を発揮します。
アルゴリズムなどの知識

配列があるていど整列されているなら、中央値はおおむね、データc列の真ん中のほうにあるでしょう。なので、データ列の真ん中の値を基準にする方法がよく使われます。
アルゴリズムなどの知識

ただし、これだと、たまたまデータ列の真ん中に、最小値または最大値に近い値があった場合、運悪く、比較の回数が増えてしまいます。
アルゴリズムなどの知識

なので、念のため、データ列の先頭の値、データ列の真ん中の値、データ列の最後尾の値といった、この3つの値の中央値を取れば、よほど運が悪くないかぎり、まあ、採用した基準値がきっと最終結果の中央値にも近いでしょう、近いはずだ、近ければいいなあ・・・という事です。(前提として、整列前のデータがあるていどは整列されていることを前提にしています。)
アルゴリズムなどの知識

ネットでは、「クイックソートが一番早い」みたいなデマがありますが、しかし文科省は下記のように反論しています。
アルゴリズムなどの知識

クイックソートが早い場合とは、あるていど不規則なデータ列で、さらに最初に選んだ基準値がデータ列全体の中央値に近い場合です。
アルゴリズムなどの知識

もし、元データが整列済みまたは ほぼ整列済み の場合、クイックソートはバブルソートと同じような比較回数になってしまいます文部科学省/mextchannel『高等学校「情報I」オンライン学習会 【第7回】アルゴリズムの比較から効率的なアルゴリズムの理解の仕方』 。なぜなら基準値を最初および分割ごとに選ぶ際、その基準値が二分ではなく一分になってしまうからです。
アルゴリズムなどの知識

比較回数だけ見ればバブルソートとクイックソート最悪時は比較回数だけは同じですが、しかしクイックソートには他のプログラム処理も色々と加わるので、場合によってはバブルソートよりも少しだけ遅くなりかねません。
アルゴリズムなどの知識

さて、文科省の教材では触れられてないですが、バブルソートと選択ソートの比較回数は基本的には同程度ですから、つまりクイックソートが選択ソートより遅くなる場合もあるという事は、クイックソートがバブルソートよりも遅くなる場合もあるという事です。
アルゴリズムなどの知識

また、二分探索法のアイデアに基づくクイックソートが、事前にデータ列がある程度は整列されている事を前提にしているということは、つまり、そもそも「二分探索法が速くなる場合とは、事前にある程度は探索結果が分かっている」という意味です。文科省がそういう感じのことを研修用教材で言っています。
アルゴリズムなどの知識

探索法には、二分探索法のほか線形探索法があります。ネットのデマでは、二分探索法が最強でいつも速いということですが、しかし文科省はこのデマを否定しています。場合によっては、探索結果が予想に反している場合などは、二分探索法は線形探索法よりも遅くなると文科省は言っています。
アルゴリズムなどの知識

文科省は教材で言っています。
アルゴリズムなどの知識

文科省は、ネットのデマを真っ向から否定です。
アルゴリズムなどの知識

※ データベースソフトの Microsoft Access を買わなくても、Excel のテーブルでソートなど出来るので、まずは Excel で練習しよう。
アルゴリズムなどの知識

そもそも「テーブル」という用語自体、データベース用語でもある。
アルゴリズムなどの知識

なお、Google アプリにAccess相当の機能は無い(2023年現在)。
アルゴリズムなどの知識

さて、並び替えの基準にしている項目名のことをキーと言う。たとえばもし国語の得点で並び替えるなら、キーは「国語の得点」である。
アルゴリズムなどの知識

Excel には並び替え機能のほか、フィルター機能もあるが(たとえば特定の数値よりも大きい列を検出したりできる)、あまり使い勝手が良くない。(テーブルの項目名の三角マークをクリックすると、フィルターも選べる。)
アルゴリズムなどの知識

本来、Excelはデータベースソフトではないので、UI的に少し分かりづらい。
アルゴリズムなどの知識

Google スプレッドシートおよび Libreoffice Calc には、ソートの機能はあるが、しかしExcelでいう「テーブル」の機能(つまり簡易データベース機能)が無い。なので、Excelのテーブル設定がGoogleスプレッドシートなどでは維持できず、互換性が悪い。
アルゴリズムなどの知識

よって、データベース目的では、初心者はGoogleスプレッドシートおよびLibreOffice Calc の使用は避けたほうが安全だろう。
計算量

教科書ガイドで、二分探索の計算量を紹介。(少なくとも実教「情報I」(PythonとかJavaScriptの対応のヤツ)のガイドに書いてあった。)
計算量

二分探索の計算量は log2N に比例とか、書いてある。
計算量

Nは、探索対象の要素数であり、もちろん整数。慣習的に「N」を使う。
計算量

ほかの探索法の計算量の記法でもNを使って表記するのが一般的。探索だけでなくソートなどの計算量でも、Nをつかって表記するのが一般的。
計算量

一般に計算量の式では、Nをつかって表記するのが慣習。
アルゴリズムなどの知識

※ 『高等学校情報科「情報I」教員研修用教材 JavaScript 版(第3 章のみ) - 20200716-mxt_jogai01-000001169_001.pdf』などでソートを紹介しています。
アルゴリズムなどの知識

読者の皆さんは、よく
アルゴリズムなどの知識

のような、データ一覧で、「国語の点数の高い順に並べ替えてみたいなあ・・・」とか思ったことはないでしょうか。
アルゴリズムなどの知識

つまり、
アルゴリズムなどの知識

と並べ替えたりとか。
アルゴリズムなどの知識

※ 説明を短くするため、クラスの生徒数が3人だけの学級として設定しています。
アルゴリズムなどの知識

こういうふうに、ある項目の数値の大小順に並べ替えることを情報技術の用語でソートと言います。
アルゴリズムなどの知識

ソートの概念は、単にデータを整理するだけの用途のほかにも、たとえば最短ルートの探索などにも応用できます。(※ 教員向けマニュアルで紹介しているのはコッチ(探索)のほう。)なお、検定教科書で二分探索法などの探索法を教えてるのは偶然ではなく、探索法をする前には前処理としてソートが必要になる場合が多いからです。
アルゴリズムなどの知識

なので、ともかくソートの手法はいろいろ応用されるので、ソートという概念を知っておきましょう。
アルゴリズムなどの知識

ソートの代表的な手法には数種類あります。教員向けマニュアルでは「選択ソート」と「クイックソート」が紹介されています。教科書では、バブルソートなども紹介されているようです。
アルゴリズムなどの知識

時間に余裕があれば、JavaScriptやPython など、普通のプログラミング言語を使って、ソートをプログラムを自力で作ることも可能です。
アルゴリズムなどの知識

どのプログラミング言語にもある、条件分岐の if文 やその条件式の中での不等号( ≦ や ≧ に相当する判定のこと)の利用、繰り返し処理の for文 、そしてソートの処理前および処理後の結果を格納するための「配列」(はいれつ)といわれるデータ構造、などの入門的な機能を組み合わせることで、ソートのプログラムを作ることができます。(教員むけプログラムにも、ソートのコード例があります。)
アルゴリズムなどの知識

バブルソートが、いちばん理解がラクでしょう。バブルソートは、リーグ戦方式の順番で、集団のうちから2つの数を取り出して並べる方法です。
アルゴリズムなどの知識

たとえば、先ほどの 阿部(数学55)、 内村(数学90)、枝野(数学73)の数学の点数をこの順に配列にした(55,90,73)並べ替えるなら、
アルゴリズムなどの知識

この順番で行うだけです。
アルゴリズムなどの知識

バブルソートの比較の回数は、チーム数n個でのリーグ戦の試合の回数と同じなので、比較の回数はおおむね n ( n + 1 ) 2 {\displaystyle {\frac {n(n+1)}{2}}} に比例することが知られています。
アルゴリズムなどの知識

このほか、選択ソートというのもありますが、比較の回数はバブルソートとあまり変わりません。単に、比較の順番が違うだけです。
アルゴリズムなどの知識

選択ソートは配列内のデータから最小値を探索し,最小値から順に取り出すことで並べ替えを実現するアルゴリズムです(文科省の研修用教材にそう書いてある)。
アルゴリズムなどの知識

さて、実際の並び替えでは、おおむね順番に整列されているが、ところどころ順番通りでない列というのもあります。
アルゴリズムなどの知識

そういう、おおむね整列されているものを並び替えるときに、バブルソートよりも短い比較回数で済まそうとするのが、クイックソートや挿入ソートやマージソートなどのソート方法です。
アルゴリズムなどの知識

たとえば、「完全に整列されていたデータ列Aの内部に、あらたなデータをいくつか追加した。元データ列のどこら辺に追加したかは分からない。追加したデータの個数は少なめで、元データ列の個数に比べて、それほど個数が多くは無いことは分かってる。この混ざったデータ列を並びなおして、整列されたデータ列(これを仮にデータ列Bとする)を得たい」みたいな場合です。
アルゴリズムなどの知識

もし元のデータ列が整列されてない場合、必ずしもクイックソートやマージソートなどを使っても、ソートは高速化されません。(出典サイトURLは忘れましたが、文科省の制作支援する勉強会のYouTube動画で、大学教員がそう言っています。) また、後述する文科省の研修用教材でも、似たようなことを言っています。
アルゴリズムなどの知識

さて、そのクイックソートとは、配列内から1つの値を取り出し、それを基準に残りの数値を2分割していくものです。
アルゴリズムなどの知識

たとえば、
アルゴリズムなどの知識

3,7,1,4,2,10
アルゴリズムなどの知識

を並び替える場合、
アルゴリズムなどの知識

3を基準に、それより小さい(1,2)のグループと、それより大きい(7,4,10)のグループを得ます。
アルゴリズムなどの知識

その後、同様に(1,2)を1を基準にして、それより大きい2を得ます。(2)のように1個だけになったら、そこで確定です。
アルゴリズムなどの知識

結果的に、(1,2)が確定し、さらにその前で基準にしていた3より小さいことが確定しているので、(1,2,3)が確定します。
アルゴリズムなどの知識

(7,4,10)のほうも並び替えをします。
アルゴリズムなどの知識

まず、7を基準にそれより小さい4と、それより大きい10が得られます。そして、(4)も(10)もカッコ内に1個しかないので確定です。
アルゴリズムなどの知識

(4,7,10)が確定します。
アルゴリズムなどの知識

あとは、(1,2,3)と(4,7,10)とをこの順番でくっつけるだけです。
アルゴリズムなどの知識

こうして、この場合のクイックソートでは最終的に(1,2,3,4,7,10)で確定します。
アルゴリズムなどの知識

クイックソートは、2分探索法のような考え方をソートに応用したものです(と述べている)。
アルゴリズムなどの知識

運が良ければ、最初に選んだ基準値が最終結果の真ん中のほうに来る値に近ければ、2分探索法のように計算時間が短縮できます。
アルゴリズムなどの知識

事前にある程度、配列の中央値が分かっている場合、クイックソートが価値を発揮します。
アルゴリズムなどの知識

配列があるていど整列されているなら、中央値はおおむね、データc列の真ん中のほうにあるでしょう。なので、データ列の真ん中の値を基準にする方法がよく使われます。
アルゴリズムなどの知識

ただし、これだと、たまたまデータ列の真ん中に、最小値または最大値に近い値があった場合、運悪く、比較の回数が増えてしまいます。
アルゴリズムなどの知識

なので、念のため、データ列の先頭の値、データ列の真ん中の値、データ列の最後尾の値といった、この3つの値の中央値を取れば、よほど運が悪くないかぎり、まあ、採用した基準値がきっと最終結果の中央値にも近いでしょう、近いはずだ、近ければいいなあ・・・という事です。(前提として、整列前のデータがあるていどは整列されていることを前提にしています。)
アルゴリズムなどの知識

ネットでは、「クイックソートが一番早い」みたいなデマがありますが、しかし文科省は下記のように反論しています。
アルゴリズムなどの知識

クイックソートが早い場合とは、あるていど不規則なデータ列で、さらに最初に選んだ基準値がデータ列全体の中央値に近い場合です。
アルゴリズムなどの知識

もし、元データが整列済みまたは ほぼ整列済み の場合、クイックソートはバブルソートと同じような比較回数になってしまいます文部科学省/mextchannel『高等学校「情報I」オンライン学習会 【第7回】アルゴリズムの比較から効率的なアルゴリズムの理解の仕方』 。なぜなら基準値を最初および分割ごとに選ぶ際、その基準値が二分ではなく一分になってしまうからです。
アルゴリズムなどの知識

比較回数だけ見ればバブルソートとクイックソート最悪時は比較回数だけは同じですが、しかしクイックソートには他のプログラム処理も色々と加わるので、場合によってはバブルソートよりも少しだけ遅くなりかねません。
アルゴリズムなどの知識

さて、文科省の教材では触れられてないですが、バブルソートと選択ソートの比較回数は基本的には同程度ですから、つまりクイックソートが選択ソートより遅くなる場合もあるという事は、クイックソートがバブルソートよりも遅くなる場合もあるという事です。
アルゴリズムなどの知識

また、二分探索法のアイデアに基づくクイックソートが、事前にデータ列がある程度は整列されている事を前提にしているということは、つまり、そもそも「二分探索法が速くなる場合とは、事前にある程度は探索結果が分かっている」という意味です。文科省がそういう感じのことを研修用教材で言っています。
アルゴリズムなどの知識

探索法には、二分探索法のほか線形探索法があります。ネットのデマでは、二分探索法が最強でいつも速いということですが、しかし文科省はこのデマを否定しています。場合によっては、探索結果が予想に反している場合などは、二分探索法は線形探索法よりも遅くなると文科省は言っています。
アルゴリズムなどの知識

文科省は教材で言っています。
アルゴリズムなどの知識

文科省は、ネットのデマを真っ向から否定です。
アルゴリズムなどの知識

※ データベースソフトの Microsoft Access を買わなくても、Excel のテーブルでソートなど出来るので、まずは Excel で練習しよう。
アルゴリズムなどの知識

そもそも「テーブル」という用語自体、データベース用語でもある。
アルゴリズムなどの知識

なお、Google アプリにAccess相当の機能は無い(2023年現在)。
アルゴリズムなどの知識

さて、並び替えの基準にしている項目名のことをキーと言う。たとえばもし国語の得点で並び替えるなら、キーは「国語の得点」である。
アルゴリズムなどの知識

Excel には並び替え機能のほか、フィルター機能もあるが(たとえば特定の数値よりも大きい列を検出したりできる)、あまり使い勝手が良くない。(テーブルの項目名の三角マークをクリックすると、フィルターも選べる。)
アルゴリズムなどの知識

本来、Excelはデータベースソフトではないので、UI的に少し分かりづらい。
アルゴリズムなどの知識

Google スプレッドシートおよび Libreoffice Calc には、ソートの機能はあるが、しかしExcelでいう「テーブル」の機能(つまり簡易データベース機能)が無い。なので、Excelのテーブル設定がGoogleスプレッドシートなどでは維持できず、互換性が悪い。
アルゴリズムなどの知識

よって、データベース目的では、初心者はGoogleスプレッドシートおよびLibreOffice Calc の使用は避けたほうが安全だろう。
計算量

教科書ガイドで、二分探索の計算量を紹介。(少なくとも実教「情報I」(PythonとかJavaScriptの対応のヤツ)のガイドに書いてあった。)
計算量

ほか、検定教科書でも日本文教出版『情報II』(P.117)に計算量が書いてある。
計算量

二分探索の計算量は log2N に比例とか、書いてある。
計算量

Nは、探索対象の要素数であり、もちろん整数。慣習的に「N」を使う。
計算量

ほかの探索法の計算量の記法でもNを使って表記するのが一般的。探索だけでなくソートなどの計算量でも、Nをつかって表記するのが一般的。
計算量

一般に計算量の式では、Nをつかって表記するのが慣習。
計算量

あるアルゴリズムの計算量がたとえば 2n + n + 1 に比例するとき、計算量はもっとも大きな次数だけの影響を受ける。
計算量

つまり、上記の例のアルゴリスムの場合なら 2n に近似できる。
計算量

計算量の表記ではよく、下記のような「O記法」(オーきほう、O notation)を使って記述を簡素化する。
計算量

たとえば計算量 2n + n + 1 は
計算量

と略記される。
計算量

線形探索の計算量は O ( n ) {\displaystyle O(n)} である。
計算量

二分探索の計算量は O ( log 2 n ) {\displaystyle O(\log _{2}n)} である。
計算量

二次関数や三次関数のグラフを書いたことあるなら分かると思うが、変数の値が大きくなるほど(ただし変数は正だとする)、次数の小さい項の影響は無視できる。高校の数学IIや数学IIIの微分(びぶん)や極限などの理論も、この性質を前提にしている。
計算量

そして、コンピュータ科学において、実用的に関心のあるのは、計算対象の要素の個数が多い場合である(たとえばソートなら、並び替え対象が多い場合を、コンピュータにやらせたいので)。
計算量

極端な話、並び替えの対象がたったの1個しかないなら、そもそもソートのプログラムを実行するまでもなく、すでにもう並び替えは終わっている。ソートの対象が2個しかない場合でも、単に大小比較を1回すれば終わるので、アルゴリズムをあれこれと考える必要が無い。
計算量

必然的に、要素の数が多い場合についてだけ、技術者は気にすれば良いことが多い。
計算量

なので、コンピュータ科学において、計算量を調べたい場合は、通常、要素の数が多い場合を考えるのである。
計算量

また、負の数を考える必要は無い。なぜなら要素数がマイナス1個とか、ありえないからである。たとえば「マイナス5人の生徒の成績の並び替え」(←??)とか、意味不明であり、ありえない。
計算量

また、ここでの要素数 n は当然ながら自然数である。たとえば「ルート3人の生徒の成績の並び替え」(←??)とか、意味不明であり、ありえない。
計算量

数学では慣習的に自然数の変数には n を使うことが多い。