ソートアルゴリズムについて

　大小関係が定められたたくさんのデータを、小さい順（昇順）あるいは大きい順（降順）に並べ替える作業をソート（整列）と言い、それを行うアルゴリズムをソートアルゴリズムと言います。 この処理は、さまざまなプログラムの中で頻繁に使われ、それ故、古くからいろいろなアルゴリズムが考案されてきました。

参考文献:いろいろなソートアルゴリズム

動機

　ソートの勉強を調べていたらソートアルゴリズムがたくさんあることに少しだけ疑問があった。
　なぜなら数字などを順番に並び変えるのにソートアルゴリズムなんて一つで十分ではないのか？と思ったという素朴な疑問。
　一つ一つ調べると、どのソートが効率が良く、どのソートが効率が悪いなど色々あることが分かったのですが、どれが良くてどれが悪いかを知るだけじゃいまいち物足りない気のするので実装してみようと思いつきました。
　その中で代表的なものの中の5つのソートアルゴリズムの速度を比較したいと思います。(ちなみに昇順に並べるコード)

測定するアルゴリズム

• まず1つ目はソートと聞いて自分がパッと思いついた”バブルソート”です。これは比較的短いコードで書け、簡単なアルゴリズムですがソートアルゴリズムの中でもかなり効率の悪いアルゴリズムで、計算量はO(n^2)。
• 2つ目は先ほどのバブルソートの改良版の”シェーカーソート”というもので、計算量はO(n^2)。
• 3つ目はシェーカーソートよりは速いがクイックソートよりは遅い”挿入ソート”で、計算量はO(n^2)。
• 4つ目はソートの中でも高速とされる”クイックソート”で、計算量はO(nlogn)。
• 5つ目はC++のライブラリである”標準ソートです”。

実装

データサイズを1から10億をそれぞれ10回測定しそれらの平均の時間を調べた。

結果

結果は以下の表にまとめた。

　空白の箇所はあまりにも時間がかかるため断念したところです。
　データサイズが少ないと一般的に速いとされているクイックソートや標準ライブラリによるソートが他のより若干遅いことがわかりました。
　ただデータサイズが大きくなるにつれやはり高速と呼ばれるクイックソートと標準ソートは100万まではデータサイズが小さい時とあまり変わらない速度でソートしてます。
　10億といった値だとなんと標準ソートの速度がクイックソートの半分といった結果でやはりライブラリは強い
　要するに

であることが分かりました。