コンテンツメディア事業本部の新卒エンジニア坂本がお送りいたします。
突然ですが、皆さんの好きなソートアルゴリズムはなんですか？ 私は基数ソートのスマートでストイックな雰囲気に惹かれます。
とはいえ、普段の開発では「どのソートアルゴリズムを使うか」を意識することは少ないのではないでしょうか。 むしろ現実世界で「トランプが全部揃ってるか」を手作業で確認するときとかのほうが、実はソートアルゴリズムが必要なのかもしれません。
ということで（？）、そのような現実的な場面で、本当に実用的なソートアルゴリズムを決める戦いが始まりました。
選手紹介
今回試したソートアルゴリズムは、独断と偏見で選んだ以下の5種類。
1 挿入ソート
- シンプル・イズ・ベスト！正直言ってベンチマークの噛ませ犬！
2 クイックソート
- 「クイック」の名前はダテじゃない！王者の貫禄を見せてやれ！
3 マージソート
- 安定感のある隠れた実力者！魅せるソートで人気も優勝もかっさらえ！
4 基数ソート
- 彼氏にしたいソートアルゴリズムNo.1！数値のソートは任せろ！
5 鳩ノ巣ソート
- メモリ大食らいの暴君！現実世界でその夢のようなスピードは出せるのか！？
堂々たるメンツが揃い踏みです。 それぞれのアルゴリズムの説明はここでは省略します。
また、「ヒープソートは？」「スリープソートは？」「ボゴソートは？」などの意見は一切受け付けませんのでご了承ください。
ルール
- ランダムにシャッフルされた数字の書かれた64枚のカード （今回使用したのはニムトのカード）を、
- テーブル上で手作業で並び替えて
- 要したタイムを競う
これを上記5つのソートアルゴリズムでカウンターバランスをとりながら、それぞれ3回ずつ計測しました。 下記のランキングでは3回の計測のうち最短のものを採用しています。
また、暗黙の了解として「カードが4,5枚の場合は目視でソート可（アルゴリズムを意識しなくてよい）」というルールも加えました。 実用的には4,5枚だったらアルゴリズム意識するよりパパッとやったほうが速いでしょうし。
なお、シャッフルについてもそれなりにランダムになるよう、
- 麻雀式のごちゃ混ぜシャッフルを1回
- ヒンズーシャッフル（一般的なカードシャッフル）を1分間
というルールで行いました。
そして、ソート後に正しくソートされたかチェックして、間違っていたらやり直しというルールを設けました（マゾい）。
結果
5位から順に発表します！
（※GIF動画が非常に重いため、スマートフォンだとスムーズに表示されないおそれがあります）
5位 マージソート
記録 3分38秒！
やる気が感じられませんね！マシンというフィールドでは優秀なマージソートも、本当に「実用的」とは言えないようです。
しかもこの記録、少々やり方を工夫した結果です。最初は単純に2つの束を1つの束にマージし続けていましたが、非常に遅かったので4つの束を1つの束にマージする方法にしたところだいぶ改善されました。それでも最下位ですが＾＾；
まあソートしている間は結構楽しいので、ソートに楽しさを求める方は一度お試しあーれ。
4位 クイックソート
記録 3分30秒！
クイック（笑）
見た目だけは非常にクイックですね。 上記のGIF動画ではものすごい勢いでカードを捌いているように見えますが、やっぱり無駄な動きが多いのでしょうか。 優勝候補の一角だっただけに残念な結果です。
こちらも少々工夫をしていまして、ピボットを10の倍数にするなどして人間が（私が）一瞬で判断できる値を採用しています。 一枚一枚サクサクとふるい分けていくので体感のスピードはなかなかですが、クイック感を意識しすぎるとミスが出ます。 2回ミスっていたせいで合計5回計測する羽目に……。はっきりいって人間向きではありません。
3位 挿入ソート
記録 3分02秒！
まさかの健闘です。
特徴はなにより全くスペースを必要としないことですね。 さらに、極めて単純なので脳のリソースもほとんど使いません。 友人と喋りながらでもできそうです。
ただ、圧倒的に地味です。ソート中のワクワク感を大切にする方にはオススメできません。 あとこちらも1回ミスをしましたが、やり直しの落胆っぷりはクイックソートのそれを遥かに凌駕します。
2位 基数ソート
記録 2分35秒！
基数ソートさんステキ！
安定感もさることながら安心感が強いです。 特に今回はソート対象が2桁の整数だったため、その力を遺憾なく発揮できたといえるでしょう。 カードの枚数が増えても何とかなりそうな包容力も魅力的ですね。 筆者の個人的な好みを抜きにしてもオススメです。
1位 鳩ノ巣ソート
記録 2分08秒！
ということで栄えある一位は鳩ノ巣ソートさんでした！
もう完全に力技ですね。机のスペースをあますところなく使っています。 カードの枚数が増えたらスペースが足りなくなるって？ そしたらもっと大きい机を用意すればいいじゃない。
鳩ノ巣ソートさんにはこれからもぜひ、他人に流されずに自分の人生を歩んでもらいたいと思います。
考察
なぜこのような結果になったのでしょうか。
実際にソートしてみて分かったこととしては「カードを拾い上げる動作が遅い」ということです。 マージソートもクイックソートも、一度机に置いたカードを拾って持ち直す回数が多いのです。 一方で鳩ノ巣ソートは一度置いたカードはずっとそのままで、拾い上げの動作は最後にカードをまとめることろくらいです。
また、「1対1で比較するより一気に複数を比較するほうが速い」ということです。 人間はマシンと違って「35は17より大きいか」と「35は17, 26, 45, 64, 83に対してどこに位置するか」とでは、判断してカードを並べるのにかかる時間は対して変わらないのではないかと思います。
認知科学分野の方面から槍が飛んできそうなテキトウな考察ですが、どうか夏休みの自由研究を見るような温かい目で見守ってくださいm(_ _)m
まとめ
ということで「机のスペースが十分に確保できるなら鳩ノ巣ソート、そうでなければ基数ソート」という結論になりました。 この記事がみなさまの充実したソートライフの糧になりましたら幸いです。
え？タイトルで「たったひとつの」って言ってるだろって？
はて、なんのことやら……
