memoranda2016-08-07SortアルゴリズムについてBubbleソート、Quickソート、Mergeソート、をpythonとCで実装してみた。pythonはバグがあるので、Cを参照のこと。Quickソートさえ分かっていればよくて、qsortとか標準ライブラリを使えば良いと思っていたけれど、Mergeソートに負けてしまった。ソート対象の配列が非常に大きい場合は、リスクを回避という観点で言えば、QuickソートよりMergeソートの方が良さそう。あとは、どのくらいソート対象の配列にランダム性があるのかどうか、という点も考える必要があるかもしれない。pythonの方では、指定した数の倍のシーケンシャルなリストを作った後で、指定した数だけサンプリングし、その順序をランダマイズしたリストをソート対象としている。Cの方では、重複した値をテストするために、データをサンプリングする過程で100回に1回データの重複が発生するようにしている。Cで試したところ、mergeソートの方がquickソートよりも常に速いが、あるデータサイズを超えると、quickソートの方が速くなる。いうか、mergeソートがかなり遅くなる。これはおそらく、mergeソートの実装の方がメモリを消費するので、先に上限に達してしまうからだろう。mergeソートは必ず全ての要素を最小単位まで分割するため、quickソートよりもメモリの消費量は多い。(実装でうまく回避できるのかもしれないが)ちなみに、メモリ量を最も抑えられるのはBubbleソートですね。必要なメモリは、ソート対象の配列と一つの変数だけ。スピードは非常に遅い(平均の計算量がO(n2))けれど使用可能なメモリ量に厳しい制限があり、かつ、ソート対象の配列のサイズが小さいことが分かっていれば、Bubbleソートが解になりそうです。仮想マシンのスタックとネットワークI/Oについて月別アーカイブ参加グループインターネットテクノロジープログラミングはてなブログをはじめよう!nishidyさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。