こんにちは！しゅんです！
今回はソートアルゴリズムについて解説していきます！
数字を小さい順に並べ替えるアルゴリズムはマージソート、ヒープソート、クイックソートなどたくさんあります。そしてこのソートアルゴリズムの計算量って結構\(O(n\log{n})\)のものが多い気がします。
ということでこの記事ではなぜソートアルゴリズムの計算量で\(O(n\log{n})\)がよく登場するのかについて説明していきたいと思います。
それでは解説していきましょう！
普段は統計検定2級の記事を書いてたりします。
ぜひ他の記事も読んでみてください！
このブログの簡単な紹介はこちらに書いてあります。
興味があったら見てみてください。
このブログでは経営工学を勉強している現役理系大学生が、経営工学に関することを色々話していきます！
ぼくが経営工学を勉強している中で感じたことや、興味深かったことを皆さんと共有出来たら良いなと思っています。
そもそも経営工学とは何なのでしょうか。Wikipediaによると
経営工学（けいえいこうがく、英: engineering management）は、人・材料・装置・情報・エネルギーを総合したシステムの設計・改善・確立に関する活動である。そのシステムから得られる結果を明示し、予測し、評価するために、工学的な分析・設計の原理・方法とともに、数学、物理および社会科学の専門知識と経験を利用する。
引用元 : 経営工学 – Wikipedia
長々と書いてありますが、要は経営、経済の課題を理系的な観点から解決する学問です。
ソートってなに？
そもそもソートってなに？ってなるかもしれません。簡単に言うとソートとはデータを並び替えることです。下の図みたいに適当に数字列が与えられたときに、小さい順に並べ替えたりすることのはソートの1種です。
マージソート、ヒープソート、クイックソートなどは数字を並べ替えるソートアルゴリズムの代表的な例です。
アルゴリズムは計算量が重要
世の中には様々なアルゴリズムが存在しますが、それらの中でどれを使うかを判断するための指標の一つに計算量というものがあります。簡単に言うと計算にどれだけ時間がかかるかを表しています。
計算量が小さいアルゴリズムの方が早く計算できるので、その点に関しては良いアルゴリズムだと言えます。
ソートアルゴリズムも色んな種類がありますが、並べ替えたい数字の数を\(n\)としたときの計算量が\(O(n\log{n})\)のソートアルゴリズムが結構多いんです。
先ほど説明したマージソート、ヒープソート、クイックソートはどれも計算量が\(O(n\log{n})\)です。これは偶然でしょうか。
ソートは\(O(n\log{n})\)が限界なのか
それではソートアルゴリズムはどう頑張っても\(O(n\log{n})\)の壁を超えることができないのでしょうか。結論から言うと、比較ソートに分類されるソートはどう頑張っても\(O(n\log{n})\)より計算量を小さくすることができないんです。
ということでなぜこのようなことが言えるのかについて説明したいと思います。
比較ソートってなに？
まず比較ソートがどんなソートなのかについて説明していきます。簡単に言うと数字の大小を比較して並べていくソートのことを比較ソートと言います。（そのままですね笑）
先ほど紹介したマージソート、ヒープソート、クイックソートはどれも比較ソートに分類されます。
比較ソートの計算量を考える
では比較ソートの計算量について考えてみましょう。\(n\)個の数字が与えられた場合を考えます。このとき考えられる数字の並びは全部で\(n!\)通りあります。
このことを図で表してみましょう。例えば数字列\([a_1, \; a_2 ,\; a_3]\)が与えられたときにこれを小さい順に並べ替えることを考えます。
数字を比較して順番を決めるのでまず\(a_1\)と\(a_2\)を比較します。もし\(a_1\)の方が大きかったら「はい」の方に進み、そうじゃなかったら「いいえ」の方に進みます。
これを繰り返していくことでいずれは数字列の順番を決定することができます。例えば\(a_1>a_2\)が「はい」、\(a_2>a_3\)が「いいえ」、\(a_1>a_3\)が「いいえ」のときは\(a_2<a_1<a_3\)となるので小さい順に並べると\([a_2,\; a_1,\; a_3]\)となります。
次に比較回数のところを見てみましょう。比較ソートの計算量を考えるうえで重要なのが比較回数です。これが多ければ多い程計算量も増えてしまうので、比較回数はなるべく少ないほうが良いです。
例えば上の例で言うと最大3回で比較が終了していますね。
（\([a_3,\;a_2,\;a_1]\)の場合は2回の比較で終了しています。）
これは並べる数字の数が3つだからです。では並べる数字の個数が変わると比較回数はどのように変化していくのでしょうか。これを考える上でのポイントが、このグラフの一番下の部分です。
1回比較をするごとに選択肢が2倍になっていきます。そのため3回比較を行うと起こりうる可能性が\(2^3=8\)通りとなります。
そして並べ替えた数字列は一番下の枝にくっついているはずです。例えば数字が3つの場合は6通りの選択肢があると話しましたが、それらは3回目の比較でできた8個の末端の頂点のどれかに必ず割り当てられるはずです。
例えば比較回数が2回の時点では、末端の頂点が4つしかないので6個の数字列の選択肢を全て割り当てることができません。
つまり並べる数字が3つの場合は\(3!=6\)通りの選択肢があるので、このとき比較は3回行うことで十分なのです。
この事実を使うと並べる数字の個数が変わっても比較回数が分かるんです。例えば数字が4つの場合数字列の選択肢は\(4!=24\)通りで、\(2^4=16,\; 2^5=32\)なので5回比較を行えば十分です。
それでは数字の個数が\(n\)個で比較回数が\(T(n)\)回のとき、この2つの間にどのような関係式が成り立つでしょうか。
これまでと同じように考えると、数字が\(n\)個ある場合は\(n!\)通りの選択肢があります。そして比較回数が\(T(n)\)回ということは末端の頂点が\(2^{T(n)}\)個あり、これが\(n!\)以上になる必要がありますね。
従って\(n\)と\(T(n)\)の間には以下の関係式が成り立ちます。
\(2^{T(n)} \geq n!\)
ここでスターリングの公式を使えば\(n!\)は\(\sqrt{2 \pi n}(\frac{n}{e})^n\)と近似できるので上記の式は以下のように表せます。
\(2^{T(n)} \geq \sqrt{2 \pi n}(\frac{n}{e})^n\)
この式から\(T(n)\)は\(\Omega(n\log{n})\)であることが分かります。
\(T(n)=\Omega(n\log{n})\)
つまり数字が\(n\)個あるときの比較回数は最小でも\(O(n\log{n})\)回はあることをあらわしています。比較回数が大きくなればその分計算量も大きくなるので、これは比較ソートの計算量に\(O(n\log{n})\)の壁があることを表しています。
比較しないソート
ではすべてのソートが比較ソートに分類されるのでしょうか？答えはNoです。ソートの中には比較をしないものも存在します。
例えばカウントソートは比較しないソートの一例です。数字を並べ替えるときに大小を比較するのではなく数字を数えて並べるソートアルゴリズムです。
他にもソートアルゴリズムはたくさんあるので気になる方は是非調べてみてください！
おわりに
いかがでしたか。
今回の記事ではソートアルゴリズムの計算量について解説していきました。
今後もこのような経営工学に関する記事を書いていきます！
最後までこの記事を読んでくれてありがとうございました。
自分は文系の大学生1年生です。
好きで、情報系の勉強をしています。
nlognとなる理由が非常にわかりやすかったです。
活動応援しています。
応援ありがとうございます！