ノート:コムソート

間隔を割る係数について

Byte Magazineに載った論文では実験的に求めた値として 1.3 が示されているとのことです(原論文未確認)。

一方、Combsort: shrink factor for guaranteed O(n log n) worst case time?において、「9/7 以上の数ではうまく turtle を除去できない」との主張がされています。しかし具体的な証明が示されていないようです。

英語版の記事では、1.247330950103979 という係数も出ていますが、これも出典が示されていません。

11以下の間隔について、11,8,6,4,3,2,1しか用いないようにすると、turtle がうまく除去されるとなっていますが、とくに証明についての情報は無いようです。

12以上の間隔で忌避すべき物は不明です。(9 11 5 13 8 14 3 6 7 4 2 15 16 18 10 1 17 12)という数列は間隔14,11,8,6,4,3,2,1という系列ではソートしきれず、もう一度間隔1で櫛をかける操作が要ります。14は避けるべき間隔の候補ですが、その他の値、系列についての情報が不足しています。

実装の際は、最後の間隔1の処理を、挿入ソートで行うのが安全かつ効率的と見られます。

--Shigenori TSUNEZAWA 2008年4月24日 (木) 14:16 (UTC)

平均計算時間、最悪計算時間ついて

係数1.3の場合、最初の4～5回で小さい数字が配列の後半に留まった場合の計算時間はO(n^2)になります。 ワーストケースは当然O(n^2)ですが、 これが起きる確率は単純計算だとn/10^17程度で、nが十分に大きい場合この確率は100％に近付くので、平均計算時間もO(n^2)になります。 実際に1億件程度のランダムなデータでワーストケースに遭遇したので、この問題は無視できるほど小さい確率ではないようです。--TokusiN（会話） 2013年4月2日 (火) 10:38 (UTC)