アルゴリズムとデータ構造

アルゴリズムと
データ構造
第8回
ソート・その2
単純挿入ソート

単純挿入ソートとは
 順に要素に着目し、それを適当な位置に挿入
 別名：シャトルソート
6
1
4
3
4
1
7
3
9
8
8
単純挿入ソート

目的列と原列
 目的列：ソート済みの部分
 原列：これからソートする部分

単純挿入ソートのアルゴリズム
 原列の先頭要素を目的列の適当な位置に挿入
1
4
6
目的列
7
3
9
原列
8
単純挿入ソート

「適当な位置に挿入」の実現
 左隣の要素と比較し、挿入すべき値より大きけれ
ば左隣の値を代入
 挿入する値以下の要素に出会ったところに挿入
1
4
6
4
7
6
3
7
9
8
単純挿入ソート

「適当な位置に挿入」のアルゴリズム
 原列左端の値を保存
 目的列の右端から、保存した値と比較
 目的列左端に達するか、保存した値と等しいか
小さいキーを持った値を持つ項目が見つかったら
その位置に保存していた値を挿入

安定性
 飛び越えた要素の交換が行われないので安定
単純挿入ソート

単純挿入ソートのプログラム
for (i = 1; i < n; i++) {
int tmp = a[i];
for (j = i; j > 0 && a[j - 1] > tmp; j--)
a[j] = a[j - 1];
a[j] = tmp;
}
シェルソート

単純挿入ソートの特徴
 ソート済みに近い場合は高速
 挿入先が遠く離れていると移動回数が増大
1
0
2
1
3
2
4
3
5
4
0
5
6
シェルソート

シェルソートの考え方
 単純挿入ソートの長所を生かしつつ、回数の多
い移動を避ける
 最初にまずグループ化を行い、グループ内で大
まかにソート（地ならし）
 グループを次第に小さくしていき、最終的に単純
挿入ソートを行ってソート完了
 前処理を含めても、移動回数が少なくてすみ、全
体として高速化
シェルソート

シェルソートの実例
 4-ソート
8
7
1
4
3
2
7
8
6
3
4
5
シェルソート

シェルソートの実例
 2-ソート
3
7
1
4
3
2
7
8
6
5
8
4
5
6
シェルソート

シェルソートの実例
 1-ソート
1
3
1
3
2
3
4
2
4
5
7
7
6
5
7
8
8
6
シェルソート

シェルソートのプログラム
for (h = n / 2; h > 0; h / 2)
for (i = h; i < n; i++) {
int tmp = a[i];
for (j = i - h; j >= 0 && a[j] > tmp; j -= h)
a[j + h] = a[j];
a[j + h] = tmp;
}
シェルソート

増分の選択
 ある値から減少して1になればよい
 増分のとり方によっては、同じグループ内でのみ
ソートして、グループ分けが十分に機能しなくなる
 増分が互いに倍数にならないようにする
 h = ・・・、121、40、13、4、1

1から始め、3倍して1を足していく
 最初が大きすぎても効果なし：n
/ 9を超えない値
シェルソート

適切増分シェルソートのプログラム
for (h = 1; h < n / 9; h = h * 3 + 1) ;
for ( ; h > 0; h /= 3)
for (i = h; i < n; i++) {
int tmp = a[i];
for (j = i - h; j >= 0 && a[j] > tmp; j -= h)
a[j + h] = a[j];
a[j + h] = tmp;
}

Download Report