1 :
123人目の素数さん:
マージソートってどうよ!?
2 :
おっさん:2001/08/11(土) 22:00
知りません。
3 :
132人目の素数さん:2001/08/11(土) 22:14
比較回数がどうのこうのってやつ?
4 :
132人目の素数さん:2001/08/11(土) 22:14
なかなか良いよ。何回か使ったことがある。
5 :
132人目の素数さん:2001/08/11(土) 22:15
ヒープソートとかクイックソートとかあるよね。
6 :
132人目の素数さん:2001/08/11(土) 22:16
>4
何に使ったんだい?
7 :
132人目の素数さん:2001/08/11(土) 22:21
俺もしらねぇー。
マージソートってどうやるんだっけ?
2個ずつに分けて…?
どうよって、マージソートの何が聞きたいんだ?
性能を知りたいんなら、
オーダーは最悪でもO(nlogn)。
でも、ヒープソートとかクイックソートのほうが早い。
あと、マージするためにバッファを用意してやらナイトいけないから
配列とかをソートする場合にはメモリを無駄に食う。
連結リストをソートするときにはなかなか有効なソートだけど、
連結リストに特化したマージソートの亜種みたいなのがあって、
そっち使ったほうが早い。
クイックソートやヒープソートとは違って安定なソートだから、
同じ大きさの要素の順番が入れ替わって欲しくないときには
マージソートを使う。
ちなみに、C++の標準ライブラリのソート関数は
基本的にはクイックソートで、
枢軸選びは、配列の先頭と末尾と中央の要素のメディアンを使って、
ソートすべき要素数が一定値(大体16〜32)より少なくなると
挿入ソートに切り替える。
最近、再起が深くなってきたらマージソートとかに切り替えるって
アルゴリズムを実装したらしいから、オーダーは最悪でもO(n^2)に
なることはない。
あと、同じくC++の標準ライブラリのstable_sortは、
マージソートを使ってる。
こっちは割りとどこででも見かける普通のマージソート。
マージソートって数字を順番に並べ替えるプログラムだよね。
どうやって並べ替えるんだね。
11 :
132人目の素数さん:2001/08/12(日) 09:51
>>10 1. 配列の長さが2ならその2つの要素を単純に比較して整列して終了
2. 配列の長さが2以上なら配列を真っ二つに割る
3. 真っ二つに割った配列を、再起的にマージソートする
12 :
132人目の素数さん:2001/08/12(日) 11:11
マージ−ビートって何だっけ?
13 :
132人目の素数さん:2001/08/12(日) 15:07
クイックソートは平均O(nlog n)、最悪O(n^2)かかるのでマージソートよりも速いとは言えないのでは。
個人的にはヒープソートが好き。
一番エレガントだと思う。
>>13 最悪の場合はね。
でも、平均するとクイックソートのほうが速いよ。
マージソートは同じオーダーでも定数部分がでかいから。
まあ、結局のところ、基本はクイックソートで、
再帰が深くなってきたら他のソートに切り替えたり、
要素数が短くなってきたら挿入ソートに切り替えるアルゴリズムが
現時点で一番速いとされてる。
>>14 ヒープソートは確かに最悪の場合のオーダーがO(nlogn)の
ソートの中では高速だけど、クイックソートと一緒で不安定なソートだし。
それにやっぱりクイックソートのほうが速い。
エレガントさでは確かにヒープソートはいい感じだけど。
>>11 これ書いたの漏れだけど、
最後にマージしてくっつけてくの忘れてたな。
急いでたもんで。
スマソ
16 :
132人目の素数さん:2001/08/12(日) 22:56
マージソートってヒープソートよりは速いよ。
ヒープソートが優れてるのは最悪の場合でも速いという事。
クイックソートやマージソートは平均すると速いけど、最悪の場合
かなり遅くなる。
あと、マージソートはメモリを余分に必要とするって聞くよね。
マージソートが優れてるのは速さもあるけど、クイックソートや
ヒープソートが不安定なソートに対して、マージソートは安定な
ソートであるということ。安定なソートというのはソートしたとき
の順位が同一な項目の順番が保存されるということ。
結局実用的には安定なソートが必要で、マージソートしか選択肢ないって
ことは多い。
18 :
132人目の素数さん:2001/08/12(日) 23:04
マージソートは、テープみたいに遅くてシーケンシャルアクセス
しかできないメディア上のデータをソートするための方法じゃ
なかったっけ?
オンメモリにできるデータに対してわざわざ使うものでは
ないのでは?
19 :
132人目の素数さん:2001/08/12(日) 23:23
20 :
132人目の素数さん:2001/08/13(月) 00:47
>>18 いや、確かにそういう用途ではマージソートが唯一の選択肢だけど、
それ以外のようともあるよ<マージソート。
>>17が書いてるように、安定なソートの中では一番高速だから、
安定性が必要なときにはマージソートを使うのが普通かと。
C++の標準ライブラリでもそうだし。
あと、連結リストをソートするときには
マージソートの欠点である、メモリを余計に(約1.5倍)食うっていう
問題もなくなるし、マージソート使うことが多い。
>>19 挿入ソートとシェルソートがないが、まあ、見やすくまとまってるな。
21 :
4 ◆BI2EKkq.:2001/08/13(月) 04:28
ヒープソートを中心に、マージソートの出来損ないみたいなのを使っていた<学生時代自分の作ったプログラムで。
プログラムは結晶の原子を3次元表示するもので、陰面処理のためZ方向にソートする必要があった。
ヒープソートを使ったのは、単位格子内では既にソートされていて、多くの場合単位格子の1.5倍ぐらいを表示することが多く、その時は既にソートされたものにわずかなデータを加えてソートすることになり、クイックソートの「最悪の場合」に近くなってしまうから。
あと、個人的にヒープソートが好きだったから(エレガントに感じたので)。
マージソートもどきを使ったのは、格子数が多くなるとメモリに乗り切らなくなったため、ディスク上で行なう必要があったため。
単位格子または単位格子の整数倍を1単位としてマージすることで、コーディングが楽だった。
プログラムを、「まずZ方向から単位格子だけ表示して、その後利用者が格子の大きさや見る方向を決める」という風に作ることで、ソートがかなり楽になっていた。
↑なかなかやるじゃなーい
23 :
132人目の素数さん:2001/08/13(月) 18:46
おっぱお
24 :
132人目の素数さん:2001/08/13(月) 18:47
いいわけねぇだろ バカやロウ!
25 :
132人目の素数さん:2001/08/13(月) 20:23
バカっていうほうがバカ
26 :
132人目の素数さん:2001/08/13(月) 23:59
ぷっ…
27 :
132人目の素数さん:2001/08/14(火) 00:02
やるわけねぇだろ バカヤロぅ
28 :
132人目の素数さん:2001/08/14(火) 00:04
昔大学のC言語の授業でプログラム作ったなぁ。
29 :
132人目の素数さん:2001/08/14(火) 00:25
/■\ / ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
( ´∀`)<おにぎりワショーイ
_φ___⊂)__ \_______________
/旦/三/ /|
| ̄ ̄ ̄ ̄ ̄| |
|こしひかり|/
30 :
132人目の素数さん:2001/08/14(火) 05:59
できるわけねぇだろ バカヤロウ
31 :
◇:2001/08/14(火) 07:00
数学板でやる話題じゃないだろ…
32 :
132人目の素数さん:2001/08/14(火) 10:16
>31
理由を言ってみろ! バカヤロウ
33 :
132人目の素数さん:2001/08/14(火) 10:19
おにぎりワショーイ バカヤロウ
34 :
尊師@お盆限定 ◆BI2EKkq.:2001/08/14(火) 10:26
さあー跳ぶぞ跳ぶぞ跳ぶぞ
>>32 だって、情報系ほど数学的裏づけが弱いのに成功してる学問ないし。
あぼーん
37 :
132人目の素数さん:2001/08/14(火) 16:19
このスレ立てた人は数学的に
聞いてみたかったんだよ多分
39 :
132人目の素数さん:2001/08/14(火) 16:20
>36
どうやって料理するの?
40 :
132人目の素数さん:2001/08/14(火) 16:25
41 :
132人目の素数さん:2001/08/14(火) 17:31
プログラム組んだことあるけど、どこ行っちゃったかな?
42 :
:2001/08/14(火) 23:08
>>35 お前の言う数学的裏づけって何だ?
答えるべし。
>>35 商売としてはともかく、学問として成功しているのか?
>>42 電気系とかだったら電磁気とか微分方程式が必須だけど、
情報系ってそんなのいらないんだよな。
論理回路とか符号理論なんかはいいんだけどな、
ブール代数とか群論とか使わなくもないから。
今、情報系の論文とかって、
「ソートのアルゴリズム作りました」とか、
「データベース作りました」とか、
「ハードウェアで実装しました」で通っちゃうんだよな。
数学的知識がなくても大丈夫だったりする。
>>43 一応してるんだけど、怪しいな。
45 :
132人目の素数さん:2001/08/15(水) 13:41
>>44 どこの論文四電の?
あ、学部生の卒論ならそうかもしんないけど
普通の情報系論文に数学的知識は必須だよ
46 :
132人目の素数さん:2001/08/15(水) 20:30
>>44 それは君が表面的なところしか知らないだけ。計算機科学の基礎は数学に裏づけされてるよ。
47 :
132人目の素数さん:2001/08/16(木) 20:43
そうだそうだ
48 :
>:2001/08/16(木) 21:09
>電気系とかだったら電磁気とか微分方程式が必須だけど、
>情報系ってそんなのいらないんだよな。
電磁気学が数学か?という素朴なツッコミはおいといて、
1 .数値積分の実装の際に、用いた公式の公式誤差を評価するのに
微積の知識がなくてどうっやってできると思う?
2 マルコフモデルに従うような情報源について
考えるときに、ブール代数だけで、どうにかなると思う?
3. 計算可能性やら計算モデルとしてのオートマトンを考えるときに、
基礎論や集合論方面の知識なくてどうにかなると思う?
49 :
132人目の素数さん :2001/08/16(木) 22:54
今のPCのパワーをもってすれば、数値データを追加していく
だけのなら、なつかしのバブルソートも悪くないか。
割り込みかけながらでも重くならんし、
リソースも食わん。
>>追加してゆくのなら
1、挿入場所の検索
2、実際の挿入 の操作があって
挿入場所の検索が早くても、実際の挿入には平均 N/2 の時間がかかるから
バブルソートの最初の1回を実行させればいいという事だね?
51 :
132:2001/08/17(金) 15:35
ほほう
52 :
132人目の素数さん:2001/08/17(金) 19:52
いいねー
マージソート
53 :
竹内まりや:2001/08/17(金) 20:08
ちょっとスレ違いかもしれんが、理論計算機科学関係のスレを数学板に立てるのはアリだろうか?あまりレスが期待できんかも知れんが。
55 :
132人目の素数さん:2001/08/18(土) 21:24
理論計算機科学関係ってどういうこと?
56 :
132人目の素数さん:2001/08/18(土) 21:37
アルゴリズムの話などと思われ。
57 :
>:2001/08/19(日) 01:30
P=NPを解決すべしとか
チューリングマシーンとか?
59 :
:2001/08/19(日) 13:15
数学と計算機科学の関係とか?
60 :
132人目の素数さん:2001/08/19(日) 15:59
立派な数学じゃねェか
どこがアリじゃねぇんだ バカヤロウ
61 :
132人目の素数さん:2001/08/20(月) 01:41
ふぉーーーーっ!!!
62 :
132:2001/08/20(月) 20:50
頑張れマージソート
とりあえず、マージソートにしとけば間違いないだろ。
64 :
132:2001/08/23(木) 01:00
そうだね
65 :
132人目の素数さん:2001/08/23(木) 10:48
ねばるな、マージソート。
レッツマージソート
68 :
132人目の素数さん:2001/08/24(金) 21:37
最大n
69 :
132人目の素数さん:2001/08/25(土) 02:50
>>54 情報システム板がアレだしな。
立ててくれ。
70 :
132人目の素数さん:01/08/26 14:02
どういうこと?
71 :
132人目の素数さん:01/09/01 16:22 ID:8behHHuE
がるるるるっ!
なんで出ねーんだよ、バカやロウ