C++で基数・バケットソートを実装したら速いのか?

はやいの?


事前知識

32bit整数をソートすることにする。
下位から4bitごとにバケットソートを行う。(よって、N=8)
データ数N。

基数・バケットソートの計算量%$O(MN)$%
クイックソートの計算量%$O(N \log(N))$%


STL君(quicksort) 1.47s



基数バケットソート 3.01s



だめじゃん・・・これ。

queueに突っ込んで、追い出して…あたりのメモリ操作に時間喰われている感じでしょうか?


基数要素を排除したバケットソート(0-255)なら何とか超えました。整数範囲がかなり制限されてしまいますが。
バケットソート 1s
http://ideone.com/za0Vxp 1文字変えただけなのでURLだけ


このくらいの差ならstd::sortで十分そうですね。
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

コメントの投稿

非公開コメント

プロフィール

舞葉(ぶよう)

Author:舞葉(ぶよう)
github.io
はてなブログ(競プロ)

古い記事のソースコードは色分けしていないので、高機能テキストエディタに貼り付けたほうが見やすいかも。

検索フォーム
このブログについて
自分がつまづいた話題、なんとなく書きたいと思ったこと、ググったけど殆ど資料なかったぞオイ な話等をアップする予定。通りすがりでも、参考になっていただければと。プログラムの例外入力、メモリリークは責任負いません。投稿された記事は修正・削除する場合があります。
カテゴリ
タグ

HSP3アルゴリズムとデータ構造c++RubyJavaUnity画像解析C機械学習C#LinuxcodeIQKinectMinecraftTonyuSystemraspberrypiPythonHTML5音声制御Simulinkruby俺ルール通信制御Javascriptシミュレーション

counter-shinobi
固定記事
最新記事
最新コメント
月別アーカイブ
ブロとも申請フォーム

この人とブロともになる

アクセスランキング
[ジャンルランキング]
コンピュータ
1253位
アクセスランキングを見る>>

[サブジャンルランキング]
プログラミング
219位
アクセスランキングを見る>>