[挿入ソート]
シェルソートを説明する前に、まず挿入ソートについて少し説明しておく。
挿入ソートとは、配列の先頭から要素を整列した状態にしていき、最後に全ての要素が整列
した状態にするアルゴリズムである。つまり、はじめ先頭の要素のみ整列されている
とすると、二番目の要素を見て今、整列されている部分の適切な場所に挿入されて
次は三番目、四番目と繰り返していって最終的には全ての配列が整列状態になるわけである。
また、挿入ソートは要素がランダムに並んでいるよりも、整列されかかった要素のほうが
計算が少なくて済むという性質を持っている。

// 挿入ソートのサンプルプログラム

class Insert{
	public static void main(String args[]){
		int a[] = {9, 3, 2, 5, 6, 1, 7, 8, 0, 4};
		int t;
		int j;

		for(int i = 1; i < 10; i++)
		{
			j = i;
			while(j >= 1 && a[j - 1] > a[j])
			{
				t = a[j - 1];
				a[j - 1] = a[j];
				a[j] = t;
				j--;
			}

			for(int k = 0; k < 10; k++)
				System.out.print(a[k] + " ");
			System.out.println("");
		}
	}
}

/* 実行結果
3 9 2 5 6 1 7 8 0 4
2 3 9 5 6 1 7 8 0 4
2 3 5 9 6 1 7 8 0 4
2 3 5 6 9 1 7 8 0 4
1 2 3 5 6 9 7 8 0 4
1 2 3 5 6 7 9 8 0 4
1 2 3 5 6 7 8 9 0 4
0 1 2 3 5 6 7 8 9 4
0 1 2 3 4 5 6 7 8 9
*/

[シェルソート]
シェルソートは、挿入ソートを変形したアルゴリズムで、
その名前は発表者であるD.Shellから来ているそうだ。
考え方としては、挿入ソートとほぼ同じだが違うのは挿入ソートでは隣同士の
要素を比較・交換しながら整列させていったのに対し、シェルソートの場合
ある一定の間隔だけ離れた要素を比較・交換し、終わったらその間隔を狭め、
再び狭めた間隔だけ離れた要素を比較・交換し、また間隔を狭め最終的に
挿入ソートと同じように隣同士で比較・交換を行って配列の要素を整列させる。
なぜこのような事をするのかというと、挿入ソートは先に説明したように配列が
整列されかかったていた方が計算量が少ないという性質を持っているからである。
つまり、あらかじめ先頭から遠く離れた要素も比較て・交換しておけば全体的に配列が整列される。
その結果、最後に隣り合う要素を比較・交換する時、その手間が省けるので
全体的に見て、シェルソートの方が挿入ソートよりも計算量を少なくすることができる。

[サンプルプログラム]
class Sample04{
	public static void main(String args[]){
		int a[] = {9, 3, 2, 5, 6, 1, 7, 8, 0, 4};
		int t, j;
		int h = 4; /* 間隔 */

		while(h > 0)
		{
			for(int i = h; i < 10; i++)
			{
				j = i;
				while(j >= h && a[j - h] > a[j])
				{
					t = a[j - h];
					a[j - h] = a[j];
					a[j] = t;
					j = j - h;
				}
				for(int k = 0; k < 10; k++)
					System.out.print(a[k] + " ");
				System.out.println("");	
			}
			h /= 2; /* 1/2ずつ間隔を狭める */
			
			
		}
	}
}


このサンプルプログラムは配列の要素を小さい数字順に並べるものとする。
間隔hを4としているので、4つずつ離れた要素を比較する。
つまり先頭から9と6と0、3と1と4、2と7、5と8、というグループに分けてそれぞれ整列させる。
そうすると{0,6,9},{1,3,4},{2,7},{5,8}となり各グループの先頭要素から
0,1,2,5,6,3...というように順に並べていくと配列は{0,1,2,5,6,3,7,8,9,4}となる。
次に間隔の広さを1/2倍してその間隔を狭める。
2つずつ離れた要素を比較するので、{0,2,6,7,9},{1,5,3,8,4}の2つのグループに
分けて整列させ要素を交互に先頭から並べると、{0,1,2,3,6,4,7,5,9,8}となる。
この状態で配列がほぼ整列しかけていることがわかる。そして
最後に間隔を1/2倍して1になるので隣り合う要素を比較・交換し整列が完了する。
このように3つのループを使い、外側のループでは間隔を狭めてゆき
真ん中のループと内側のループでは配列内でグループを分け要素の比較・交換を行って
シェルソートを実現することができる。

/* 実行結果
6 3 2 5 9 1 7 8 0 4
6 1 2 5 9 3 7 8 0 4
6 1 2 5 9 3 7 8 0 4
6 1 2 5 9 3 7 8 0 4
0 1 2 5 6 3 7 8 9 4
0 1 2 5 6 3 7 8 9 4
0 1 2 5 6 3 7 8 9 4
0 1 2 5 6 3 7 8 9 4
0 1 2 5 6 3 7 8 9 4
0 1 2 3 6 5 7 8 9 4
0 1 2 3 6 5 7 8 9 4
0 1 2 3 6 5 7 8 9 4
0 1 2 3 6 5 7 8 9 4
0 1 2 3 6 4 7 5 9 8
0 1 2 3 6 4 7 5 9 8
0 1 2 3 6 4 7 5 9 8
0 1 2 3 6 4 7 5 9 8
0 1 2 3 6 4 7 5 9 8
0 1 2 3 4 6 7 5 9 8
0 1 2 3 4 6 7 5 9 8
0 1 2 3 4 5 6 7 9 8
0 1 2 3 4 5 6 7 9 8
0 1 2 3 4 5 6 7 8 9
*/

戻る