マージソートってどうよ！？

1 ：１２３人目の素数さん：2001/08/11(土) 21:47

マージソートってどうよ！？

2 ：おっさん：2001/08/11(土) 22:00

知りません。

3 ：１３２人目の素数さん：2001/08/11(土) 22:14

比較回数がどうのこうのってやつ？

4 ：１３２人目の素数さん：2001/08/11(土) 22:14

なかなか良いよ。何回か使ったことがある。

5 ：１３２人目の素数さん：2001/08/11(土) 22:15

ヒープソートとかクイックソートとかあるよね。

6 ：１３２人目の素数さん：2001/08/11(土) 22:16

＞４
何に使ったんだい？

7 ：１３２人目の素数さん：2001/08/11(土) 22:21

俺もしらねぇー。
マージソートってどうやるんだっけ？
２個ずつに分けて…？

8 ：１３２人目の素数さん：2001/08/12(日) 00:27

どうよって、マージソートの何が聞きたいんだ？

性能を知りたいんなら、
オーダーは最悪でもO(nlogn)。
でも、ヒープソートとかクイックソートのほうが早い。
あと、マージするためにバッファを用意してやらナイトいけないから
配列とかをソートする場合にはメモリを無駄に食う。
連結リストをソートするときにはなかなか有効なソートだけど、
連結リストに特化したマージソートの亜種みたいなのがあって、
そっち使ったほうが早い。
クイックソートやヒープソートとは違って安定なソートだから、
同じ大きさの要素の順番が入れ替わって欲しくないときには
マージソートを使う。

ちなみに、C++の標準ライブラリのソート関数は
基本的にはクイックソートで、
枢軸選びは、配列の先頭と末尾と中央の要素のメディアンを使って、
ソートすべき要素数が一定値(大体16～32)より少なくなると
挿入ソートに切り替える。
最近、再起が深くなってきたらマージソートとかに切り替えるって
アルゴリズムを実装したらしいから、オーダーは最悪でもO(n^2)に
なることはない。

あと、同じくC++の標準ライブラリのstable_sortは、
マージソートを使ってる。
こっちは割りとどこででも見かける普通のマージソート。

9 ：１３２人目の素数さん：2001/08/12(日) 08:00

マージソートって数字を順番に並べ替えるプログラムだよね。

10 ：１３２人目の素数さん：2001/08/12(日) 08:08

どうやって並べ替えるんだね。

11 ：１３２人目の素数さん：2001/08/12(日) 09:51

>>10
1. 配列の長さが2ならその2つの要素を単純に比較して整列して終了
2. 配列の長さが2以上なら配列を真っ二つに割る
3. 真っ二つに割った配列を、再起的にマージソートする

12 ：１３２人目の素数さん：2001/08/12(日) 11:11

マージ－ビートって何だっけ?

13 ：１３２人目の素数さん：2001/08/12(日) 15:07

クイックソートは平均O(nlog n)、最悪O(n^2)かかるのでマージソートよりも速いとは言えないのでは。

14 ：１３２人目の素数さん：2001/08/12(日) 18:08

個人的にはヒープソートが好き。
一番エレガントだと思う。

15 ：１３２人目の素数さん：2001/08/12(日) 21:57

>>13
最悪の場合はね。
でも、平均するとクイックソートのほうが速いよ。
マージソートは同じオーダーでも定数部分がでかいから。

まあ、結局のところ、基本はクイックソートで、
再帰が深くなってきたら他のソートに切り替えたり、
要素数が短くなってきたら挿入ソートに切り替えるアルゴリズムが
現時点で一番速いとされてる。

>>14
ヒープソートは確かに最悪の場合のオーダーがO(nlogn)の
ソートの中では高速だけど、クイックソートと一緒で不安定なソートだし。
それにやっぱりクイックソートのほうが速い。
エレガントさでは確かにヒープソートはいい感じだけど。

>>11
これ書いたの漏れだけど、
最後にマージしてくっつけてくの忘れてたな。
急いでたもんで。
スマソ

16 ：１３２人目の素数さん：2001/08/12(日) 22:56

マージソートってヒープソートよりは速いよ。
ヒープソートが優れてるのは最悪の場合でも速いという事。
クイックソートやマージソートは平均すると速いけど、最悪の場合
かなり遅くなる。
あと、マージソートはメモリを余分に必要とするって聞くよね。
マージソートが優れてるのは速さもあるけど、クイックソートや
ヒープソートが不安定なソートに対して、マージソートは安定な
ソートであるということ。安定なソートというのはソートしたとき
の順位が同一な項目の順番が保存されるということ。

17 ：１３２人目の素数さん：2001/08/12(日) 22:57

結局実用的には安定なソートが必要で、マージソートしか選択肢ないって
ことは多い。

18 ：１３２人目の素数さん：2001/08/12(日) 23:04

マージソートは、テープみたいに遅くてシーケンシャルアクセス
しかできないメディア上のデータをソートするための方法じゃ
なかったっけ？
オンメモリにできるデータに対してわざわざ使うものでは
ないのでは？

19 ：１３２人目の素数さん：2001/08/12(日) 23:23

ここおもろいＹＯ！
http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/algorithm/sort-algorithm/

20 ：１３２人目の素数さん：2001/08/13(月) 00:47

>>18
いや、確かにそういう用途ではマージソートが唯一の選択肢だけど、
それ以外のようともあるよ＜マージソート。

>>17が書いてるように、安定なソートの中では一番高速だから、
安定性が必要なときにはマージソートを使うのが普通かと。
C++の標準ライブラリでもそうだし。

あと、連結リストをソートするときには
マージソートの欠点である、メモリを余計に(約1.5倍)食うっていう
問題もなくなるし、マージソート使うことが多い。

>>19
挿入ソートとシェルソートがないが、まあ、見やすくまとまってるな。

21 ：4 ◆BI2EKkq.：2001/08/13(月) 04:28

ヒープソートを中心に、マージソートの出来損ないみたいなのを使っていた＜学生時代自分の作ったプログラムで。

プログラムは結晶の原子を3次元表示するもので、陰面処理のためＺ方向にソートする必要があった。
ヒープソートを使ったのは、単位格子内では既にソートされていて、多くの場合単位格子の1.5倍ぐらいを表示することが多く、その時は既にソートされたものにわずかなデータを加えてソートすることになり、クイックソートの「最悪の場合」に近くなってしまうから。
あと、個人的にヒープソートが好きだったから(エレガントに感じたので)。
マージソートもどきを使ったのは、格子数が多くなるとメモリに乗り切らなくなったため、ディスク上で行なう必要があったため。
単位格子または単位格子の整数倍を１単位としてマージすることで、コーディングが楽だった。

プログラムを、「まずＺ方向から単位格子だけ表示して、その後利用者が格子の大きさや見る方向を決める」という風に作ることで、ソートがかなり楽になっていた。

22 ：１３２人目の素数さん：2001/08/13(月) 12:33

↑なかなかやるじゃなーい

23 ：１３２人目の素数さん：2001/08/13(月) 18:46

おっぱお

24 ：１３２人目の素数さん：2001/08/13(月) 18:47

いいわけねぇだろ　バカやロウ！

25 ：１３２人目の素数さん：2001/08/13(月) 20:23

バカっていうほうがバカ

26 ：１３２人目の素数さん：2001/08/13(月) 23:59

ぷっ…

27 ：１３２人目の素数さん：2001/08/14(火) 00:02

やるわけねぇだろ　バカヤロぅ

28 ：１３２人目の素数さん：2001/08/14(火) 00:04

昔大学のC言語の授業でプログラム作ったなぁ。

29 ：１３２人目の素数さん：2001/08/14(火) 00:25

　　　　　　　　　／■＼　／￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
　　　　　　　　（　´∀｀）＜おにぎりﾜｼｮｰｲ
　　　　　　　＿φ＿__⊂)__ ＼＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
　　　　　　／旦／三／／|
　　　　　　　　|￣￣￣￣￣|　 |
　　　　　　　　|こしひかり|／

30 ：１３２人目の素数さん：2001/08/14(火) 05:59

できるわけねぇだろﾊﾞｶﾔﾛｳ

31 ：◇：2001/08/14(火) 07:00

数学板でやる話題じゃないだろ…

32 ：１３２人目の素数さん：2001/08/14(火) 10:16

>31
理由を言ってみろ！　バカヤロウ

33 ：１３２人目の素数さん：2001/08/14(火) 10:19

おにぎりﾜｼｮｰｲバカヤロウ

34 ：尊師@お盆限定 ◆BI2EKkq.：2001/08/14(火) 10:26

さあー跳ぶぞ跳ぶぞ跳ぶぞ

35 ：１３２人目の素数さん：2001/08/14(火) 11:35

>>32
だって、情報系ほど数学的裏づけが弱いのに成功してる学問ないし。

36 ：あぼーん：あぼーん

あぼーん

37 ：１３２人目の素数さん：2001/08/14(火) 16:19

このスレ立てた人は数学的に
聞いてみたかったんだよ多分

38 ：１３２人目の素数さん：2001/08/14(火) 16:20

>>35
え？どういうこと？

39 ：１３２人目の素数さん：2001/08/14(火) 16:20

＞36
どうやって料理するの？

40 ：１３２人目の素数さん：2001/08/14(火) 16:25

>>35
日本語になってなくない？

41 ：１３２人目の素数さん：2001/08/14(火) 17:31

プログラム組んだことあるけど、どこ行っちゃったかな？

42 ：　：2001/08/14(火) 23:08

>>35
お前の言う数学的裏づけって何だ？
答えるべし。

43 ：１３２人目の素数さん：2001/08/15(水) 00:25

>>35
商売としてはともかく、学問として成功しているのか？

44 ：１３２人目の素数さん：2001/08/15(水) 10:39

>>42
電気系とかだったら電磁気とか微分方程式が必須だけど、
情報系ってそんなのいらないんだよな。
論理回路とか符号理論なんかはいいんだけどな、
ブール代数とか群論とか使わなくもないから。

今、情報系の論文とかって、
「ソートのアルゴリズム作りました」とか、
「データベース作りました」とか、
「ハードウェアで実装しました」で通っちゃうんだよな。
数学的知識がなくても大丈夫だったりする。

>>43
一応してるんだけど、怪しいな。

45 ：１３２人目の素数さん：2001/08/15(水) 13:41

>>44
どこの論文四電の？
あ、学部生の卒論ならそうかもしんないけど

普通の情報系論文に数学的知識は必須だよ

46 ：１３２人目の素数さん：2001/08/15(水) 20:30

>>44
それは君が表面的なところしか知らないだけ。計算機科学の基礎は数学に裏づけされてるよ。

47 ：１３２人目の素数さん：2001/08/16(木) 20:43

そうだそうだ

48 ：>：2001/08/16(木) 21:09

＞電気系とかだったら電磁気とか微分方程式が必須だけど、
＞情報系ってそんなのいらないんだよな。
電磁気学が数学か？という素朴なツッコミはおいといて、

1 .数値積分の実装の際に、用いた公式の公式誤差を評価するのに
微積の知識がなくてどうっやってできると思う？

2 マルコフモデルに従うような情報源について
　考えるときに、ブール代数だけで、どうにかなると思う？

3. 計算可能性やら計算モデルとしてのオートマトンを考えるときに、
　　基礎論や集合論方面の知識なくてどうにかなると思う？

49 ：１３２人目の素数さん：2001/08/16(木) 22:54

今のPCのパワーをもってすれば、数値データを追加していく
だけのなら、なつかしのバブルソートも悪くないか。
割り込みかけながらでも重くならんし、
リソースも食わん。

50 ：１３２人目の素数さん：2001/08/17(金) 12:33

>>追加してゆくのなら
　１、挿入場所の検索
　２、実際の挿入　の操作があって
　挿入場所の検索が早くても、実際の挿入には平均 N/2 の時間がかかるから
　バブルソートの最初の1回を実行させればいいという事だね？

51 ：132：2001/08/17(金) 15:35

ほほう

52 ：１３２人目の素数さん：2001/08/17(金) 19:52

いいねー
マージソート

53 ：竹内まりや：2001/08/17(金) 20:08

http://member.nifty.ne.jp/kkudoh/MerseyBeatDeUtawasete.htm

54 ：１３２人目の素数さん：2001/08/18(土) 15:44

ちょっとスレ違いかもしれんが、理論計算機科学関係のスレを数学板に立てるのはアリだろうか？あまりレスが期待できんかも知れんが。