fortran66 https://blog.hatena.ne.jp/fortran66/ fortran66のブログ https://fortran66.hatenablog.com/ Fortran2003 動的に記憶領域を確保できなかったFORTRAN77時代に重宝していたShell Sortのプログラムを書いてみました。ギャップのとり方として、Knuthの数列[tex:\{g_{n+1}=3*g_n+1|2*g_ha102549）。しかし、実行時間をデータ数の関数としてみると大体Ｏ(N^2)に比例していて、Shell sortの計算量の理論値Ｏ(N^1.2〜1.5)と食い違っています。 少し調べたところ、Bubble sortやKnuth数列以外のギャップでの場合と比較すると、データスワップ回数はBubble sortではＯ(N^2)、Shell sortはＯ(N^1.3)前後で理論値通りにな… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Ffortran66.hatenablog.com%2Fentry%2F20100224%2F1266943692" title="&lt;del datetime=&quot;2010-02-24T23:43:13+09:00&quot;&gt;Shell sort実行時間がO(N^2)で謎だった件&lt;/del&gt;Shell sort かわいいよ Shell sort！の巻 - fortran66のブログ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> http://cdn-ak.f.st-hatena.com/images/fotolife/f/fortran66/20100225/20100225035509.png Hatena Blog https://hatena.blog 2010-02-24 01:48:12 rich https://fortran66.hatenablog.com/entry/20100224/1266943692 1.0 100%