シェルソートをわかりやすくまとめる

シェルソートについて、わかりやすくまとめたいと思います。

シェルソートとは

一定間隔(g)ごとに挿入ソートを行うことをシェルソートといいます。 最後に必ず、通常の挿入ソートを行いますが、
この時に、あらかた整列されていることが期待されます。

この一定間隔gの決め方ですが

g = 1,4,13,40,121・・・

つまりは、
$g_{n+1} = 3g_{n} + 1$の数列を用いると、
計算量が$O(N^{1.25})$になるようです。

また、上記のgを適応すると、2のべき乗の値($2^p = 1,2,4,...$)の場合は、ソート対象となる要素が少なくなるため、
効率化は見込めないようです。

シェルソートの工程を図解する

実際にシェルソートが行われる工程を図解してみます。

数列{4,8,9,1,10,6,2,5,3,7}に対して、 g{4,3,1}として、シェルソートをかけてみます。

ここで、選択対象数字を赤で、整列済みの数字を緑で表現したいと思います。

1.間隔を4に空けて挿入ソートをかけます。

4,8,9,1,10,6,2,5,3,7
3,8,9,1,4,6,2,5,10,7

3,8,9,1,4,6,2,5,10,7
3,6,9,1,4,7,2,5,10,8

3,6,9,1,4,7,2,5,10,8
3,6,2,1,4,7,9,5,10,8

3,6,2,1,4,7,9,5,10,8
3,6,2,1,4,7,9,5,10,8

2.間隔を3に空けて挿入ソートをかけます。

3,6,2,1,4,7,9,5,10,8
1,6,2,3,4,7,8,5,10,9

1,6,2,3,4,7,8,5,10,9
1,4,2,3,5,7,8,6,10,9

1,4,2,3,5,7,8,6,10,9
1,4,2,3,5,7,8,6,10,9

3.最後に間隔1(通常)に空けて挿入ソートをかけます。

1,4,2,3,5,7,8,6,10,9
1,2,3,4,5,6,7,8,9,10