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

データ構造とアルゴリズム
第11回
整列
～バケットソート，基数ソート，ヒープソート～
1
前回の課題(1)


正解は75.3%
下記の疑似コードにしたがってソートする時，外側の
forループの各 i での配列aの内容を記せ．
配列の要素数nは6とし，配列aの初期値は先頭から
順に{ 8, 4, 3, 9, 1, 5 }であるものとする．
void sort(int a[], int n)
{
int i, j;
for (i = 0; i < n - 1; i++)
for (j = n - 1; j > i; j--)
if(a[j] > a[j-1])
a[j]とa[j-1]を交換;
降順！
}
2
本日の内容


比較によらないソート

バケットソート

基数ソート
ヒープソート
4
バケットソート (bucket sort)



別名ビンソート(bin sort) ともいう
計算量 O (n)
バケットソートを適用できる条件：
n個の要素は整数で0以上m-１以下の値をとるとする。
バケット
0
1
2
m-1
5
バケットソートの原理
１．値kの要素を入れる箱(バケットB[k]、ただし、
kは０≦k≦m-1)を準備し、各要素A[i]を
B[A[i]]に入れる。
B[A[i]] = A[i];
A = {0, m-1, … , 2}
２．バケットをB[0], B[1], …,B[m-1]の順に連結
する。
0
1
B[0]
B[1]
m1
B[2]
B[m-1]
6
バケットソートの概念図
配列 A
キーに
重複がない場合
バケットB
[0] 1
[0]
A[2]
[1] 4
[1]
A[0]
[2] 0
[2]
A[4]
[3] 6
[3]
[4] 2
[4]
空のバケット
最後にデータをバケット
から順に取り出し，
配列に戻して整列終了
A[1]
[5]
[6]
A[3]
7
キーに重複がある場合
バケットB
配列 A
[0]
1
[1]
6
[0] A[2]
i番目のバケットに要素が
何個入るか分からない
⇒連結リストで表現
[1] A[8] A[6] A[4] A[0]
[2]
0
[3]
6
[2] A[9]
[4]
1
[5]
5
[3] なし
[6]
1
[4] A[7]
[7]
4
[5] A[5]
[8]
1
[9]
2
[6] A[3] A[1]
8
バケットソートの実現（手順1）
バケットB への格納
配列 A
[0]
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
1
6
0
6
1
5
1
4
1
2
バケットB
[0]
A[2]
[1]
A[8]
[2]
A[9]
A[6]
A[4]
A[0]
空のバケット
[3]
[4]
A[7]
[5]
A[5]
[6]
A[3]
A[1]
9
バケットソートの実現（手順2）
バケットB[i]とB[i+1]の要素を連結 (CONCATENATE)する。
B
[0]
A[2]
[1]
A[8]
[2]
A[9]
A[6]
A[7]
[5]
A[5]
[6]
A[3]
A[0]
この例では，先頭に要素を追加
したが，末尾に追加すれば，順
序関係が維持される⇒安定
[3]
[4]
A[4]
A[1]
10
バケットソートの特徴



計算量O(n)
バケットのためのメモリが必要．
（所要メモリ量はデータ数nに比例）
キーの種類数 m がある程度小さい場合に使用可．
種類数mが大きい場合は現実的でない．
例
int型=4バイト(32ビット) –2147483648～2147483647
種類数は約40億種
11
基数ソート（radix sort）



radix : 基数．基礎として用いる数．
 10進法の基数は10
（0から9まで）
 16進法の基数は16
（0から15（F）まで）
整列対象となるキーを，いくつかのサブキーに分割
し，下位から上位の順に，サブキーをもとに安定な
整列を行う
サブキーの整列には，計算量O(n)の安定なアルゴ
リズムを使用
12
基数ソートの例
基数個のバケットを用意
各バケットは待ち行列
基数１０で，３桁に分割した場合
バケット B
配列 A
[0]
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[10]
100
602
90
362
128
517
123
454
112
230
231
一の位で
バケット
ソート
[0]
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
配列 A
100 90 230
231
602 362 112
123
454
517
128
[0]
[1]
先頭から [2]
連接
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[10]
100
90
230
231
602
362
112
123
454
517
128
13
基数ソートの例
基数個のバケットを用意
各バケットは待ち行列
基数１０で，３桁に分割した場合
配列 A
[0]
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[10]
バケット B
100
90
230
231
602
362
112
123
454
517
128
十の位で
バケット
ソート
[0]
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
配列 A
100 602
112 517
123 128
230 231
454
362
90
[0]
[1]
先頭から [2]
連接
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[10]
100
602
112
517
123
128
230
231
454
362
90 14
基数ソートの例
基数個のバケットを用意
各バケットは待ち行列
基数１０で，３桁に分割した場合
配列 A
[0]
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[10]
配列 A
バケット B
100
602
112
517
123
128
230
231
454
362
90
百の位で
バケット
ソート
[0]
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[0]
[1]
100 112 123 128
先頭から [2]
230 231
[3]
連接
362
[4]
454
[5]
517
[6]
602
[7]
[8]
[9]
[10]
90
90
100
112
123
128
230
231
362
454
517
602 15
基数ソートによる文字列の整列


k文字の文字列において、i番目の文字をキーとして
バケットソートを適用することで整列する。
ただし、処理は文字列の末尾から先頭の順に行う。
k=3
さとう
ささき
さわだ
←i
16
辞書式順序(lexicographical order)


単語 x = a1a2…akと y = b1b2…bkについて考える．
あるiに対し、aj=bj j=1,2,…, i-1で、かつai＜biのとき、
x＜yと定義する。ただし空文字はどの文字より小さ
いとする。
例 ab＜ba,
abd＜aca,
bc ＜bcd
あり＜りあ，あおい＜あじあ，まき＜まきば
空文字
17
例(k=3)
（基数 128) 一般的な計算機での文字コードの種類数
辞書式順序に
整列できた
[0] [1] [2]
[0] [1] [2]
[0] [1] [2]
[0] [1] [2]
a
c
t
p
a
k
f
m
b
d
a
t
b
d
m
c
p
f
a
k
m
c
k
t
d
a
a
f
b
p
a
a
b
c
d
f
k
m
p
t
n
a
h
u
n
e
o
a
u
i
d
t
e
t
y
y
x
p
g
g
n
h
u
i
a
a
u
o
n
e
d
e
g
g
p
t
t
x
y
y
a
a
e
h
i
n
n
o
u
u
p
t
y
e
g
d
y
x
g
t
n
n
u
a
i
o
e
a
u
h
d
y
g
t
g
x
y
p
t
e18
実装例
基数ソートを実装する際のバケットのデータ構造の例
 基数４の場合
(4進数 13, 12, 11, 22, 23を
バケットに入れた場合)
バケットごとに，先頭へのポインタと
末尾へのポインタを用意
B [0]
[1]
[2]
[3]
11
末尾に追加
12
22
13
23
19
基数ソートの特徴

分割数 k とすると，ソートの計算量O(k n)

kがデータ数 n より十分小さい場合O(n)

バケットのためのメモリが必要．
（所要メモリ量はデータ数nに比例）


キーのパターンを分割しても，キーの大小関係が
維持される場合に利用可（浮動小数点数は×）
整数や短い文字列のソートに利用
20
問題
次の３文字の系列を基数ソートで辞書式順序に
並べていく過程を示せ。
( J O Y ), ( R E D ), ( R U N ), ( M I D )
１回目
２回目
３回目
21
解答
( J O Y ), ( R E D ), ( R U N ), ( M I D )
１回目
２回目
３回目
( R E D )
( R E D )
( J O Y )
( M I D )
( M I D )
( M I D )
( R U N )
( J O Y )
( R E D )
( J O Y )
( R U N )
( R U N )
22
ヒープソート(heap sort)(p.94)



ヒープを用いてデータの整列を行うアルゴリズム
計算量 O (n log n)
ヒープ : 配列により半順序木を実現したもの
常に子が親より
大きい木の例
常に子が親より
小さい木の例
3
5
6
9
8
10 18 9
9
10
8
10
6
4 1
9
3
2
7
6
23
ヒープソートの原理
１．ヒープ（半順序木）を作る（優先度つき待ち行列
に入れる）
２．以下の処理を繰り返して並べかえる
1. ヒープの先頭の要素と末尾の要素を交換
2. [先頭]～[末尾-１]の部分の半順序を回復させる
優先度つき
リストＬ
２，９，５，６，… 待ち行列
９
６
５
２
24
半順序木の構成例
初期状態 10
半順序木 3
6
5
9
9
5 15 15 12 3 18
6 8 9 10 10 18
9 8 11 9 20 10
9 15 11 15 20 12
10
3
6
5
5
9
15
15 12
3 18 9 8 11 9 20 10
初期状態
6
9
8
9
10
10 18 9 15 11 15 20 12
半順序木
25
半順序木の構成法
部分木の根の要素を適切な位置まで下げる操作を
繰り返すことで，半順序木をボトムアップに構築する
10
← a[0]
6
15
18
赤字は交換が
必要な箇所
9
5
3
要素数 n = 15
9
15
8
11
12
9
20
← a[n/2-1]
(=a[6])
a[n-1]
(=a[14])
10 ←
26
半順序木の構成法
10
← a[0]
6
9
5
9
8
3
18
9
15
11
10
15
20
12
27
半順序木の構成法
10
← a[0]
9
3
6
18
9
10
9
8
5
15
11
15
20
12
28
並べかえ前の状態
3
5
6
9
8
9
10
10 18 9 15 11 15 20 12
初期状態：ヒープは配列全体を占めている
[0]
a
[n-1]
3 5 9 6 8 9 10 10 18 9 15 11 15 20 12
29
並べかえの手順(1)

半順序木の根と右端の葉を交換
3
5
6
9
8
9
5
10
10 18 9 15 11 15 20 12
[0]
a
12
6
9
8
9
10
10 18 9 15 11 15 20 3
[n-1]
12 5 9 6 8 9 10 10 18 9 15 11 15 20 3
30
並べかえの手順(2)

残りの部分の半順序の回復
子が親より小さい間，
2つの子のうち
小さい方の子
と親を交換していく
この部分のヒープを再構成
この部分の
半順序を
回復させる
12
5
6
9
8
9
10 18 9 15 11 15 20
3
[n-2] [n-1]
[0]
a 12 5 9 6 8 9 10 10 18 9 15 11 15 20
5 6
10
10
12
3
31
並べかえの手順(3)

半順序木の根と右端の葉を交換
5
20
6
10
6
9
8
9
10
12 18 9 15 11 15 20 3
10
9
8
9
10
12 18 9 15 11 15 5
[0]
a 5 6 9 10 8 9 10 12 18 9 15 11 15 20
20
5
3
[n-1]
3
32
並べかえの手順(4)

残りの部分の半順序の回復
20
6
10
12 18
9
8
9
9 15 11 15
10
5
3
この部分のヒープを再構成
[0]
a
[n-3] [n-2][n-1]
33
最終的な状態
以上の操作を繰り返す ⇒ 降順に並ぶ
10
9 9 9 8 6
5 3
34
最終的な状態
最下段の右端からみると昇順
10
9 9 9 8 6
5 3
35
昇順に並べるには？

ヒープを構成するときの親子の大小関係を
逆転させればよい
昇順にしたいときは，
子が親より小さい
半順序木を作る
20
18
6
3
5
15
15
11
3
降順にしたいときは，
子が親より大きい
半順序木を作る
12
6
9
8
9
10
5 9 8 10 9 9 10 10 18 9 15 11 15 20 12
36
ヒープソートの計算量
swap (a[1], a[i]);
最小値を取り出す
O (1)
downMin (…);
半順序の回復
O ( log (i-1) )
ヒープの先頭から最小値を除く処理
→ n-1 回繰り返す
合計回数＜ (n-1)・log(n-1) ≒ n log n
ヒープソート全体で
→ 常にO (n log n)
37
本日の問題
(問1)次の5個の整数 {4, 7, 5, 6, 7}をバケットソートでバ
ケットB[i]( 0 ≦ i < 10) を用いて整列する手順を図を
用いて説明せよ。
(問2)次の３文字の系列を基数ソートで辞書式順序に並べて
いく過程を示せ。
(B U T ),
１回目
( F A N ),
２回目
( A N Y ),
( K I D )
３回目
38

Download Report