ソートアルゴリズム高速化への道 - kivantium活動日記

先日、アルゴリズムの授業でソートのアルゴリズムをいくつか習いました。ソートアルゴリズムの名前と原理くらいは聞いたことがありましたが、実装したことはなかったのでいい機会だと思い実装してみることにしてみました。ただ実装するだけでは面白くないので高速化の限界に挑戦してみたいと思います。 計測用プログラム 今回の計測では、ランダム値が入った配列のソートを100回行い、平均時間を各アルゴリズムに競わせるというシンプルなルールにしました。プログラムは以下の通りです。 C++11で入ったメルセンヌ・ツイスタなどの機能を使っているので、ビルド時には-std=c++11を指定する必要があります。 実験に使用したパソコンのCPUはCore i3-3227U@1.90GHz、コンパイラはgcc version 4.8.4で最適化オプションには-O3を指定しました。 #include <iostream> #in

[hyottokoaloha]

プロだ・・・

[ragion]

「ピボットに選ばれる数が配列の最小値であった場合は無限ループに陥る」ってどういうことだろう？

[ziyaretci]

再帰版でも十分に速いから満足したんだろうけど、クイックソートは再帰なしで実装もできるよ。

[masayoshinym]

新人研修でクイックソートで躓いた過去を思い出した。

[n2s]

再帰版でも十分に速いから満足したんだろうけど、クイックソートは再帰なしで実装もできるよ。非再帰版のスピードも計測してみてほしい。

[aipacommander]

並列化はドキドキする

[pipehead]

バブルソート, 挿入ソート, マージソート, ヒープソート, クイックソート