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

データ構造とアルゴリズム
第11回
整列
～シェルソート，クイックソート～
1
問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
2
問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]
3
問2 解答
１回目
２回目
３回目
KID
FAN
BUT
ANY
FAN
KID
ANY
BUT
ANY
BUT
FAN
KID
問1：94.3%,
問2：95.8%
4
復習1

配列の後ろから先頭に向かってスキャ
ンし，隣り合う２つの要素の大小関係
が逆であったら入れかえる
1
3
挿入ソート


未ソート
バブルソート


2
O(n )のソート
現在処理対象となっているデータを，
整列済みのデータ列内の適切な位置
に挿入する
5
9
10
7
10 11
7
20 17
6
ソート済
3
5
8
選択ソート

整列されていない部分から最小要素
を選び，先頭と入れかえる処理を繰り
返す
未ソート
1
3
5
入れかえ
9
10
7
20 17 18
最小値
5
復習2
配列 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
[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
2
ヒープソート O(n log n)

バケットB
4
7 13
4
6
本日の内容

シェルソート

クイックソート
7
シェルソート (p.109)
8
シェルソート（Shell sort）

1959年に D. L. Shellが発表したアルゴリズム

挿入ソートを変形

計算量O（n1.25）～O（n1.5）

安定ではない
9
シェルソートの原理
離れたデータの組を挿入ソ
ートで整列し，順次，要素
間の距離を減らして整列を
繰り返す


55 74 3 45 13 87 46 30
4つずつ離れたデータの組
13 74 3 30 55 87 46 45
右の例は4, 2, 1と間隔を減らしている
…,121，40, 13, 4,
1ならばO（n1.25）
(3k−1)/2 k＝1,2,3・・・
2つずつ離れたデータの組
3 30 13 45 46 74 55 87
(Knuthの解析実験)

…,15, 7, 3,
1ではO（n1.5）
1つずつ離れたデータの組
3 13 30 45 46 55 74 87
２k−1 k＝1,2,3・・・
整列終了
10
練習問題


以下のデータをシェルソートで昇順に整列しなさい
整列の間隔は4、2、1の順で減らすこと。
10, 5 , 4, 27, 2, 6, 3, 20, 1, 0, 8, 9, 7, 23, 13, 42
11
解答
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
12
クイックソート (p.96～)
13
クイックソート(quick sort)

1962年に C. A. R. Hoareが発表したアルゴリズム

内部整列アルゴリズムの中で最速

不安定な整列アルゴリズム
計算量O（n log n）
ただし，最悪の場合O (n2)

14
クイックソートの原理
1.
ソートする範囲のデータから適当な軸要素(枢軸、pivot)νを
選ぶ。
2.
要素をひとつずつ調べて、νより小さいグループと大きいグ
ループに分割する。
3.
小グループと大グループ各々に上記１．と２．を適用する。
4.
各々のグループが分割できなくなるまで分割を繰り返す。
大きな問題を小さな問題に分けて解決していく
⇒ 分割統治（divide and conquer）
15
クイックソートの疑似コード
void quicksort(int l, int r, int A[])
{
int k; /* 枢軸より大きい部分の開始位置 */
軸要素を決める;
if (キーがすべて同じ) 終了;
vより小さい部分と大きい部分に分割し，
大きい部分の先頭の位置kを返す;
quicksort(l, k – 1,A);
quicksort(k, r, A);
/* 小さい部分を整列 */
/* 大きい部分を整列 */
}
16
軸要素(pivot)の選び方

方法1）データの中からランダムに一つ選ぶ。

方法2）ランダムに３要素選びその中央値をとる。

方法3）左からみて最初に得られた二つの異なる値
の大きい方をとる。
ポイント：
小さい部分と大きい部分の要素数が
ほぼ半々になるような軸要素が良い
17
pivot
軸要素の位置を返す関数
int pivot(int i, int j, int A[ ])
i
k→
{
A 4 4 4
int pv, k;
k = i + 1;
while(A[i] == A[k] && k <= j) k++;
if (k > j) pv = -1; /* キーが全て同じ */
else if (A[i] >= A[k]) pv = i;
else pv = k;
return(pv);
}
枢軸の位置
6
6
5
j
3
枢軸
枢軸未満のキー
枢軸以上のキー
が必ずそれぞれ
1つ以上ある
↓
partition()のループ変数
i, j がl～rの範囲を超え
ないことが保証される
18
分割の手順
要素が軸要素 v より小さい限り l を右へ、
要素が v 以上である限り r を左へ動かす
i
l
r
j
A
キー＜v
キー ≧ v
l, r : カーソル
v : 枢軸
19
分割の手順(続き)
l <= r なら A[l] とA[r] を入れかえて１．に戻る
i
l
j
r
A
キー＜ν
l > r なら分割終了
i
キー＞ν
r
l
j
A
それぞれの部分に対して
再帰的に処理をくりかえす
20
分割手順の疑似コード
int partition(int i, int j, int v, int A[])
{
int l = i, r = j, k;
for(;;){
while (A[l] < v) l++;
while (A[r] >= v) r--;
if(l <= r){
A[l]とA[r]を交換；lとrを1つ移動;
}
else ループから抜ける;
}
k = l;
return k;
}
21
v = 3の場合
←r
l→
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
分割終了
r =2
l=3
22
各々のグループをさらに分割
a[0] a[1] a[2]
レベル2
2
1
v=2
1
1
1
終了
キーが
全て同じ
レベル4
レベル5
ソート終了
a[4] a[5] a[6] a[7] a[8] a[9]
4
5
9
3
6
5
3
9
6
5
5
v=5
1
レベル3
1
a[3]
2
4
3
3
2
4
3
3
終了
v=4
6
5
5
9
v=9
3
3
9
3
3
終了
4
5
6
5
4
5
6
5
5
5
6
5
5
6
終了
v=6
終了
終了
9
終了
23
クイックソートの計算時間

分割の段数≒log2 n

各段での時間 O ( n )

平均時間 → O ( n log n )
24
最悪の場合
比較回数
7
6
5
4
3
2
1
n-1
Σｉ
i=1
= { n ( n - 1) } / 2
→ O ( n 2)
25
まとめ
名称
計算量
内部/
外部
安定/
不安定
バブルソート
O(n2)
内部
安定
挿入ソート
O(n2)
内部
安定
選択ソート
O(n2)
内部
不安定
クイックソート O(n log n) 内部
備考
不安定最悪O(n2)
ヒープソート
O(n log n) 内部
不安定
マージソート
O(n log n) 外部
安定
ビンソート
O(n)
内部
安定
データに制限有
基数ソート
O(mn)
内部
安定
データに制限有
26
今後の予定
7/23
7/30

ヒープソートの演習(2階電算室に集合)
期末試験（掲示をよく見ること）
27
本日の問題 (問1)

i=0, j=9, 軸要素v = 4の場合、関数partitionを実行すると
配列の中身がどのように変化していくかを書け。また、分
割終了時の l と r は各々いくつか。
Start
0
1
2
3
4
5
6
7
8
9
3
1
4
1
5
9
2
6
5
3
(1)
(2)
(3)
28

Download Report