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

アルゴリズムと
データ構造
第11回
ソート（2）:
バケットソート，基数ソート
先週の復習
ソートの基本
 ソートアルゴリズムの要件

全体の計算量
比較
交換
バブルソート
O(n2)
n(n-1)/2 回
（a[j]<a[j-1]）の
個数回
挿入ソート
O(n2)
選択ソート
O(n2)
（a[j]<a[j-1]）の
約n(n-1)/4 回
個数回
n(n-1)/2 回
n-1回
先週の演習問題
解説
i=6
0
1
2
3
4
5
答え:
32
15
53
28
32
67
41
28
53
86
74
67
15
32
74
67
86
41
53
先週の演習問題
先頭から、すでに整列が終
わったとみなされる範囲はもう
ソート済みとみなす。
last
解説
k=0
k=2
k=4
k=7
答え:
0
1
2
3
4
5
6
7
32
15
53
15
67
15
28
15
86
15
74
15
15
41
0
1
2
3
4
5
6
7
15
32
28
28
53
67
28
28
86
41
74
41
41
0
1
2
3
4
5
6
7
15
28
32
41
53
67
41
41
86
74
74
0
1
2
3
4
5
6
7
15
28
32
41
53
67
74
86
j
単純ソートアルゴリズムに関する小テスト
第１問
次のプログラムは、バブルソートを行うプラグラムである
#include <stdio.h>
#define N 6
/* データ数 */
void main(void)
{
static int a[] = { 80, 41, 35, 90, 40, 20};
int t, i, j;
for ( i=0; i< N-1; i++){
for ( j = N-1; j > i; j-- ) {
if ( a[j] < a[j-1]) {
t = a[j]; a[j] = a[j-1]; a[j-1]= t;}
}
}
}
iループにおいて、各iの値のときの処理後、配列a[]の並びがどのように
なるかを示せ。
第２問
次のプログラムは、単純挿入ソートを行うプラグラムである
#include <stdio.h>
#define N 6
void main(void)
{
static int a[] = { 80, 41, 35, 90, 40, 20};
int t, i, j;
for ( i=1; i< N; i++){
for ( j = i-1; j >=0; j-- ) {
if ( a[j] > a[j+1]) {
t = a[j]; a[j] = a[j+1]; a[j+1]= t;}
else
break;
}
}
}
iループにおいて、各iの値のときの処理後、配列a[]の並びがどのように
なるかを示せ。
第３問
次のプログラムは、単純選択ソートを行うプラグラムである
# include <stdio.h>
#define N 6
void main(void)
{
static int a[] = { 80, 41, 35, 90, 40, 20};
int t, i, j, min, s;
for ( i=0; i< N-1; i++){
min = a[i]; s=i;
for ( j = i+1; j <N; j++ ) {
if ( a[j] < min ) {
min = a[j]; s=j;}
}
t = a[i]; a[i] = a[s]; a[s] = t;
}
}
iループにおいて、各iの値のときの処理後、配列a[]の並びがどのように
なるかを示せ。
小テスト問題の解説
問題１：バブルソートに関する

配列の後ろから先頭に向かってスキャンし，隣接する２項を比較し、後の項
が前の項より小さければ、両項の入れ替えを行うを繰り返す
i=0
80
20
41
35
90
40
20
i=1
20
80
35
41
35
90
40
i=2
20
35
40
80
41
40
90
i=3
20
35
40
41
80
41
90
i=4
20
35
40
41
80
90
答え：
i=0: {
20
,
80
,
41 ,
35
,
90
,
40
}
i=1: {
20
,
35
,
80 ,
41
,
40
,
90
}
i=2: {
20
,
35
,
40 ,
80
,
41
,
90
}
i=3: {
20
,
35
,
40 ,
41
,
80
,
90
}
i=4: {
20
,
35
,
40 ,
41
,
80
,
90
}
問題2：単純挿入ソートに関する


０〜(i-1)番目まではすでにソート済
ｉ番目の要素を０〜ｉの間の適切な位置に挿入する
i=1
80
i=2
41
80
i=3
35
41
80
i=4
35
41
80
90
i=5
35
40
41
80
答え：
35
90
40
20
90
40
20
40
20
20
90
i=1: {
41
,
80
,
35 ,
90
,
40
,
20
}
i=2: {
35
,
41
,
80 ,
90
,
40
,
20
}
i=3: {
35
,
41
,
80 ,
90
,
40
,
20
}
i=4: { 35
,
40
,
41 ,
80
,
90
,
20
}
i=5: {
,
35
,
40 ,
41
,
80
,
90
}
20
問題3：単純選択ソートに関する

整列されていない部分から最小要素を選び，先頭と入
れかえる処理を繰り返す
i=0
80
20
41
35
90
40
20
i=1
20
41
35
35
90
40
80
i=2
20
35
40
41
90
40
80
i=3
20
35
40
41
90
41
80
i=4
20
35
40
41
80
90
80
答え： i=0: {
i=1: {
20
,
41
,
35 ,
90
,
40
,
80
}
20
,
35
,
41 ,
90
,
40
,
80
}
i=2: {
20
,
35
,
40 ,
90
,
41
,
80
}
i=3: { 20
,
35
,
40 ,
41
,
90
,
80
}
i=4: {
,
35
,
40 ,
41
,
80
,
90
}
20
本日の内容

比較によらないソート

バケットソート

基数ソート
バケットソート (bucket sort)



別名ビンソート(bin sort) ともいう
計算量 O (n)
バケットソートを適用できる条件：
n個の要素は整数で0以上m-１以下の値をとるとする。
バケット
0
1
2
m-1
バケットソートの原理
１．値kの要素を入れる箱(バケットB[k]、ただし、
kは０≦k≦m-1)を準備し、各要素A[i]を
B[A[i]]に入れる。
B[A[i]] = A[i];
A = {m-1, 0, 1… , 2}
２．バケットをB[0], B[1], …,B[m-1]の順に連結
する。
0
1
B[0]
B[1]
m-1
B[2]
B[m-1]
バケットソートの概念図
配列 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]
最後にデータをバケット
から順に取り出し，
配列に戻して整列終了
キーに重複がある場合
バケット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]
バケットソートの実現（手順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]
空のバケット
[3]
[4]
A[7]
[5]
A[5]
[6]
A[3]
A[1]
A[4]
A[0]
バケットソートの実現（手順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]
バケットソートの特徴



計算量O(n)
バケットのためのメモリが必要．
（所要メモリ量はデータ数nに比例）
キーの種類数 m がある程度小さい場合に使用可．
種類数mが大きい場合は現実的でない．
例
int型=4バイト(32ビット) –2147483648～2147483647
種類数は約40億種
基数ソート（radix sort）



radix : 基数．基礎として用いる数．
 10進法の基数は10
（0から9まで）
 16進法の基数は16
（0から15（F）まで）
整列対象となるキーを，いくつかのサブキーに分割
し，下位から上位の順に，サブキーをもとに安定な
整列を行う
サブキーの整列には，計算量O(n)の安定なアルゴ
リズムを使用
基数ソートの例
基数個のバケットを用意
各バケットは待ち行列（キュー）
基数１０で，３桁に分割した場合
バケット 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
基数ソートの例
基数個のバケットを用意
各バケットは待ち行列
基数１０で，３桁に分割した場合
配列 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
基数ソートの例
基数個のバケットを用意
各バケットは待ち行列
基数１０で，３桁に分割した場合
配列 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
基数ソートによる文字列の整列


k文字の文字列において、i番目の文字をキーとして
バケットソートを適用することで整列する。
ただし、処理は文字列の末尾から先頭の順に行う。
k=3
さとう
ささき
さわだ
←i
辞書式順序(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
あり＜りあ，あおい＜あじあ，まき＜まきば
数字の場合・・・
300＜310
空文字
例(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
e
基数ソートの特徴

分割数 k とすると，ソートの計算量O(k n)

kがデータ数 n より十分小さい場合O(n)

バケットのためのメモリが必要．
（所要メモリ量はデータ数nに比例）


キーのパターンを分割しても，キーの大小関係が
維持される場合に利用可（浮動小数点数は×）
整数や短い文字列のソートに利用
問題
次の３文字の系列を基数ソートで辞書式順序に
並べていく過程を示せ。
( J O Y ), ( R E D ), ( R U N ), ( M I D )
１回目
２回目
３回目
解答
( 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 )
まとめ
配列 A

バケットソート O(n)


値kの要素を入れる箱(バケット
B[k]、ただし、kは０≦k≦m-1)を準
備し、各要素A[i]をB[A[i]]に入れ
たあと、バケットの中身を連結する
基数ソート

[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]
O(n)
整列対象となるキーを，いくつか
のサブキーに分割し，下位から上
位の順に，サブキーをもとに安定
な整列を行う
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) を用いて整列する手順を図を
用いて説明せよ。
(問2)次の３文字の系列を基数ソートで辞書式順序に並べて
いく過程を示せ。
(B U T ),
１回目
( F A N ),
２回目
( A N Y ),
３回目
( K I D )
名前と学籍番号をご記入のうえ、解答用紙（A4）を提出する
提出先：
工学部電子情報実験研究棟５階
NO.5506室のドアのポストに入れてください
締め切り時間：
来週月曜日（6月30日）午前９時まで

Download Report