トップページ⇒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
学生なんですが、定数なんてソースに埋めるもんなんですか？？
■ このスレッドは過去ログ倉庫に格納されています