注意
筆者はソートのプロでもなんでもないので、各々のソートの最適仕様を実装して競わせているわけではありません。ひどいとプログラムにミスがあるかもしれません。もし間違いやおかしな点がありましたらお手柔らかにご指摘いただけると幸いです。
また今回の計測結果では、同じ条件下でもソート時間に倍近くの差がでることが確認されてます。故にこの計測結果が統計的に意味があるとは言えません。（つまり半分ネタ要素として見ていただけば）
目的
アルゴリズムの勉強でソートを勉強していたのですが、ソートって色々ありますよね？早い、遅いと言われている色々なソートアルゴリズムが、実際はどれくらいの違いが出るのか気になったのでたくさんのソートを実装し、彼らにレースしてもらうことにしました。
実施環境
google chrome Version 89.0.4389.82
使用言語:javascript
PCやCPUは特別良いものではない、一般のノートPCです。
実施内容
走ってもらうソートたち:12名
名前が長いのでグラフでは「」に書いた一文字で表記します。
「泡」バブルソート
FOR文の中身が実質3行で処理でできる超お手軽ソート「挿」挿入ソート
整列されている配列に未整列のデータを挿入していき、徐々に整列していく「選」選択ソート
未整列のデータから一番小さい値を比較で探す。人間らしいやり方。「精」ノームソート
整列されてないデータを見つけると、整列されている箇所に向かってバブルソートする。「基」基数ソート
下位の基数ごとにバケットソートする。データの最大値が大きほど遅くなる傾向大「振」シェーカーソート
バブルソートのスキャンを双方向に行うタイプ「櫛」コムソート
間隔を開けた状態からバブルソートし、徐々に間隔を縮めていく。「貝」シェルソート
データを分割して各々で挿入ソートを行うことで効率的にソートする「早」クイックソート
基準値より大きいものと小さいものに区分していく（今回は中央インデックスが基準値）「積」ヒープソート
２分木の構造を利用して効率的に一番大きい数を探しだす「結」マージソート
まずデータを分割して二組の集合からソートし、徐々に集団を結合させていく「メ」jsの配列メソッドである.sort()
開発者様の恩恵により、現状最も手軽かつ最も高速ににできるソート。中身はブラウザに依存する
条件
乱数を一定数発生された配列を様々なソートアルゴリズムでソートさせ、かかった時間を出力させて確認する。
経過時間の計測にはDateオブジェクトを使用した。
発生する乱数の幅は0~100までとする。
値の幅は1000~20000までを1000こ間隔で増やしていきながら計測した。
レース結果
上位6ソート
1~3位の差は数ミリ秒しか存在せず、各々のソートで8msくらいの差異が生じていますので、実質的には同等の性能です。
**1位：シェルソート **
一応推奨されている「データ数/3h-1」等分に分割する方式でソートさせたとはいえ、一番早いとは意外（誤差次第でひっくり返ります）。え？貴方ってこんなに優秀だったの？
**2位：基数ソート**
今回はデータの幅が100までしかないので、1の位,10の位、100の位だけでソートすれば終わってしまう。有利な条件で測定しているとはいえ、既存関数のソートより早いとは意外。ちなみに乱数の幅を0~2万にすると25ミリ秒前後となり、5位のマージソートより若干遅いくらいになる。
**3位：メソッドソート**
実験開始時では最強候補だった。恐らく中身も一番凝っているはずのソートであるが、まさかの３位。
**4位：コムソート**
シェルソート風のバブルソートが他の最強3ソート(シェル、マージ、クイック)の内、2体を抜いて4位に入りました。あまり聞かないソートだったのにこんなに早いとは、しかも理解すれば手軽なアルゴリズムだし。（もっとも、間隔の狭め具合の研究が進んでいたからとも言える。）
**5位：マージソート**
最強3ソートの一角、マージソート様は4位の2倍近い時間をかけてゴールしました。勿論このマージソートは改良を加えたやつではなく、素朴なマージソートです。
**6位：クイックソート**
クイック「なんてこと！最速と言われる私がなぜこんな順位にならないといけないの！？」
筆者「クイックソートにも質の良し悪しがあるようですからね。私には質の低いやつしか作れませんでした。サーセン。」
※
本物のクイックソートはこんなに遅くないはずです。恐らくメソッドソートの中身が本気のクイックソートだと思います。同じクイックソートでもこんなに差がつくんですね。
下位6ソート
7位:挿入ソート
ようやく基本3ソート(挿入、バブル、選択)がきました。6位のクイックソートの約4倍の時間がかかったとはいえ、実装自体はクイックソートの1/4時間もかかりませんでした。手軽さに対するコスパが高いっすねー。
**8位:シェーカーソート**
バブルソートを双方向で行うやつ。仕組みはなんとなくわかるが実装当初はなぜかバブルソートより遅かった。修正して早くはなったが、結局のところ若干の違い。バブルに手を加えるならコムソートのほうが良いよ。
**9位:バブルソート、ヒープソート **
ごめんなさいm(＿ ＿)m。ヒープソートがこんなに遅いわけないです。でも仕組みは積み木のはずなんですが。何がこんなにヒープソートを遅くさせたんだろう？？
一方で「遅い（速度が）」「短い（コードが）」で有名なバブルソート。（スリープソートを対象から外した時点で）当初は正直こいつが最下位だと思っていました。ソート済みの箇所を再スキャンしないようにした質の良い方とはいえ、最下位じゃなくて良かったね！
**11位:選択ソート**
一番小さい値を見つけるために全部のデータを比較させる手間をかけるこいつは確かにバブルソートより遅いのも納得。バブルは一番小さい値を動かすついでに他の並び替えも若干するからね。数が少ないなら人間的にもやりやすいけど、万単位になると流石に対応できない。。
**12位:ノームソート**
選択ソートと似て非なるもの。未整列の領域を進めるたびにいちいちバブルソートで一つのデータを再整列させるって、そりゃあ遅いだろうね。。
ソートレースさせるために作ったサイトを紹介
今回ソートレースを実装するために１サイトを作り、そこで計測をしました。せっかくなのでURLを貼らせていただきます。
https://akimakitools.coresv.net/sort/sortSimulator.shtml
「ctrl+U」で恐らくコードも見れます。
こちらではソート速度の他に、交換回数や出力までの時間なども計測できます。またソートレースに参加できなかったスリープソートもあります（なぜ出れなかったかは試せばわかります）。比較回数の計測は未実装です。
「allsort」のボタンは全ソートを一括で計測させるボタンです。かなり重いので注意。
実際にやってみると、ソート速度なんかより出力時間の方がずっと大きいことに気づきます。2000データの数字を出力するだけでもだいぶ重いですから。（考えてみれば当たり前ですが。。）
