シェルソート

今までのようにループ回数から計算量を直感的に求められないアルゴリズム。
挿入ソートは、整列されていれば高速に動作し、そうでない場合にはN(N-1)/2よりO(N^2)のアルゴリズムに
なるのだった。

この特徴を生かし、あらかじめざくっと(３個ずつとか４個ずつとか)挿入ソートをしたあとで
１つずつの通常の挿入ソートを行えば、計算量はN回に近づくのではないかという方法。
詳しい方法は参考リンクの動画を参照。(すばらしい!)

コツは、間隔をGとして、G={1,4,13,40,121,...}とするh = 3*h + 1で指定しているところ。
こんなの思いつかない・・・。
一方、間隔Gを２のべき乗など、最終的にソート対象にならない要素がたくさんでるような
規則的なものにすると、効率は良くならないらしい。

ちなみに、挿入ソートは安定的だが、シェルソートは安定的でない。
(まあ、指定間隔で初期順序をシャッフルしてしまうので・・・。)

計算量はO(N^1.25)程度なようだ。求め方はわからないですが・・・。
論文等があれば更新したい。

■ソースgithub.com

■参考URL(処理方法のイメージ動画)www.codereading.com
■参考URL(間隔に関する考察)
シェルソートと間隔hの決め方【C++】 - Programming Magic

■参考資料

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造