ソート・整理整頓の話

ソート（ものを整列させる）は生産性向上のために重要な作業です。

靴下の整理や本棚の整理、ファイルの整理など色々な場面で私たちはソートをします。今回はソートの理論とそれを日常に活かすにはどうすればいいのか考えてみます。

1. なぜソートをするのか (ソートの目的)
2. ソートとトレードオフなものは何か
3. ソートには規模の不経済が働く
4. 色々なソート
5. 日常や自然の中のソート
6. 終わりに

　　ソートを行う目的を理解することは非常に大切です。でないと自己満足でしかない作業に時間を割くことになり、結果としてそれは生産性を低下させるからです。

ソースを行う目的は結局のところ

「人間の目に利用しやすい形で物事を掲示すること」に着きます。

そして人間が利用する形とは

①  ソートを行うことでそれまで見えなかった情報が見えるようになる

例：データを整理することで規則性に気づいたり、データの漏れに気づくなど

②  検索をするときに楽になる

例：Google検索は検索よりむしろソートをして世界中の情報から検索した人に有益であろう上位10件程度の情報を示してくれていることに本質的な価値がある。

以上のような目的に沿うようなソートが行う価値のあるソートです。それ以外のソートは自己満足でしかないのでやっても価値を生みません。このあたりの話については次の「ソートとトレードオフなものは何か」で説明します。

　　ソートに限らず私たちの作業の多くはトレードオフです。つまり、ある作業に時間を費やす分だけ、他の作業に費やす時間が少なくなります。ですので生産性を上げるにはソートを行うのは他の作業の時間をより大きく減らせる場合に限ります。そしてソートとトレードオフな作業が検索です。

　　ソートはいわば検索の下処理のようなものです。先に整理しておくことで後で探すのを楽にするのがソートだからです。そう考えると、ソートせずにあえてカオスのまま残しておく方がトレードオフを考えた場合に生産性が高いものがあります。例えば、一人暮らしの食器棚を綺麗に皿やコップ別に並べるというソートです。確かに並べておいた方が後で「フォークはどこだ？」と言った（検索）時に早く見つけられますが、フォークまできちんと並べるソートのコストを考えるとごちゃ混ぜの洗い物の中からフォークを見つける方がコストは低そうです（一人暮らしなら食器も少ないですし）。メールなども同じで、綺麗にフォルダ分けしなくとも名前やメール本文の一部で検索すると容易に見つけることが多いので普段からソートをするよりもその場で検索のコストを払う方がコストが低くなりそうです。

　　このように物をソート（整理）するかどうかは、その後の検索にかかるコストと比較して考えるべきです。

　　一般的に生産単位あたりのコスト（一個のものを作るのにかかるコスト）を下げるには業務の規模を大きくします。

例：1人分の食事を2回作るより2人分の食事1回作る方が1食分のコストは低くなる。

しかし、ソートの場合は規模が大きくなると1つあたりのソートにかかるコストは大きくなります。つまり、ソートする対象が増えるほど、一つのものを並べるのに必要なコストは増えてしまいます。

例：50冊の本を並べるのに1冊の場所を決めるコストと100冊の本を並べるのに1冊の場所を決めるコストは後者の方が大きい。

つまりソートのは規模の不経済が働く。そう考えるとデータの整理や片付けは規模が大きくなる前にこまめにソートしておくのが大事である（コストが低くなる）のがわかります。

あとからソートしようとすると、それだけ1つのデータを整理したり、1つのものを片付けるためのコストが高くなるからです。

この後紹介する色々なソートもこの規模の不経済を解消することでソートにかかるコストを抑えています。

ここでは幾つかのソートの仕方を紹介してみます。

ソートを比較するのに重要なのがビッグO(オー)です。これは最悪の場合にそのソートにかかる時間と問題のサイズの間の関係を表すものです。

要するには、ある対象をソートし終わるのに最悪の場合どれくらいの時間がかかるのかを対象の個数nを使って見積ったものです。

（ビックO自体はソート以外のアルゴリズムでも利用されます）

本棚にある順番がバラバラの本を「あいうえお」順に並べる場面を考えて書くソートを説明します。

• バブルソート(O(n^2))　

　本棚の左端から右端まで2冊ずつ見ていき順番が逆のものがいたら入れ替えるという操作をする。右端まで行ったらまた左端から同様のことをする。これを繰り返して1つも入れ替えることなく右端まで行けるようになったらソート終了。

• 挿入ソート(O(n^2))

　本を一旦全部本棚から出して1冊ずつ入れ直す方法。2冊目以降は左端から見て行って手に持ってる本が置かれるべきところがきたらそこに本を置くという作業を繰り返す。

• マージソート(O(n log n))

　本をいくつかのグループに分けてその中でとりあえず順番を並べる（規模が小さいのでコストが低い）。そのあとで2つのグループを照合して一つのソートされたグループにする（照合は2つのグループそれぞれの一番先頭を見比べてあいうえおで若い方を本棚にしまう。を繰り返す。)照合を繰り返して最後グループが一つになったら終了。

• バケットソート

　あらかじめ「あ行」「か行」みたいなバケットと呼ばれる箱を用意しておいて本棚にある本をとりあえずバケット何の順番は気にせずにあ行のものはあ行バケットへ、か行のか行バケットへ放り込む。そのあと箱の中でソートして並べる。

（麻雀の牌を並べる時はマンズとかソーズというバケットで集めてそのあと、その中で順番並べよるように私はしていますがそれと同じですね）

このような感じで色々なソートのアルゴリズムはあります。

適材適所で使い分けることが大事です。私たちが日常でソートするときはコンピュータほど現実じゃないので、いろんなソートをベースにアレンジして使えばいいかなと思います。（むしろ自然とそうしてると思います）

• スポーツとか大会の順位決めもソートだったのか！

スポーツなどの大会で順位を決めるのもある意味ソートです。出場者の集合を実力順にソートするというのと同じです。ただし、実際の大会は無駄なく全出場者の順位を決めるようなアルゴリズムではなく試合が盛り上がるとか不確実性（優勝チームがなかなか決まらない）とか、試合数を少なく（あるいは多く）することが実際は行われています。

その理由は、ただただ順位を効率的に決めることがスポーツやゲームにおいて正ではないからです。

＊ソートをうまく使えば、不確実性をコントロールした大会が開催できる。こういうのうまく使えばすごい盛り上がるように設計できそうな気もします（実際そうされてると思いますけど）。

• 動物の群れにおける序列もソートと検索のトレードオフで説明できる

ケンカというものであらかじめ群れの中で序列を決めておけば、交尾や食料の取り合いのたびに争わなくて済見ます。つまり、ケンカであらかじめ群れの中の序列をソートしておけば、後で

どっちが強いとか「検索」しなくて済むということです。そして、本気の争いが起きるのは、２個体の間でこの序列が食い違う時となります。（そしてソートに失敗して勘違いしてた方がおそらく負けます。あるいはたまたま勝って序列が変わります。）

• レースを使えば一発で序列を決めることができる

　　序列を決めるためにはケンカなど「戦い」を用いるソートよりも一発で決まる効率的な方法があります。それはレース（競争）です。マラソンをみればわかるように、２選手ずつマラソンを何回も走って順位を決めるということは必要ありません。タイムという基準さえあればそれぞれが記録を出して基準に照らして一気に序列を決めることができます。動物も体の大きさなどを利用してケンカをせずとも序列を決めています。

　　ソートとかレースとか検索って普段から何気なくやっていますが、深いところで繋がっていて面白いなあと思います。

今回はここまでです。最後までお読みいただいてありがとうございました。

＊今回の記事はアルゴリズム思考術　第3章のソートを参考にしています。