高等学校情報/情報I/ソート

アルゴリズムなどの知識

ソート

※ 実教出版の情報I Python でソートが紹介されています。

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

※ 数研出版、第一学習社などは紹介していない。理系に強そうな出版社でも、ソートを意外と紹介していない。

※ 情報II では紹介されていない（東京書籍、日本文教出版、実教　のそれぞれ情報II）。実教の情報IIですら紹介されてない。

---

読者の皆さんは、よく

出席番号:01, 阿部、 国語80点、 数学55点、

出席番号:02, 内村、　国語50点、 数学90点、

出席番号:03, 枝野、　国語70点、 数学73点、

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

つまり、

出席番号:01, 阿部、 国語80点、 数学55点、

出席番号:03, 枝野、　国語70点、 数学73点、

出席番号:02, 内村、　国語50点、 数学90点、

と並べ替えたりとか。

※ 説明を短くするため、クラスの生徒数が3人だけの学級として設定しています。

こういうふうに、ある項目の数値の大小順に並べ替えることを情報技術の用語でソートと言います。

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

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

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

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

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

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

たとえば、先ほどの 阿部（数学55）、 内村(数学90)、枝野(数学73)の数学の点数をこの順に配列にした(55,90,73)並べ替えるなら、

安部55・内村90の比較をして、結果の並びとして「55,90」の配列をまず作成し、これで（55,90,73）の1番目と2番目を置き換え。結果的に、同じ（55,90,73）のまま

↓

安部55・枝野73の比較、すでに「55,90,73」の配列があるが枝野の点数は安部の隣に入れることとし、安部の左側に入れるか右側に入れるかを判別するために先ほどの安部・枝野の比較を利用し、枝野のほうが大きいので「55,73,90」の配列になる。

↓

内村90・枝野73の比較、さきほどの安部・枝野の比較では内村と枝野の関係は無視していたので、残りの比較をする必要がある。リーグ戦方式なら、最終的には漏れなく比較することになる。「55,73,90」が確定する。

この順番で行うだけです。

バブルソートの比較の回数は、チーム数n個でのリーグ戦の試合の回数と同じなので、比較の回数はおおむね${\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分探索法のように計算時間が短縮できます。

事前にある程度、配列の中央値が分かっている場合、クイックソートが価値を発揮します。

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

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

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

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

しかしながら，クイックソートでは逆順に並べ替えられている場合など，ある条件下では比較を行う回数が膨
大になり，選択ソートよりも処理に必要な時間が多くなることもある。
ソートアルゴリズムの場合においても，必ずしもクイックソートの方が優れたアルゴリズムであるとは言い切
れないことがわかる

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

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

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

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

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

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

文科省は教材で言っています。

最大探索回数だけを比較すると，回数の少ない二分探索がよいアルゴリズムと考えがちだが，二分探索には事
前にデータを並べ替えておく必要があり，一概によいアルゴリズムとは言い切れない。例えば「事前にデータが
並び替えられている保証がない場合」や「データの数がそれほど多くなく，シンプルなアルゴリズムの方が望ま
しい場合」などは線形探索の方が有用な場合もある。

文科省は、ネットのデマを真っ向から否定です。

表計算ソフトのソート

じつは Excel や Google スプレッドシートなどの表計算ソフトには、すでに数値の並び替えの機能がある。 Excel の場合、事前にテーブル化しておくと、操作ミスの心配が減るので、テーブル化すると良い。 テーブル化すると、あとはメタデータ部分の項目にある▽マークをクリックするだけで、昇順または降順でソートを選べる。 なお、小さい順で並べたい場合を「昇順」と言う。 大きい順で並べたい場合を「降順」と言う。 ただし、Googleスプレッドシートには、テーブル化の機能が無い。 なんらかの事情で表をテーブル化したくない場合、それでもソートしたいなら、 Excelなら 「ホーム」＞「並び替えとフィルター」 である。 Google スプレッドシートの場合、 「データ」＞「シートを並び替え」 である。 ただし、他のアプリと連動できないので、もし自分でソートの機能をもったアプリを作りたい場合には、上記のバブルソートだのクイックソートだのといったソートを自前でプログラムする必要がある。 並べ替えは数値だけでなく、文字も行える。 アルファベット→仮名（かな）→漢字 の順。 アルファベットはABC順、 かなは、平仮名→カタカナの順で、それぞれ清音（例：は）→濁音（例：ば）→半濁音（例：ぱ）の順 漢字は文字コード順。

※　データベースソフトの 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）に計算量が書いてある。

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

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

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

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

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

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

Ｏ記法

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

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

$O(n^{2})$

と略記される。

線形探索の計算量は $O(n)$である。

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

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

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

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

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

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

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

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

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