tag:blogger.com,1999:blog-3636872937372639901.post4987413787285966342..comments2024-03-27T21:24:43.584+09:00Comments on 本の虫: insertion sortをジェネリックに実装してみた江添亮http://www.blogger.com/profile/13387122818743087721noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-3636872937372639901.post-22294367558282806252009-12-01T19:27:45.684+09:002009-12-01T19:27:45.684+09:00ですよね。勘違いしてました。ですよね。勘違いしてました。江添亮https://www.blogger.com/profile/13387122818743087721noreply@blogger.comtag:blogger.com,1999:blog-3636872937372639901.post-35983376650811769702009-11-26T19:07:43.541+09:002009-11-26T19:07:43.541+09:00> insertion sortは、ほとんどソートされた配列に提供するのが筋である。
>...> insertion sortは、ほとんどソートされた配列に提供するのが筋である。<br />> だから、逆から追っていくのが普通の実装だ。<br /><br />この部分、意味がよくわかりません。<br /><br />例えば、完全にソートされた配列 a[] = {3,4,5} に、完全にソートされた配列かb = {1,2}をappendした配列 c[] = {3,4,5,1,2} やソートされていない配列 b'={2,1}をappendした配列 a'= {3,4,5,2,1}に対して、逆が追っていくと、前から辿るよりメモリコピーの回数が増えます。<br /><br />こういう意味ではないのでしょうか・・。<br /><br />「ほとんどソートされた配列」、たとえば a'' = { 1,2,3,0,4 }に対しても前から追ったほうが速いです。もちろん逆から追ったほうが速い、「ほとんどソートされた配列」も作ることは出来ますが、要するに「ほとんどソートされて」いることと前から辿るか後ろから追うかは何の関係もないように思えます。<br /><br />結局、前から辿っても逆から追っても平均すれば同じ処理量であるなら、後ろから追うとメモリハザードが生じる可能性が高いぶんだけ損ではないかと思うのですが。やねうらおhttp://d.hatena.ne.jp/yaneurao/noreply@blogger.com