ソートアルゴリズムを熱く語ろう♪
■ このスレッドは過去ログ倉庫に格納されています
000155
NGNG000257
NGNG珠玉のプログラミングにのってたbitsortにはびびった。
http://www.programmingpearls.com/
http://www.programmingpearls.com/code.html
つーか、勉強不足なだけか・・・。
0003デフォルトの名無しさん
NGNG0004デフォルトの名無しさん
NGNG何故順番が安定でないかについてレポートせよ
0005デフォルトの名無しさん
NGNG答えは可能です。
クイックソートでは、前からと後ろから挟むように
前からは大さい値を見つけた時点で、
後ろから小きい点を見つけた時点で一つ交換します。
たとえば、値５と比較してる時
->3736139<-
3331 679
前から7のところで、後ろから３のところで交換が生じます
そのまま比較を続けても次の3では交換が起きませんから
そして再帰の次のステップで今度は先頭の３が一番後ろに回ってしまいます
ようは交換する時、同じ値が無いか調べて同じ値があれば
前に移すときは一番後ろのものに 後ろに移す時は一番前のものと
交換するように変更すればOK
ただし、交換する都度検索したのではクイックソートなんて
名前を付けられないでしょうね
0006デフォルトの名無しさん
NGNGつまり交換しなければならない個所にマークだけしておき、
手前から交換してゆく方法でも安定なソートが可能です
->3736139<-に対してマークだけ
---*-*@@-- とつけて
交換は前から順に交換してゆきますつまり
7<->1 6<->3 と交換します。
マークをつけずに、最初に分割点を探すだけにして
次に分割点からそれぞれ後ろに向かって比較交換しても同じですね
0007デフォルトの名無しさん
NGNGそれを「できる」と言っていいのかな〜？
現実的な解じゃない気が。
いちいち比較の時に検索しに行くって、クイックソートを使う意味があまり無い気がするし。
普通に他の安定ソート使った方が圧倒的に速いような・・・。
暇ができたら試してみようかな。
それはそーと(凍結)、ギコソートやモナソートをだれか作ってください。
0008デフォルトの名無しさん
NGNG0009デフォルトの名無しさん
NGNGその方法だと、たとえば、データが
->3736139<-
でなく、
->3736319<- だと、左から2番目の7と、右から3番目の3が交換されるので、安定
ではないような氣がしますが…
ちなみに私なら、整列前の位置をどこかに保存しておいて、普通にクイックソート
した後に、保存しておいた値を使って挿入ソートするのがいいような...
って、クイックソートから離れてしまったのでsage。
安定という命題からも離れてしまったのでsage。
あと、直観ですが、nの2乗に比例する時間か、nに比例する作業領域（マージソート
の場合はn/2?）を使わないと安定なソートはできないような氣がしますが、間違って
いたら申し訳ないのでsage。
0010デフォルトの名無しさん
NGNG0011デフォルトの名無しさん
NGNG以下は私が判る範囲で。
○安定ソート
・バブルソート
・挿入ソート
・選択ソート
・分布数えソート
・マージソート
・ラディックスソート(基数ソート)
○不安定ソート
・クイックソート
・シェルソート
○不明
・コムソート(バブルソートの親戚なので、安定？)
0012デフォルトの名無しさん
NGNG0013デフォルトの名無しさん
NGNGコムソートはシェルソートと同じで、離れた値を比較・交換し、だんだん間隔を
狭めていくので、不安定だと思います。
サイトによっては「クイックソートより高速」などと表現されていることがあります
が、私がintの配列で実装したところでは、シェルソートとクイックソートの中間
位の速度でした。（キーの型を変えれば違うかも）
あと、不安定のほうに、ヒープソートを追加キヴォン。
0014デフォルトの名無しさん
NGNGこれでいいのだ。
0015デフォルトの名無しさん
NGNG-------------------------------
○安定ソート(順序不定)
・バブルソート
・挿入ソート
・選択ソート
・分布数えソート
・マージソート
・ラディックスソート(基数ソート)
・デマイズソート ←12で追加
-------------------------------
○不安定ソート(順序不定)
・クイックソート
・シェルソート
・コムソート
・ヒープソート ←13で追加
-------------------------------
他にもありましたらお願いします。
あとは必要リソース、制限とかもあると良いかな。
0016期待age
NGNG名前 ： 安定度（5：良<->1：悪） ： 必要リソース ： 備考
バブルソート ： 4 ： ？ ： ？
挿入ソート ： 4 ： ？ ： ？
選択ソート ： 4 ： ？ ： ？
分布数えソート ： 4 ： ？ ： ？
マージソート ： 4 ： ？ ： ？
ラディックスソート(基数ソート) ： 4 ： ？ ： ？
デマイズソート ： 4 ： ？ ： ？
クイックソート ： 2 ： ？ ： ？
シェルソート ： 2 ： ？ ： ？
コムソート ： 2 ： ？ ： ？
ヒープソート ： 2 ： ？ ： ？
安定度のみでソート
--------------------------------------------------------------
0017デフォルトの名無しさん
NGNGそれはさておき、一覧にするなら計算量は必須だろうな。
また、必要リソースではなく、in-placeか否かの方がいいのではないか？
0018デフォルトの名無しさん
NGNGマージソートの欠点は無いの？
0019デフォルトの名無しさん
NGNG速度もクイックソートより遅い傾向にある。
0020名無しさん＠お腹いっぱい。
NGNG名前がダサい
0021デフォルトの名無しさん
NGNGクイックソートより遅いって、そりゃ当たり前じゃ。
0022デフォルトの名無しさん
NGNG計算時間：O(n)
制限：キーが整数で、その範囲が判っている場合のみ適用可能
作業領域：分布格納用の整数配列(例：キーが0〜127の範囲なら128個の整数配列)
逆写像ソート(安定)
計算時間：O(n)
制限：分布数えソートと同じ
作業領域：ソートする配列と同じ大きさの作業用配列が２つ
備考：分布数えソートより遅い
ところで>>16の安定度って基準は何？
もしかして５段階評価？主観で決めろと？
0023デフォルトの名無しさん
NGNG0024デフォルトの名無しさん
NGNGなぜ当たり前なのかな？
クイックソートでO(n^2)になるデータだったら
マージソートの方が速いかもしれないぞ。
0025デフォルトの名無しさん
NGNGいや、でも妙な制限無しのソートで、平均して一番速いのはクイックソートだろ。
0026デフォルトの名無しさん
NGNG0027デフォルトの名無しさん
NGNGクイックソート＞マージソート＞ヒープソート＞シェルソート＞＞他＞＞バブルソート
（ただし、条件の違う分布数えソートなどを除く）
これでいい？
0028デフォルトの名無しさん
NGNGキャッシュヒット率最強！
0029デフォルトの名無しさん
NGNG00305,6
NGNG安定にするには２度目のスキャンでは交換ではなく
挿入してシフトするしかないですね。
0031デフォルトの名無しさん
NGNGヒープソートって不安定か？
最悪の場合でも速いソートとして有名だが？
0032デフォルトの名無しさん
NGNG処理する方が多くありませんか？
というか最近ならデータベースか・・・
00332
NGNG4,10,3,8,6
0001101010100000
重複無し、データはひとつでそれに付随するデータ無しのとき使う。
http://www.programmingperls.com/bitsort.c
0034デフォルトの名無しさん
NGNGヒープソートの速度が不安定なのではなく、同一の値における整列前の順序が保存
されるか否かという観点で>>11の表は分類されていると思うのですが。
速度に関しては全くおっしゃる通りで、最悪の場合でもn log n の時間で実行
できますね。ただし、実装方法にもよりますが、最初から逆順に並んでいるデータを
好む傾向があります。
0035デフォルトの名無しさん
NGNGquick sortのLatest and Greatestな実装が解説されてます。
ソートヲタは必読ですな。
0036デフォルトの名無しさん
NGNG0037ゆたんぽ
NGNG適化版、コムソート１１。
日経バイト誌での追試（数千件くらいだったと
思う）ではクイックソートの速度を上回ってお
り、個人的に試した数万〜数十万件の文字列の
ソートでもクイックソートを圧倒していました。
0038デフォルトの名無しさん
NGNG0039デフォルトの名無しさん
NGNGcomb sort 8.13
quick sort(1) 5.06
quick sort(2) 2.81
qsort 3.06
結果は秒です。
quick sort(1)は、通常のクイックソート、(2)は要素数が10を下回った場合に
挿入ソートに切り替えました。また、qsortは標準ライブラリのqsortです。
環境は、
CPU P100
MEM 40M
OS Vine Linux 2.1
egcs-2.91.66 最適化オプションなしです。
やはりcomb sortはquick sortより遅いような気がしますが...
0040デフォルトの名無しさん
NGNG0041デフォルトの名無しさん
NGNG>>39 で
comb sortと書いてあるのは実際はcomb sort 11でした。
失礼。
004240
NGNG0043>40
NGNG0044期待age
NGNG00452
NGNG(∩∩）
0046デフォルトの名無しさん
NGNGリンク先見れないのだが
00472
NGNG(∩∩） ｽﾍﾟﾙﾐｽ･･････ｳﾂﾀﾞｼﾉｳ
http://www.programmingpearls.com/bitsort.c
0048デフォルトの名無しさん
NGNGbitsortは制限が強すぎるような気が...
0049デフォルトの名無しさん
NGNG全訳してくれ！>2
0050新世紀期待age
NGNG0051デフォルトの名無しさん
NGNGあくまでもintの配列の時の話ですが、挿入ソートに切り替える閾値は7-10の
間が良いようでした。ヒープソートに切り替えるタイミングはPlauger氏の
いうようなタイミングでいいと思います。
あと枢軸値の選び方ですが、Plauger氏の方法でも1 .. n/2 .. 1のように
並んだ配列を食わせると実行時間が倍程度になるようです。ある程度以上の再帰が
おきたらヒープソートを使うことによってスタックオーバーフローはおきないよう
になっているので、いっそのこと枢軸値はランダムに選んでもいいような気が
いたしました。で、実際にやってみたら、良好な結果を得ました。
（入力によって実行時間が極端に変化することがないということです。）
あと、以上の結果はあくまでもintの配列で自分で実装した結果ですので、
ライブラリ関数として汎用性を重んじたPlauger氏の実装と単純な比較は
できません。
そのうちPlauger氏のソースを直接いじってご報告致す所存。
0052デフォルトの名無しさん
NGNGピアソンから出ている「珠玉のプログラミング」という本を読めば詳しく書いて
あります。
私も読んでいるところであります。
参千四百円＋税であります。
0053ゆたんぽ
NGNG長さ0-200,000の文字列の配列100,000件をソートしてみました。
comb sort 721
qsort 270(ライブラリ関数)
160万件だと
comb sort 27499
qsort 6720(ライブラリ関数)
結果はmsです。環境は、
CPU PIII 500
MEM 512M
OS Windows NT 4.0 SP5
VC++ 6.0
ううむ、確かにクイックソートの方が速い。
９年前の計測はまぼろしか？
世紀をまたがってプログラムを組んでしまいました。
0054デフォルトの名無しさん
NGNG挿入ソートに切り替えるタイミングは9が定説。
0055デフォルトの名無しさん
NGNG私もクイックソートより早いアルゴリズムがあると聞いて早速実装してみて、
結果に落胆したクチなんですよね。
0056デフォルトの名無しさん
NGNG005755
NGNG鬱だ...
0058デフォルトの名無しさん
NGNG0059デフォルトの名無しさん
NGNGアルゴリズムには長所と短所がある。なにか一つの方法論に頼ろうとするな。
0060デフォルトの名無しさん
NGNGなんでもクイックソートあたりにしとけば、いいんじゃないの？
0061デフォルトの名無しさん
NGNG私はバブルソートを使うならクイックソートを使うという
一つの方法論に頼っています。
0062デフォルトの名無しさん
NGNG別にいいじゃん。
このスレッド好きだな。
0063>61
NGNG必要であればquick sortに書き換える。
quick sortはn^2地雷回避コードきっちり書くの結構面倒なので。
0064>63
NGNGquick sortとheap sortとmerge sortがあれば事足りるだろ。
あとはAVL木、キャッシュ付きAVL木、自己組織化木、オープンハッシュあたりで十分。
というわけでSTL使え。
0065デフォルトの名無しさん
NGNGハッシュとソートがどう関係あるのか教えれ。
リンクリストにつなぐときに順番を考慮して、っていうのは無しな。
もし関係ないならそう書け。
0066デフォルトの名無しさん
NGNG↑意味不明
bucket sortも便利だろ(藁
0067名無しさん
NGNGＱソートは、バブルがあまりに遅いときだけかなー。
シェル、インサート、マージ、なんかは、研修の時ぐらいしか使わんなー。
0068デフォルトの名無しさん
NGNG例えば、C言語はqsort関数が標準でついてるだろ。
sortする関数がついてない言語なんてあるのか？
0069名無しさん＠お腹いっぱい。
NGNGバケツソートってメジャー？
0070デフォルトの名無しさん
NGNGそう責めるなよ。ライブラリの使い方をしらないだけなんだから。
0071デフォルトの名無しさん
NGNG全てを壊して始めからって感じで。
0072デフォルトの名無しさん
NGNG0073デフォルトの名無しさん
NGNG0074デフォルトの名無しさん
NGNG0075デフォルトの名無しさん
NGNGちゃんと番号で教えてくれ。
0076デフォルトの名無しさん
NGNG飼い主に小便を垂れるイヌ発見
0077７６
NGNG0078デフォルトの名無しさん
NGNG誰も文句言わなかったのかなあ
0079デフォルトの名無しさん
NGNG説明できるやついねえのかよ。
大学行ってないやつはしょうがないが。
なぜ、
O(n^2)
と
nlog(n) t < c*nlog(n)
くらいの説明がでてこんのだ。
数学勉強しろ！
リンク任せにすな！
上の二つどっちがドレですか？とか聞くな！
0080デフォルトの名無しさん
NGNGおしえて♪
0081>>78
NGNG構造体の要素後とに代入しないといかんかったりするんだよね。
しぶしぶMFCみながら作りなおしたよ．．．
0082デフォルトの名無しさん
NGNG0083デフォルトの名無しさん
NGNGO(n^2)はともかく
> nlog(n) t < c*nlog(n)
って何？意味不明。
0084デフォルトの名無しさん
NGNGそれ以来、ソートにはシェルソート (そのとき Y 氏が使ったのがこのアルゴリズム) を信者の様に使っていますが、自分で作ったソートのアルゴリズムにも生き残る道がありました。私の作ったアルゴリズムは、ソートされた配列の後尾に追加されたデータをソートするときには、どのソートにも負けないので、配列に順次データを追加して結果を表示するなどというプログラムには、今でも使っています。
これって挿入ソートだろうな。
> 自分で作ったソートのアルゴリズム
って無知を晒してるだけでイタイのですが。
0085デフォルトの名無しさん
NGNG0086デフォルトの名無しさん
NGNGソートスレほど親父ギャグがでるスレもすくないね。
0087デフォルトの名無しさん
NGNGただのQuickSortだと遅すぎるんですが、
何かいいアイデアは無いですか？
お知恵を拝借したいのです。
0088デフォルトの名無しさん
NGNGhttp://www.ingnet.or.jp/~kojif/mu/comp/bwt.htm
BWTってこれ？
0089デフォルトの名無しさん
NGNGバケツ法はどう？
0090デフォルトの名無しさん
NGNGじゃあ、お言葉に甘えて「ボゴソート」Ｏ(n!)
0092デフォルトの名無しさん
NGNGクイックそーち戸？
0093デフォルトの名無しさん
NGNG基数ソートが応用できないかな？
キーが巨大だから全段実行するとO(n^2)の計算量になってしまうけれど、
ある程度緩やかにソートできたら、他の安定なソートでとどめを刺せば良さそう。
キーがサイクリックに読み替えできるのがポイント
各桁の度数分布が全部同じなのも美味しい
0094デフォルトの名無しさん
NGNGデマイズソートって何ですか？
Google にも引っかかりません
0095デフォルトの名無しさん
NGNG>>12が生み出した変形バブルソート。
009693
NGNG予備的なソートならバケツソートの方が簡単かも？
89 の方が正解か？
基数ソートやバケツソートはキーの比較が楽なのがメリット。
それで、クイックソートもピボットを特定の要素ではなく
特定の桁だけで比較する方が速いかな？
分割の効率は落ちるけれど。
あと、特殊なデータ（例オール０）だと異様に時間が掛かりそうだけれど、
対策は必要だろうか？
009792改
NGNGクイックソート？
009987
NGNGBWTって、比較関数をどれだけ呼ばないで済むか、
がポイントになると思います。文字列比較なんで。
そうなると比較結果のハッシュとかまで
考慮しなきゃいけないのかなぁ。
0100デフォルトの名無しさん
NGNG0101デフォルトの名無しさん
NGNG配列要素の値のビット数分でいいって、どっかの本に載ってたけど、
どういう根拠でしょう？
■ このスレッドは過去ログ倉庫に格納されています