高等学校情報/情報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をつかって表記するのが慣習。