コンテンツメディア事業本部の新卒エンジニア坂本がお送りいたします。

突然ですが、皆さんの好きなソートアルゴリズムはなんですか？私は基数ソートのスマートでストイックな雰囲気に惹かれます。

とはいえ、普段の開発では「どのソートアルゴリズムを使うか」を意識することは少ないのではないでしょうか。むしろ現実世界で「トランプが全部揃ってるか」を手作業で確認するときとかのほうが、実はソートアルゴリズムが必要なのかもしれません。

ということで（？）、そのような現実的な場面で、本当に実用的なソートアルゴリズムを決める戦いが始まりました。

f:id:sakmt:20150816194448j:plain

選手紹介

今回試したソートアルゴリズムは、独断と偏見で選んだ以下の5種類。

1 挿入ソート

シンプル・イズ・ベスト！正直言ってベンチマークの噛ませ犬！

2 クイックソート

「クイック」の名前はダテじゃない！王者の貫禄を見せてやれ！

3 マージソート

安定感のある隠れた実力者！魅せるソートで人気も優勝もかっさらえ！

4 基数ソート

彼氏にしたいソートアルゴリズムNo.1！数値のソートは任せろ！

5 鳩ノ巣ソート

メモリ大食らいの暴君！現実世界でその夢のようなスピードは出せるのか！？

堂々たるメンツが揃い踏みです。それぞれのアルゴリズムの説明はここでは省略します。

また、「ヒープソートは？」「スリープソートは？」「ボゴソートは？」などの意見は一切受け付けませんのでご了承ください。

ルール

ランダムにシャッフルされた数字の書かれた64枚のカード （今回使用したのはニムトのカード）を、
テーブル上で手作業で並び替えて
要したタイムを競う

これを上記5つのソートアルゴリズムでカウンターバランスをとりながら、それぞれ3回ずつ計測しました。下記のランキングでは3回の計測のうち最短のものを採用しています。

また、暗黙の了解として「カードが4,5枚の場合は目視でソート可（アルゴリズムを意識しなくてよい）」というルールも加えました。実用的には4,5枚だったらアルゴリズム意識するよりパパッとやったほうが速いでしょうし。

なお、シャッフルについてもそれなりにランダムになるよう、

麻雀式のごちゃ混ぜシャッフルを1回
ヒンズーシャッフル（一般的なカードシャッフル）を1分間

というルールで行いました。

そして、ソート後に正しくソートされたかチェックして、間違っていたらやり直しというルールを設けました（マゾい）。

結果

5位から順に発表します！

（※GIF動画が非常に重いため、スマートフォンだとスムーズに表示されないおそれがあります）

5位マージソート

f:id:sakmt:20150816203903g:plain

記録 3分38秒！

やる気が感じられませんね！マシンというフィールドでは優秀なマージソートも、本当に「実用的」とは言えないようです。

しかもこの記録、少々やり方を工夫した結果です。最初は単純に2つの束を1つの束にマージし続けていましたが、非常に遅かったので4つの束を1つの束にマージする方法にしたところだいぶ改善されました。それでも最下位ですが＾＾；

まあソートしている間は結構楽しいので、ソートに楽しさを求める方は一度お試しあーれ。

4位クイックソート

f:id:sakmt:20150816204023g:plain

記録 3分30秒！

クイック（笑）

見た目だけは非常にクイックですね。上記のGIF動画ではものすごい勢いでカードを捌いているように見えますが、やっぱり無駄な動きが多いのでしょうか。優勝候補の一角だっただけに残念な結果です。

こちらも少々工夫をしていまして、ピボットを10の倍数にするなどして人間が（私が）一瞬で判断できる値を採用しています。一枚一枚サクサクとふるい分けていくので体感のスピードはなかなかですが、クイック感を意識しすぎるとミスが出ます。 2回ミスっていたせいで合計5回計測する羽目に……。はっきりいって人間向きではありません。