シェルソートとは
挿入ソートの改良版。挿入ソートを何度か繰り返すことで高速化を実現
手順：
- 適当な間隔$h$を決め、この間隔だけ離れた要素同士だけで挿入ソートを行う。
- 間隔$h$を少し狭めて、同様にその間隔だけ離れた要素同士だけで挿入ソートを行う。
- これを繰り返し、最後に$h=1$で挿入ソートを行う。
なんで速くなるのか：
- $h=1$の時点で、データ全体がかなり整列済み
- 挿入ソートは、整列済みの部分が多いほど高速になる
間隔hについて：
- 一般的には$h_{n+1}=3h_n+1$を使う。
- これがいいっていう証明は困難
- ただし、例えば$h=4,2,1$とすると偶数同士、奇数同士の要素で組を作ってしまうからよくない（ので、$3h+1$を使う）
- 具体的には$h=1,4,13,40,121,\cdots$
- 大体、要素数$/9$を超えないように$h$を選ぶ
- 要素数が$100$の時に$h=40$にすればいいかというと、そうでもない
- あまりにも遠く離れた要素同士のソートは効果が薄い
サンプルコード
ここでは、int型の配列を、シェルソートを用いて整列する。
下の例では要素数が10個しかないのでただの挿入ソートになってる
shell_sort.c
#include<stdio.h>
/* 値を入れ替える関数 */
void swap (int *x, int *y) {
int temp; // 値を一時保存する変数
temp = *x;
*x = *y;
*y = temp;
}
/* シェルソート */
void shell_sort (int array[], int array_size) {
int i, j, h;
for (h = 1; h <= array_size/9; h = 3*h + 1); // 間隔hを決める
for ( ; h > 0; h /= 3) { // hを狭めていく
/* 以下、挿入ソートとほぼ同じ */
for (i = h; i < array_size; i++) {
j = i;
while ((j > h - 1) && (array[j-h] > array[j])) {
swap(&array[j-h], &array[j]);
j -= h;
}
}
}
}
int main (void) {
int array[10] = { 2, 1, 8, 5, 4, 7, 9, 0, 6, 3 };
int i;
printf("Before sort: ");
for (i = 0; i < 10; i++) { printf("%d ", array[i]); }
printf("\n");
shell_sort(array, 10);
printf("After sort: ");
for (i = 0; i < 10; i++) { printf("%d ", array[i]); }
printf("\n");
return 0;
}
実行結果
Before sort: 2 1 8 5 4 7 9 0 6 3
After sort: 0 1 2 3 4 5 6 7 8 9
性能
- 挿入ソートでは、最悪$O(n^2)$
- シェルソートの場合、$h$個ずつ飛ばして探すので、比較回数が少なく、一度の移動量が大きい
- $n^{3/2}$以上に比較されることはない