トップページ⇒tech
155コメント46KB

ソートのアルゴリズム

■ このスレッドは過去ログ倉庫に格納されています
0001デフォルトの名無しさんNGNG
2つの値を比較した時に同じだった場合、元の順序を壊さない
ソートのアルゴリズムでバブルソートよりも高速なソートって
ありましたっけ？どなたか教えてください。
宜しくお願いします。

0002デフォルトの名無しさんNGNG
バブルソートよりっておい!

クイックソートの比較関数に元の順序も比較対象にすれば？

はい終わり。
0003デフォルトの名無しさんNGNG
冬休みのレポートか。
0004デフォルトの名無しさんNGNG
ええかげんにせい・・・
0005sageNGNG
我々は1が何故このようなスレッドを立てたのかという疑問を解決するため、
1の故郷に向かった。まだ日本にこんなところがあったのか…
思わず口に出てしまった言葉を同行した友人に失礼だと咎められた。
小人が住むような小さな家、ツギハギだらけの服を着る農夫たち、そして
彼らは余所者で身なりのいい我々を監視する様に見詰めている。
高度成長だの、神武景気だの、ワールドカップだので浮かれていた我々は改めて
農村の現状を噛み締めていた。ボロ屑のような家に居たのは老いた母親一人
我々を見るなり全てを悟ったのか、涙ながらに息子が申し訳ありませんと
我々に何度も土下座して詫びた。我々はこの時初めて1を許そうと思った。
誰が悪い訳ではない、農村の貧しさが全て悪かったのだ。我々は1の母親から
買った干し柿を手に、打ちひしがれながら帰路についた

0006デフォルトの名無しさんNGNG
マージソートならO(nlogn)だ。
２〜５は、ソートの安定・非安定について勉強すること。
0007２〜５NGNG
>>ソートの安定・非安定

ようするに
>>2つの値を比較した時に同じだった場合、元の順序を壊さない
だろ?
0008２NGNG
んなこったあ、わかってんだよ。
クイックソートは非安定だ。
けど、ソート以前の順序を、比較関数に適応することことで
結果的に安定になるの。
0009デフォルトの名無しさんNGNG
＞２
「元の順序も比較対象にする」と
「2つの値を比較した時に同じ」ではなくなってしまいます
かってに条件を変更しないでください。
0010デフォルトの名無しさんNGNG
>>8=2
qsortとかのライブラリで、交換をどう制御するんだ？
馬鹿？
0011デフォルトの名無しさんNGNG
>9,10
だめだこいつら...
0012>11NGNG
どうダメなのか説明してみ
ダメだけ言って逃げるなよ
0013デフォルトの名無しさんNGNG
>11=8=2なら、詳しく説明しろ。
0014名無しさん＠お腹いっぱい。NGNG
>>12-13
ホント馬鹿だな（藁
0015デフォルトの名無しさんNGNG
お、逃げたな。
結局答えられないだけだろ(ﾜﾗ
「馬鹿」しか書けんならさっさと逃げて消えろや
0016デフォルトの名無しさんNGNG
２じゃないけど。

二つの値が同じだった時だけ
順序を比較するんでしょ？ >>12=13

説明しろとかいう前に自分の頭で考えたら？
あ、考えてもわからなかったんだー（藁

0017デフォルトの名無しさんNGNG
>>14=11=8=2
ふぁあーあ、消防相手にしてたのか。もう寝るわ。
んじゃ、2の反省文は宿題にしておく。今日の朝までに提出する事。いいな？>2
0018デフォルトの名無しさんNGNG
>>16
どうせ想像だけで検証なんかしてないんだろ。
そんな単純な考え方じゃだめなんだって！
もっと良く考えてみ？
0019デフォルトの名無しさんNGNG
>17 あーあ、もう引っ込みつかないね。かわいそ。
一晩寝て、頭スッキリさせてから、出直しておいで。
00201=2NGNG
ただの中傷合戦になってきたので
＝＝＝＝＝＝＝＝終了＝＝＝＝＝＝＝＝
0021デフォルトの名無しさんNGNG
おいおい勝手に終らすなよ。>20=2
全然中傷じゃないって。２も理解してない様だし。
0022デフォルトの名無しさんNGNG
>>21
多分、理解していないのはあなただけです。
0023だから1=2だってNGNG
＝＝＝＝＝＝＝＝終了＝＝＝＝＝＝＝＝
0024デフォルトの名無しさんNGNG
オイオイ、１が知りたいのはバブルソートより高速なソートだろ？
だったら、マージソートでもクイックソートでも良いじゃねーか。
0025デフォルトの名無しさんNGNG
＞2
まだわかってないのか？
アホ相手は疲れるね。

同じ値の比較だけならば、交換は行われないので、入れ替わる事はない。が、
比較で異なった時に行われる要素の交換で、同じ値が入れ替わらない保障が無いのが「安定しないソート」。
そもそも同じ値かどうかはソートが完了するまで判明しないので２の考えには無理がある。
反省文は朝までに各自提出する事！
0026デフォルトの名無しさんNGNG
>24,25
だめだこいつら...
0027名無しさん＠お腹いっぱい。NGNG
全員馬鹿。
クイックソートした後にソート前の順番（インデックスを参照して）でバブルソートするのが一番効率的だ。
同じ文字の確立なんて低いだろ？
マージなんか使うな低脳！
お前等全員リストラだ！！
0028＞２６NGNG
２６及びその部類達は答えが欲しいがために挑発をつづける厨房です
反応してはいけません
0029sageNGNG
>比較で異なった時に行われる要素の交換で、同じ値が入れ替わらない保障..
ニッポンゴ ムツカシーネ
0030デフォルトの名無しさんNGNG
>同じ文字の確立なんて低いだろ？
勝手に決めるな
0031名無しさん＠お腹いっぱい。NGNG
＞29
マジ馬鹿発見！
煽ったつもりだろうが自分の低脳振りをアピールしただけだぞ。
真性厨房だろ（藁
0032デフォルトの名無しさんNGNG
>25
君もういいよ。お布団へお入り。
003324NGNG
>26
理由書けよ。
0034このスレはNGNG
フィーバーしてます。
0035デフォルトの名無しさんNGNG
フィーバーと言うよりエゴのぶつかり合い。
VB vs Delphiと余りかわらん。
0036デフォルトの名無しさんNGNG
stable sortの意味が分かっていない人間と
stable sortでなくても順序付けにindexを含めれば同等に処理できるという人間と
バカなやり取りをしていることが分かってて煽ってる人間と、
なにが間違ってるのか分からないもののとりあえず煽ってる人間が、
入り乱れております。
0037デフォルトの名無しさんNGNG
期待age
0038デフォルトの名無しさんNGNG
あげてないずぁん
0039>37NGNG
いい感じ
0040名無しさん＠お腹いっぱい。NGNG
１のソートの対象になるデータ次第だろ？
結局ソートなんてデータ次第なんだよ。
データ（ソートに必要な回数）によって最適なアルゴリズムは変わるだろ？
もう終わりにしようぜ！
お前等全員ミレニアムの年末に彼女がいなくて一人で淋しくインターネットしてる３流私立大学のメガネでぶのコンピュータオタクなんだろ。
こんなお互いを中傷し合う事で淋しさを紛らわすなんて子ども地味たこと辞めようぜ。
さっさと回線切ってＡＶでも借りてきて一発抜いて寝ろよ！
明日はきっと今日よりも最悪な日。
その次の日も、またその次の日も・・・
そうやって１人でどんどん不幸になっていって最後にはバットを振り回して怪我人出して逮捕されてムショでケツ掘られてアンアンの毎日だ。
お前等の人生最高だな。
超かっこいいよ！
0041森総理NGNG
日本のIT産業の未来は明るい。
0042デフォルトの名無しさんNGNG
＞４０
良く言った
あんたはエライ
0043ダブルフォルトの名無しさんNGNG
いくつか用意してランダムで決める（藁
0044デフォルトの名無しさんNGNG
なーんだ。もう終わりか。もっとバカ同士ののしりあえば面白いのに。
ねよねよ。
0045デフォルトの名無しさんNGNG
１のデータが数十件だったらお前ら報われねーな＞ALL
0046デフォルトの名無しさんNGNG
だから冬休みの宿題だってば。
0047?f?t?H???g???????NGNG
と、落ち着いたところで私には
25 のいってることがよくわからないんですけど、
誰か説明してくれません？

0048デフォルトの名無しさんNGNG
あれ、名前に勝手にわけのわからんのがはいっちゃった。
0049???????????????BNGNG
> 2つの値を比較した時に同じだった場合、元の順序を壊さない
そもそも、こういうソートってたとえばどういうときに必要なの?
0050デフォルトの名無しさんNGNG
ソート済みのリスト複数を結合とか？
とりあえず１は頭の良い奴ではないので細かなツッコミはよそう。
いじめ（悪い）
005149NGNG
>>50
>ソート済みのリスト複数を結合とか？
その前提として、要素全体が評価対象じゃなくて、
要素の一部が評価対象である、と言ってる?
たとえば Yamada Taro,Japan,24,Male てな
個人データ群を年齢をキーとしてソートとか?
0052デフォルトの名無しさんNGNG
それにしても
25の言ってる「同じ値」ってどういう意味なのかが
わかりません。
0053デフォルトの名無しさんNGNG
ちょっと話題がずれるが
basicでswap命令が消えたのはいつだったか
あの時、私はその理由がわからずおおいに戸惑ったものだ。
あれはまさしく退化ではないか…<笑>
00542=8NGNG
比較結果が同じ場合に、元の並び順で大小を決めればいいかと思いつきで書きましたが
よくよく考えたら、無理ですね。
鬱だ、２１世紀を目前に回線切って首つります。
板橋あたりで自殺のニュースがあったらそれは私です。

ちなみに２，８以外は自分ではありません。
みなさんよい新世紀を。
0055デフォルトの名無しさんNGNG
つまらんな。
もっとソートについて熱く語ってくれよ。age
0056>55NGNG
じゃあスレ作り直したら？　１の内容じゃネタスレにしかならんsage
0057名無しさん＠お腹いっぱい。NGNG
珠玉のプログラミングにのってたbitsortにはびびった。

http://www.programmingpearls.com/
http://www.programmingpearls.com/code.html

つーか、勉強不足なだけか・・・。
0058名前ついてますか?NGNG
ああ、あの本は買わなきゃ、ってかんじだよねえ。
でもすでにいっぱいキューにたまってるからなあ...
#amazon.co.jpが送料無料のうちに英語版買うかな..
0059名無しさん＠ＬＶ５NGNG
誰かここにくいっくそ−とのそ−す書いて下さい
0060デフォルトの名無しさんNGNG
index付shell sortにしとけ
0061考えました。これはいけるかもしれません。NGNG
そーと(文字列){
　　文字列を並べる
　　天才チンパンジーに見せて並べ替えをさせる
　　値を返す
}
0062考えました。これもいけるかもしれません。 NGNG
そーと(文字列){
　　文字列を水槽に落とす //浮力の小さい順に沈んでいく
　　出来た層を返す
}
0063考えました。これもいけるかもしれません。 NGNG
そーと(文字列){
　　文字列にマラソンをさせる //いつのまにか足の速い順になっている
　　順位順に校舎に戻ってよし
　　}
0064デフォルトの名無しさんNGNG
総統も相当ソートが（以下略）
0065デフォルトの名無しさんNGNG
去年ぐらいに出たアルゴリズムの入門書で、ソートの解説が「シェルソートまで」
つーすごい本なかったっけ？「クイックソート」のクの字もなかったやつ。
0066デフォルトの名無しさんNGNG
2のいうとおりにやればOKだよ
qsort関数使えや

理解できないなら勉強せいや
0067デフォルトの名無しさんNGNG
>>63
途中で近道してた奴が3人もいました。
0068デフォルトの名無しさんNGNG
値が同じ時は元の順番を優先させてのクイックソートを使えや
0069デフォルトの名無しさんNGNG
>>68
クイックソートって「あるデータだと」
かなり遅いアルゴリズムって知ってる？
0070６８NGNG
情報１種の過去問であったよな
当然知ってるよ
0071デフォルトの名無しさんNGNG
クイックソート(文字列 s){
文字　a =　真中頃にある文字を見つける(s);
　do{
　　int n1=先頭からaより大きな文字を探させる
　　int n2=後ろからaより小さなな文字を探させる
　　s->交換(n1,n2);
　}while(先頭からの検索点<=後ろからの検索点)
n=文字aの位置
クイックソート(文字列の先頭からnまで);
クイックソート(文字列のn番目から最後まで);

}

0072デフォルトの名無しさんNGNG
>>68
あ。
安定な整列を行なう関数をわざわざ自作していたよ…。
鬱出汁膿
0073デフォルトの名無しさんNGNG
で、pegionhole sortがquick、mergeより速いってホント？
0074ＳＡＧＥNGNG
>>73

そりゃビンソートとか基数ソートと同じで O( n ) だから、
使える状況なら速いだろうけど。
0075デフォルトの名無しさんNGNG
>>72
だから、>>72にあるようにクイックソートだと前からと後ろから
検索して交換という手順があるから、　元の順番を優先させるには
元の順番のフィールドをデータ構造に含んでいなければいけない。
0076デフォルトの名無しさんNGNG
ニホンゴムツカシイネ
0077デフォルトの名無しさんNGNG
qsort関数の条件判定の関数に値が等しければ
元の順番を使って比較するように
いじれば終わり

それか
ビンソートなりマージソートでもいいよ
0078353NGNG
バカか？
選択した境界値が複数存在した場合どうするんだよ。
0079デフォルトの名無しさんNGNG
>>77
配列の時はいいけどリンクリストのときはどうするよ
データの要素に元の位置の情報がなきゃお手上げでしょ。
配列の場合は「インデックス」っていう暗黙の情報を
比較条件に使うことができるってだけじゃん
0080デフォルトの名無しさんNGNG
同じ値があれば
各々のポインタをつたってって位置情報を割り出し
元の順序を比較条件に追加だよ
0081デフォルトの名無しさんNGNG
＞データの要素に元の位置の情報がなきゃお手上げでしょ。
ソートするってことは並んでる順番をかえることだよ
元の並んでる順番の情報がないわけないじゃん
008279NGNG
>>80各々のポインタをつたってって位置情報を割り出し
　　　　　　　~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>>81
>＞データの要素に元の位置の情報がなきゃお手上げでしょ。
>ソートするってことは並んでる順番をかえることだよ
>元の並んでる順番の情報がないわけないじゃん

ごめん、「お手上げ」っていうのは撤回する。
ただリストの場合その「順番の情報」を取得するのにえらくコストが
かかるって言いたかったのよ。
そんなコストかけるくらいならqsortなんか使わずに他のO(NlogN)の
安定なアルゴリズム使った方がマシって思ったのさ。
確かにやりようによってはリストでも安定なqsortできるかもしれないけど
変な小細工して遅くなるようなら意味ないし
0083デフォルトの名無しさんNGNG
>>27
なぜマージはいけないの？
0084>79NGNG
確かにそうだな
安定で最速なソートとなると
考えてソート法を選ぶしかないな

あんたなかなかやるな
プログラム系のホームページを持ってたら教えて下さいな
0085デフォルトの名無しさんNGNG
qsortも遅くならないように普通は改良されてるから、
何も考えずにqsortでいいんじゃないか？
それはまずいの？
0086>85NGNG
ただのqsortじゃ安定しないの
008785NGNG
>>86
だから、不安定にならないように色々工夫されてるんじゃないの？
組み込みの関数なんかは特に。
0088ＳＡＧＥNGNG
>>87
わざわざ安定なソートになるように変形してあるqsortの実装は
見たことないぞ、俺。組み込みがどうとかは知らんけど。
0089デフォルトの名無しさんNGNG
>>87
stable sortの意味が分かって書いてるのか？
最悪なケースをなるべく生み出さないようなpivotの選出法とか、
数が少ないときはbubble sortに切り替えるだとかいったテクニックは
色々使われていると想定できるが、それはソートが「安定」かどうか
とは全く次元の違う話だぜ。
0090デフォルトの名無しさんNGNG
みんないやらしいね。ところでホントに何でマージソートはいけないの？>>27
009183NGNG
記憶領域を大量に使う（150%）ことを覗けばqsortより優秀だと思ってるんだが。
あと、
pegionhole sortとビンソートってのもわからん。
ダメだな、俺。
[分布数え|radix|マージ|挿入]ソートしか使わないもん。
009227はバカじゃんかNGNG
クイックソートした後にソート前の順番（インデックスを参照して）でバブルソートするのが一番効率的だ。
同じ文字の確立なんて低いだろ？

一番効率的とゆっときながらバブルソートを使うのが理解不能
009379NGNG
>>84
だいぶ前に勢いあまってソース公開スレに自推したことあるけど
恥ずかしいからヒミツ
0094デフォルトの名無しさんNGNG
>>85
Cの標準ライブラリのqsort仕様だと元の順序は保証されてないな
でも扱うのは配列だから比較のときに位置情報は使えるな
0095名無しさん＠お腹いっぱい。NGNG
>>92
ソート前の順番を保持してqsortかけるなら、それもソートキーに
含めてqsortすれば安定するやんけ。
なんでわざわざ最後にバブルソートかけるんだ？
恥ずかしい奴。
0096!92NGNG
>>95
全部読め。
アレは引用だ
009785NGNG
>>89
だから、そういう工夫された方法を使ったqsortを使ってれば、
実用上問題じゃないんじゃないの？
しかも、C言語とかにはじめからついてる関数はそうだから
何も問題ないんじゃないの？ってこと。
自分で変なqsortを書かない限りね。
間違ってる？
0098デフォルトの名無しさんNGNG
>77
>qsort関数の条件判定の関数に値が等しければ
>元の順番を使って比較するように
>いじれば終わり
元の順番を使うって、キーの配列まるまるコピーしておいとくの？？
再帰の底で全部が同じキーの値になった場合に、その部分だけのソート
用のキーとして、元の並びの添え字を保持しておき、それを使うって意味
だよね。キーがほとんど重なってないときはメモリがもったいないよ・・


0099デフォルトの名無しさんNGNG
だれかマージソートがダメな理由を教えてくれ〜
O(nlogn)でデータの選り好みをしないし、qsortなんかより
よっぽどいいと思うんだが？

記憶領域なんて256もつんでおけばたいてい問題ないだろ？
0100デフォルトの名無しさんNGNG
qsortってCの単なるライブラリ関数であってquick sortの事を
一般的にqsortって言ってるわけではないはずなのに、
みんなqsortと省略するのはなんかねぇ・・
0101デフォルトの名無しさんNGNG
>99
>記憶領域なんて256
学生なんですが、定数なんてソースに埋めるもんなんですか？？
0102デフォルトの名無しさんNGNG
>>101
意味不明
>>99
運悪いとページングがおきる可能性がある。そんなに気にすることもないかも知れんが
0103デフォルトの名無しさんNGNG
すまん。256はPCの搭載メモリが256Mってことだ。

>運悪いとページングがおきる可能性がある。
なるほど。そんなコアなところまで気が回らなかった。
0104ＳＡＧＥNGNG
>>97
だから、「Ｃ言語とかにはじめからついてるqsort」は安定じゃねぇってばさ。

>>99
普通のデータだと n log n の係数がでかいせいでクイックソートより遅い。
27みたいな余計なことやってると別のような気もしないでもないが。
0105デフォルトの名無しさんNGNG
＞８５
「遅くなる・ならない」と「安定・不安定」は全く別の話ですよ。

ちなみに関係ないけど VC++ の qsort は
　・最初と真ん中と最後の値の中央値をピボットにする。
　・サイズ８以下なら挿入ソート
でした。
0106６８NGNG
＞再帰の底で全部が同じキーの値になった場合に、その部分だけのソート
＞用のキーとして、元の並びの添え字を保持しておき、それを使うって意味
＞だよね。

qsortの比較関数
で２つの値が等しいときはその時の位置情報を使う
元の並びはいらないよ
0107デフォルトの名無しさんNGNG
工夫されたquick sortでソートした後にバブルソートがベスト。
工夫されたとはpivot選択時にskew checkを行なっていたり、
要素数がある程度以下になった時にはバブルなどに切り替えるソート。

compound keyを用いたquick sortでも良いがkey comparisonの負荷
が増加する点から考えて次点とす。
一つ目の順序が分からない云々言っている奴がいるが、
一つ目のソートができているという事はそのためのkeyは参照という意味である。
0108デフォルトの名無しさんNGNG
>>106
その方法が無効な実装も考えられる。
結局、実装依存になってしまうような気がする。
0109デフォルトの名無しさんNGNG
>>107
>工夫されたquick sortでソートした後にバブルソートがベスト。
アホか？
少なくともバブルソートより基本挿入法のほうが速い
バブルソートがベストである根拠を言ってくれ

> 同じ文字の確立なんて低いだろ？
馬鹿か？
いつ誰が比較する値を「文字」と決めた？
いつ誰が同じデータが出現する確率が低いと言った？

勝手にデータを妄想するな、厨房！
0110デフォルトの名無しさんNGNG
ＧＣＡソート？ってどーよ？
あと、厨房にもわかるように、詳しく解説すれ。
0111デフォルトの名無しさんNGNG
>>77 とかホントにクイックソートのコード書けるのか？
少なくとも単純なクイックソートアルゴリズムからは元の順
番をキーに入れるしかない。

理由は、単純なクイックソートは、[前から検索]と[後ろから検索]
しながら「交換」するからだ。

これを解決するには、一旦マークした後、交換ではなく[挿入]し
なければならない。
それは　速度的には既にクイックとは言えない
0112６８NGNG
>理由は、単純なクイックソートは、[前から検索]と[後ろから検索]
>しながら「交換」するからだ。
値が同じ時に交換するしないを
位置情報で条件分岐させるんだよ
011379NGNG
>>112
交換する２つの値の間にどちらかと同じ値があって
飛び越してしまう可能性もあるよね。
ソレを避けるためにはその間の値をサーチするしかない。
（ソレをやるとすでにクイックソートとは言えないって
111は言いたかったんだよね？）
比較する２つの値が同値かどうかチェックするだけでは
上記の飛び越しの可能性を避けることはできないよ
（つーことで比較関数が「そのときの」位置情報が使えても無駄
っていうことに後から気が付いた自分。初期配置の情報がないと
どうやってもクイックソートは安定になりそうもない）
0114デフォルトの名無しさんNGNG
Microsoft の qsort() の実装には、こういう問題もあったみたいね。
今はどうなんだ？

http://support.microsoft.com/support/kb/articles/Q48/9/65.ASP?LN=EN-US&SD=gn&FR=0&qry=Q48965&rnk=1&src=DHCS_MSPSS_gn_SRCH&SPR=CHS
0115６８NGNG
＞値が同じ時に交換するしないを
＞位置情報で条件分岐させるんだよ
では無理です

最初の順番を記憶させるか

第１比較キーが等しければ
第２比較キーで比較するように
大小比較の部分をいじるか

マージソートやビンソートを使うかだね
0116６８NGNG
＞値が同じ時に交換するしないを
＞位置情報で条件分岐させるんだよ
では無理です

最初の順番を記憶させるか

第１比較キーが等しければ
第２比較キーで比較するように
大小比較の部分をいじるか

マージソートやビンソートを使うかだね
0117じゃNGNG
おまえら全員
バブルソート
選択ソート
挿入ソート
再帰を勉強して・・・＜＜ここが重要だ。厨房
シェルソート
クイックソートを勉強し直せ。
現在もっともソートが最高速なのはイントロソートだ。
0118105NGNG
＞114
VC2以降は無事。
0119デフォルトの名無しさんNGNG
クイックソートの安定がどうたら言ってる奴

今あがってる
http://piza.2ch.net/test/read.cgi?bbs=tech&key=978149371

の、 5,6,9,30 を読め
0120デフォルトの名無しさんNGNG
このスレで議論されてるような、
速くないクイックソートを使うメリットを教えてください。
0121デフォルトの名無しさんNGNG
>>120　イヤミか？
安定なクイックソートはキーに最初の順を入れておくしかない
そうでない改善をしたらそれはクイックソートではないって事だ
0122デフォルトの名無しさんNGNG
で、１の結論はマージソートでいいんだな？
つうかイントロソートの概要でもいから誰か教えてくれよ
intoro sortで検索するとごみが多すぎてワケワカラン
0123デフォルトの名無しさんNGNG
>>122

　Introspective　Sorting なら D. R. Musser に聞け
http://www.cs.rpi.edu/~musser/gp/code/intsort.h.txt


そして
よかったら解説してくれ
0124デフォルトの名無しさんNGNG
>>123のリンク先のついて
ソースは読んでない。説明では基本はクイックソート、ピボットを決める
際に選んだ数によってヒープソートに切り替えるといっている。
メモリ消費：少ない
速度：N2地雷を回避しつつ通常はクイックソート並
安定か：不安定
といった感じか？
0125ソース読み非124NGNG
うんがー
肝心の__unguarded_partition関数の中身はどこだー
<algo.h>ってなんジャー
STL頭いてー

0126デフォルトの名無しさんNGNG
>>109
>少なくともバブルソートより基本挿入法のほうが速い
>バブルソートがベストである根拠を言ってくれ

第一キーでソートしておけば泡の動く範囲が小さく限定されると期待できるから。
0127デフォルトの名無しさんNGNG
おっと、泡は第二キーで動くって事ね。
0128デフォルトの名無しさんNGNG
>>117
>もっともソートが最高速
ナイス日本語。
0129デフォルトの名無しさんNGNG
クイックソートにしとけ。
クイックソートが不安定で困ったなんて話は聞いたことが無い。
0130デフォルトの名無しさんNGNG
不安定よりも、N2地雷コワイよ。
0131デフォルトの名無しさんNGNG
>>124
違う。ピボットとは関係なしに単純に再起の深さで決めている。ソースの感じだと
再起呼び出しの際に深さを表す数をつけて行っている。再起の深さがlog2(size)
になったところでヒープソートに切り替えてるようだ。当然再起にかかわるスタック
消費が増えるのでややメモリ的にはクイックソートより劣るだろう。
0132デフォルトの名無しさんNGNG
通読して地雷を避けるのはダメかな。N+N/2+N/4+...=2N
入れ替え計算量 nlogn 通読 2N 。ま、通読じゃ遅いか。
0133デフォルトの名無しさんNGNG
あ 2N じゃない。N*深さ=nlogn だなぁ。。
0134デフォルトの名無しさんNGNG
N2地雷なんて実際に踏むことあるのかな。
なんか、俺もう既に整列し終わった配列をqsort関数で
ソートしてみたことあるけど、遅くならなかった気がする
のだが。これって、Cのqsort関数は純粋なクイックソート
じゃないってことだろ？
N2地雷の問題なんて多くの実装において解決済み
なんじゃない？
0135デフォルトの名無しさんNGNG
N2地雷ってなに？
0136デフォルトの名無しさんNGNG
>>135
ようわからんが、計算量のオーダーがNになってしまう時の
ことじゃない？
0137134NGNG
俺は130が使ってたから、知ったかかまして、推測で使っただけ
なんだけどね。
検索しても出て来ないから、そんな言葉無いのかも。
O(n)のつもりで書いたんだけど。
0138134NGNG
ていうか、エヴァンゲリオンか？
0139デフォルトの名無しさんNGNG
＞134
O(n^2)じゃないの？
元ネタはエヴァだね、確かもう一方のソートスレで誰かが使い始めてたような・・・
という事で外では使わない方がいいかも
0140デフォルトの名無しさんNGNG
>>134
値を２つに分けるときの参照値の選び方を工夫すればソート済みの
データで遅くなる問題は避けられる。
べつにそうしたからってクイックソートでないって事にはならない。
>>105みたいに最初と最後と真中の位置のキーの中央値をとればだいたいOK
(厳密に言えばこれでも非効率になる初期配列もありえるはずだけど)
0141135NGNG
Webで検索したらエヴァンゲリオンのサイトばかり引っかかって、
どっちが元ネタなのか見分けがつかなかった。
爆発するってことからも、オーダーN^2のことかな。
0142デフォルトの名無しさんNGNG
ソートとは直接関係ないけど、キーが全て異なる配列と自然数nを入力として、
大きいほうからn番目のものをO(n)で探すアルゴリズムがあって、
それを聞いた時すげえ!と感心した記憶がある。
0143デフォルトの名無しさんNGNG
煽りきぼーそ。

話はデータが配列かリストか、ということで全然違う。

リストなら、キーで振り分けてできたリスト2つを下請けに出せば
安定なクイックソート完成。
って、もしかしてこれはクイックソートとは言わないのか？

配列の場合だと、クイックソートのように安定でなくなるか、
(マージ|ヒープ)ソートのようにin-placeでなく（メモリ消費量が
大きく）なるか。

http://ei5nazha.yz.yamagata-u.ac.jp/ADT/sorting.html

てゆーか、配列上でのマージソートって工夫したらin-placeに
なりませんか？

0144デフォルトの名無しさんNGNG
>>99
某STLのstd::list::sortはマージソートだったよ。
リストだと記憶領域は増えないらしい。
マージ中の領域を使いまわせる。
イテレーターの妙技を見たよ。
0145デフォルトの名無しさんNGNG
>>129は安定なソートの意味が分かっていないと思われ
0146デフォルトの名無しさんNGNG
比較数を少なくすることが最優先の場合は、
どんなソートがお勧め？
0147143NGNG
車輪の再発明。つーか先走りすぎだが。

マージを再帰でやればメモリ消費せずにしかも安定なソートにできるぢゃん。
O(n(logn)^2)になってしまうが。

並列計算機のバイトニックソートの情報キボーン。
古いbit誌捨ててしまったのが悔やまれる。
0148部外者ANGNG
再帰でやるってことはメモリ消費してるってことだろがｺﾞﾙｧ?>147
末尾再帰なら話は別だが。
0149部外者ANGNG
それから、bitとかの雑誌のバックナンバーは図書館でいつでも閲覧可能だけど。>147
0150デフォルトの名無しさんNGNG
>>144
stable_sortとstd::sortは？
0151143NGNG
>>148
知っとるわﾎｹﾞｪ! (ｵｲ
クイックソートと同じようにスタックサイズはO(logn)でOK。ってこと。

末尾再帰……わからない宇津死

>>149
すっかり忘れてました。見てきます。

>>146
元データは何？
0152146>151NGNG
>元データは何？
たとえばMP3や獲ろ画像ファイル。
比較を人間がやるとベスト版ができるかなーと思ったので。
で、なるべく比較回数を減らして、なおかつ早い段階で
大雑把な順位付けができるようなアルゴリズムを考えてる。
変形シェルソートが有力か？
0153151=143NGNG
>>152
なるほど。ってそれは個人でやる話？投票のような話？
個人でやる話なら……

ベスト盤作成支援ツール。条件は
１．ユーザーに「むだな比較をやらされている」と感じさせないこと。
２．ユーザーに「信頼性がある」と感じさせること。
うーん、
0154デフォルトの名無しさんNGNG
ユーザーに比較させるとa<b,b<cだけどc<aってなりそう
0155146NGNG
比較・ソートは付加的な機能で、基本はMP3プレイヤーがいいような。
今再生してるのとその前のとでどっちがいいかを
簡単なキー入力で指定する。
だから速度・計算量・使用メモリはぜんぜん問題にならない。

人間の信頼性はあてにならないので、
# >154どころかa>bが時間経ってa<bになることもありうる
なるべく評価値の近いもの同士の比較は避ける。
なるべくランダム再生になるようにする。
評価値の高いものは若干多めに再生する。
ゴミは極力再生しない。アボーンキーでもつけるか？

ってなんかソートとはあんまり関係なくなっちゃな...
■ このスレッドは過去ログ倉庫に格納されています