アルゴリズムと
データ構造
第12回
ソート（3）:
シェルソート、クイックソート
先々週の復習 O(n2)のソート
配列の後ろから先頭に向かってスキャ
ンし，隣り合う２つの要素の大小関係
が逆であったら入れかえる
1
3
挿入ソート
未ソート
バブルソート
現在処理対象となっているデータを，
整列済みのデータ列内の適切な位置
に挿入する
5
9
10
7
10 11
7
20 17
6
ソート済
3
5
8
選択ソート
整列されていない部分から最小要素
を選び，先頭と入れかえる処理を繰り
返す
未ソート
1
3
5
入れかえ
9
10
7
20 17 18
最小値
先週の復習
配列 A
バケットソート O(n)
値kの要素を入れる箱(バケット
B[k]、ただし、kは０≦k≦m-1)を準
備し、各要素A[i]をB[A[i]]に入れ
たあと、バケットの中身を連結する
基数ソート
O(n)
整列対象となるキーを，いくつか
のサブキーに分割し，下位から上
位の順に，サブキーをもとに安定
な整列を行う
[0]
[1]
[2]
[3]
[4]
1
4
0
6
2
バケットB
[0]
[1]
[2]
[3]
[4]
[5]
[6]
A[2]
A[0]
A[4]
A[1]
A[3]
B U T
K I D
F A N
F A N
A N Y
B U T
K I D
A N Y
先週の演習問題
(問1)次の5個の整数 {4, 7, 5, 6, 7}をバケットソートでバ
ケットB[i]( 0 ≦ i < 10) を用いて整列する手順を図を
用いて説明せよ。
問1 解答例1 (抽象的な説明例)
A [0] [1] [2] [3] [4]
5個の整数が配列Aに格納
されているものとする
4
7
5
6
7
バケットBにデータを格納する
B [0] [1] [2] [3] [4] [5] [6] [7] [8] [9]
A[1]
A[0] A[2] A[3]
A[4]
バケットの先頭から順に
取り出し、配列Aに戻す
A’ [0] [1] [2] [3] [4]
4
5
6
7
7
問1 解答例2
(ポインタを用いた実装を想定した例)
バケットBにデータを格納する
A [0] [1] [2] [3] [4]
B [0]
4 7 5 6 7
[1]
[2]
[3]
[4]
[5]
[6]
バケットの先頭から順に取り出し、配列Aに戻す [7]
A’ [0] [1] [2] [3] [4]
[8]
4 5 6 7 7
[9]
A[0]
A[2]
A[3]
A[4]
A[1]
(問2)次の３文字の系列を基数ソートで辞書式順序に並べて
いく過程を示せ。
(B U T ),
１回目
( F A N ),
２回目
( A N Y ),
３回目
( K I D )
問2 解答
１回目
２回目
３回目
KID
FAN
BUT
ANY
FAN
KID
ANY
BUT
ANY
BUT
FAN
KID
本日の内容
シェルソート
クイックソート
シェルソート（Shell sort）
1959年に D. L. Shellが発
表したアルゴリズム
挿入ソートを変形
計算量O（n1.25）～O（n1.5）
安定ではない
シェルソート
単純挿入ソートの特徴
ソート済みに近い場合は高速
挿入先が遠く離れていると移動回数が増大
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
3
7
1
4
3
2
7
8
6
5
8
4
5
6
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;
}
練習問題
以下のデータをシェルソートで昇順に整列しなさい
整列の間隔は4、2、1の順で減らすこと。
10, 5 , 4, 27, 2, 6, 3, 20, 1, 0, 8, 9, 7, 23, 13, 42
解答
10 5 4 27 2 6 3 20 1 0 8 9 7 23 13 42
4ずつ離れたものをソートした結果
1 0 3 9 2 5 4 20 7 6 8 27 10 23 13 42
1 0 3 9 2 5 4 20 7 6 8 27 10 23 13 42
2ずつ離れたものをソートした結果
1 0 2 5 3 6 4 9 7 20 8 23 10 27 13 42
1ずつ離れたものをソートした結果
0 1 2 3 4 5 6 7 8 9 10 13 20 23 27 42
シェルソート（Shell sort）のまとめ
挿入ソートを変形
計算量O（n1.25）～O（n1.5）
安定ではない
クイックソート
クイックソートとは
1962年に
C. A. R. Hoareが発表したアルゴリズム
内部整列アルゴリズムの中で最速
不安定な整列アルゴリズム
ある要素を決め、その要素より大きいグループと
小さいグループに分類
ある要素：枢軸
各グループで枢軸を決め直して同じように分割
計算量O（n
log n）
ただし，最悪の場合O (n2)
1.
2.
3.
4.
クイックソートの原理
ソートする範囲のデータから適当な軸要素(枢軸、pivot) Xを選ぶ。
要素をひとつずつ調べて、X より小さいグループと大きいグループに分割す
る。
小グループと大グループ各々に上記１．と２．を適用する。
各々のグループが分割できなくなるまで分割を繰り返す。
実行例１
8
4
1
1
3
2
2
6
3
4
7
1
4
2
5
3
2
5
5
3
4
5
6
1
8
8
6
6
7
7
7
8
分割の手順
枢軸をx、配列左端をpl、配列右端をprとし
pl位置の要素がxより大きくなるまでplを右に移動
pr位置の要素がxより小さくなるまでprを左に移動
pl、pr両位置の要素を交換
操作を続け、plとprの位置が交差した時点で終了
配列左端からpl位置の1つ前まで：枢軸より小さい集合
pr位置の1つ後から配列右端まで：枢軸より大きい集合
実行例２
5
pl
7
3
1
枢軸以下
4
6
2
2
6
3
7
9
8
枢軸以上
pr
クイックソート
ソートの手順
分割されたグループそれぞれに、同じ処理を再
度適用して再分割
分割されたグループの要素数が1になった時点で
分割終了
一種の分割統治法：再帰で簡単に実現
クイックソートのコード
void quicksort(int l, int r, int A[])
{
int k; /* 枢軸より大きい部分の開始位置 */
軸要素を決める;
if (キーがすべて同じ) 終了;
xより小さい部分と大きい部分に分割し，
大きい部分の先頭の位置kを返す;
quicksort(l, k – 1,A);
quicksort(k, r, A);
}
/* 小さい部分を整列 */
/* 大きい部分を整列 */
枢軸の選択
枢軸の選び方がクイックソートの効率に影響
配列の値の最小値または最大値を選ぶと最悪
できるだけ配列の値の中央値が望ましい
ただし厳密に求める処理に時間がかかると本末転倒
方針1：先頭要素、中央要素、最後尾要素の3値
の中間値を使う
方針2：方針1に加え、3値をソートして、中央要素
と最後尾1つ前の値を入れ替え、ソート範囲を3要
素分絞る
先頭は必ず枢軸以下、最後尾とその手前は必ず枢軸
以上の値になっているので、それぞれの内側をソート
範囲とすればよくなる
実行例３
Ｘ= 3の場合
pl→
←pr
A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9]
Start
3
1
4
1
5
9
2
6
5
3
(1)
2
1
4
1
5
9
3
6
5
3
(2)
2
1
1
4
5
9
3
6
5
3
分割終了
pr = 2
pl = 3
pl, pr : カーソル
v : 枢軸
実行例３：各々のグループをさらに分割
a[0] a[1]
レベル2
レベル5
ソート終了
a[4] a[5] a[6] a[7] a[8] a[9]
4
5
9
3
6
5
3
9
6
5
5
1
1
1
1
2
4
3
3
2
4
3
3
3
3
Ｘ=2
1
終了
キーが
全て同じ
レベル4
a[3]
2
1
レベル3
a[2]
終了
Ｘ=5
Ｘ=4
3
3
終了
9
6
5
5
4
5
6
5
9
4
5
6
5
5
5
6
5
5
6
終了
Ｘ=9
Ｘ=6
終了
終了
9
終了
クイックソートの計算時間
分割の段数≒log2 n
各段での時間 O ( n )
平均時間 → O ( n log n )
最悪の場合
ｎ＝ 8
比較回数
7
： 即ち n-1
6
5
4
3
2
1
選択ソートの実行と同じようになり
n-1
Σｉ
i=1
= { n ( n - 1) } / 2
→ O ( n 2)
クイックソートのまとめ
1962年に
C. A. R. Hoareが発表したアルゴリズム
内部整列アルゴリズムの中で最速
不安定な整列アルゴリズム
ある要素を決め、その要素より大きいグループと
小さいグループに分類
ある要素：枢軸
各グループで枢軸を決め直して同じように分割
計算量O（n
log n）
ただし，最悪の場合O (n2)
ソート全体のまとめ
名称
計算量
内部/外
部
安定/不安定
バブルソート
O(n2)
内部
安定
挿入ソート
O(n2)
内部
安定
選択ソート
O(n2)
内部
不安定
バケットソート O(n)
内部
安定
データに制限
有
基数ソート
O(n)
内部
安定
データに制限
有
シェルソート
O（n1.25）～
O（n1.5）
内部
不安定
内部
不安定
クイックソート O(n log n)
備考
最悪O(n2)
演習問題
次の配列を、クイックソートにより並べ替える。
並べ替え領域の左端の添え字を pl、右端の添え字を pr と設定したとき、枢軸は
(pl+pr)/2（小数点以下切り捨て）で示される添え字の位置とする（この配列では添え字 5
の 59）。ここで
1. pl 位置の値が枢軸の値以上になるまで pl を右へずらす。
2. pr 位置の値が枢軸の値以下になるまで pr を左へずらす。
3. pl 位置の値と pr 位置の値を入れ替える。
4. pl と pr が交差して入れ替わるまで、1. から 3. までを繰り返す。
という操作を行うと、配列は
となり、添え字 0 から 5 までの集合と 6 から 11 までの集合に分割される。このとき、以下の問い
に答えよ。
(1) 添え字 0 から 5 までの集合において、pl、pr および枢軸の位置を再設定し、同様に分割したと
き、分割後の配列の並びと pl、pr の添え字位置を示せ。
(2) 添え字 6 から 11 までの集合において、pl、pr および枢軸の位置を再設定し、同様に分割した
とき、分割後の配列の並びと pl、pr の添え字位置を示せ。
名前と学籍番号をご記入のうえ、解答用紙（A4）を提出する
提出先：
工学部電子情報実験研究棟５階
NO.5506室のドアのポストに入れてください
締め切り時間：
来週月曜日（７月７日） 午前９時まで
© Copyright 2024 ExpyDoc
