【アルゴリズム】シェルソートの速度を考察した

はじめに

• 「シェルソート」とは、改良された「挿入ソート」のアルゴリズムである。
• シェルソートは、簡単に記述できるアルゴリズムの中では、かなり高速だ。
• この記事では、シェルソートで並べ替える配列の長さと、ソートの速度を考察する。

前提：挿入ソートとは何か

• 「挿入ソート」とは、以下のようなソートアルゴリズムである。
  • 配列Ｎ番目（Ｎ≧２）の数字に注目する。
  • その数字が左隣の数字より小さい間は、左隣の数字と交換し続ける。
  • 配列Ｎ＋１番目の数字に注目する。
  • その数字が左隣の数字より小さい間は、左隣の数字と交換し続ける。
• 図を見た方が分かりやすい。赤字のところが交換した箇所である。

6	3	0	4	5	8	1	2	7	11	10	9
3	6	0	4	5	8	1	2	7	11	10	9
3	0	6	4	5	8	1	2	7	11	10	9
0	3	6	4	5	8	1	2	7	11	10	9
0	3	4	6	5	8	1	2	7	11	10	9
0	3	4	5	6	8	1	2	7	11	10	9
0	3	4	5	6	1	8	2	7	11	10	9
0	3	4	5	1	6	8	2	7	11	10	9
0	3	4	1	5	6	8	2	7	11	10	9
0	3	1	4	5	6	8	2	7	11	10	9
0	1	3	4	5	6	8	2	7	11	10	9
0	1	3	4	5	6	2	8	7	11	10	9
0	1	3	4	5	2	6	8	7	11	10	9
0	1	3	4	2	5	6	8	7	11	10	9
0	1	3	2	4	5	6	8	7	11	10	9
0	1	2	3	4	5	6	8	7	11	10	9
0	1	2	3	4	5	6	7	8	11	10	9
0	1	2	3	4	5	6	7	8	10	11	9
0	1	2	3	4	5	6	7	8	10	9	11
0	1	2	3	4	5	6	7	8	9	10	11

挿入ソートの特徴

• 交換回数が少ない。
• 1000くらいの要素なら、実用的な速さで動く。
• (要素数)² に比例した回数の比較処理を行うため、100万要素の並べ替えは現実的な時間ではできない。（2022年の時点）

挿入ソートの比較回数（ランダム配列の場合）

• 要素数をNとして、比較回数は 0.24 N² に近似できる。

要素	比較回数	交換回数
10	32	26
31	245	215
100	2964	2870
316	24285	23981
1000	234963	233974
3162	2445624	2442476
10000	23886833	23876841

• もし、100万要素の並べ替えを行うなら、じつに 2400億回 もの比較が必要になる。
• これを執筆しているPCでは、約7200秒(＝120分)かかる見積もりだ。

改良版挿入ソート「シェルソート」

• ドナルド・シェルが、1959年に発表したソートアルゴリズム。
• 「挿入ソートは隣同士しか交換しないから遅い」という欠点を克服すべく、離れた位置の要素を交換するように改善した。
• まずは、4n番目(0, 4, 8, 12, …)の要素を挿入ソートする。つまり4つ離れた位置の挿入ソート。
• つぎに、4n+1番目(1, 5, 9, 13, …)の要素を挿入ソートする。
• つぎに、4n+2番目(2, 6, 10, 14, …)の要素を挿入ソートする。
• つぎに、4n+3番目(3, 7, 11, 15, …)の要素を挿入ソートする。
• 最後に、n番目(0, 1, 2, 3, …)の要素について普通の挿入ソートをする。
• 4n番目などの挿入ソートを最初に実行している分、遅くなりそうな雰囲気があるが、実際にはそうではない。
• 図を見た方が分かりやすい。赤字のところが交換した箇所である。

11	10	9	8	7	6	5	4	3	2	1	0
7	10	9	8	11	6	5	4	3	2	1	0
7	10	9	8	3	6	5	4	11	2	1	0
3	10	9	8	7	6	5	4	11	2	1	0
3	6	9	8	7	10	5	4	11	2	1	0
3	6	9	8	7	2	5	4	11	10	1	0
3	2	9	8	7	6	5	4	11	10	1	0
3	2	5	8	7	6	9	4	11	10	1	0
3	2	5	8	7	6	1	4	11	10	9	0
3	2	1	8	7	6	5	4	11	10	9	0
3	2	1	4	7	6	5	8	11	10	9	0
3	2	1	4	7	6	5	0	11	10	9	8
3	2	1	0	7	6	5	4	11	10	9	8
2	3	1	0	7	6	5	4	11	10	9	8
2	1	3	0	7	6	5	4	11	10	9	8
1	2	3	0	7	6	5	4	11	10	9	8
1	2	0	3	7	6	5	4	11	10	9	8
1	0	2	3	7	6	5	4	11	10	9	8
0	1	2	3	7	6	5	4	11	10	9	8
0	1	2	3	6	7	5	4	11	10	9	8
0	1	2	3	6	5	7	4	11	10	9	8
0	1	2	3	5	6	7	4	11	10	9	8
0	1	2	3	5	6	4	7	11	10	9	8
0	1	2	3	5	4	6	7	11	10	9	8
0	1	2	3	4	5	6	7	11	10	9	8
0	1	2	3	4	5	6	7	10	11	9	8
0	1	2	3	4	5	6	7	10	9	11	8
0	1	2	3	4	5	6	7	9	10	11	8
0	1	2	3	4	5	6	7	9	10	8	11
0	1	2	3	4	5	6	7	9	8	10	11
0	1	2	3	4	5	6	7	8	9	10	11

• 交換する距離は、配列の大きさによって変更する。

なぜ速いのか

• 4つ離れた位置ごとのソートが済んでいる場合、普通のソートの実行時間は大幅に短縮されるから。（上の表を参照)
• 要素数がさらに大きいときは、挿入ソートをする間隔を以下のように広げていく。
  • 1 → 4 → 13 → 40 → 121 → (3倍+1)

シェルソートの比較回数（ランダム配列の場合）

• 要素数をNとして、比較回数は 3.5 N^1.2・(log_eN)^0.1 に近似できる。
• Wikipedia には、N^1.25 のオーダーと書いてあるが、こちらの方が実測値に近い。

要素数	比較回数	交換回数
10	19	10
31	135	83
100	1062	881
316	4333	3437
1000	17436	13634
3162	70966	55731
10000	274549	216244
31622	1123988	907860
100000	3963773	3101598
316227	16191587	13143666
1000000	64086120	53433454

挿入ソート VS シェルソート

• 挿入ソートとシェルソートの比較回数（近似式）を比べてみる。

要素数 N	挿入ソート 0.24 N2	シェルソート 3.5 N1.2・(logeN)0.1	速度比
1000	240000	15552	15倍
10000	24000000	253673	95倍
100000	2400000000	4111166	584倍
1000000	240000000000	66356454	3617倍

• シェルソートは圧倒的に速い。

JavaScript での実装

function shellSort(ary){
	// 最初の交換間隔を決める(1→4→13→40→121→...)
	let d = 1;             // d : 交換間隔
	let z = ary.length;    // z : 配列長
	let dmax = z / 30 | 0; // 最初のdは配列長の1/9程度が良い
	while(d <= dmax){
		d = d + d + d + 1;
	}
	// 交換間隔が0になったら終了
	while(d > 0){
		// i : 交換間隔の分だけ繰り返す(間隔が40なら40回)
		for(let i = 0; i < d; i++){
			// j : i～末尾まで繰り返す
			for(let j = i; j + d < z; j += d){
				// k : j～先頭まで繰り返す
				for(let k = j; k >= 0; k -= d){
					// 左が大きい場合は交換する
					// 右が大きい場合はjを進める
					if(ary[k] > ary[k + d]){
						[ary[k], ary[k + d]] =
							[ary[k + d], ary[k]];
					}else{
						break;
					}
				}
			}
		}
//		交換間隔を小さくする(121→40→13→4→1→0)
		d = d / 3 | 0;
	}
}

その他、シェルソートの特性

• ソート済配列の先頭や末尾に追加した場合、比較回数は O(N log^1.2N) のオーダー。
  • 先頭や末尾に k個 追加した場合の比較回数（実測値）の近似値は、
    1.2 N・log_e(k・N)^1.2
  • 挿入ソートの末尾追加のオーダーは O(N) であるから、その場合では挿入ソートの方が有利になる。

まとめ

• N個のランダム配列では、シェルソートの比較回数は 3.5 N^1.2・(log_eN)^0.1 だと判明した。
  参考までに、JavaScriptで整数の配列をソートする場合、1億回の比較に3秒かかる。
• シェルソートは22行で実装できるので、挿入ソートをシェルソートに置き換えるのはいいぞ。