Algorithms and Data Structures 2014
比較によらない整列
Algorithms and Data Structures 2014
この回の要点
• キーの比較を行う場合、整列の計算量の下限はO(n log n)
• これより速いアルゴリズムは理論上、存在しない・・・はず
• 比較によらない整列
• バケットソート（ビンソート）（bucket sort,bin sort）
• 分布数え上げソート（distribution counting sort）
• 基数ソート（radix sort）
• 計算量
• 時間計算量はいずれもO(n)
• 記憶容量もO(n)が必要
• 制約
• キーが離散的でなければならない
• キーの範囲の制限→基数ソートである程度は解決
• O(n)とO(n log n)の違いは、実はそれほどない
• 定数項の効き具合では、クイックソートのほうが速い
Algorithms and Data Structures 2014
バケットソート
• 原理
• キーの種類の数のバケツを用意
• キーと対応するバケツにデータを入れる
• 先頭バケツから順にデータを取り出す
1
2
44
21
31
23
13
ばらばら
n個
98
1
順に取り出す
3
56
27
放り込んで・・・
1
2
3
4
5
6
・・・
m個のバケツ
2
整列！
3
13
21
23
27
31
44
56
98
97 98 99 100
Algorithms and Data Structures 2014
バケットソートの性質
• 時間計算量
•
•
•
•
データ数n、バケツの数mとする
データを入れる回数O(n)
データを取り出す回数O(m)
トータルではO(n+m)
• 通常は、バケツの数mはデータ数nによって決まるので、m=O(n)とみなせる
• その場合、バケットソートの計算量はO(n)
• メモリー量
• バケツの数だけ必要→O(n)
• 高速性の代償として、大きなメモリーが必要
• 安定性
• 1つのバケツに複数のデータが入った場合、入った順に取り出すようにすれ
ば、同じデータの順序は変化しない
• バケットソートは安定である
Algorithms and Data Structures 2014
バケツの構造
単純な配列で可能
• 同じキーのデータの処理
• 同じキーのデータがなければ、1つのバケツは1つのデータを格納でき
れば良い。
• 同じキーのデータが複数ある場合は、1つのバケツに複数のデータを格
納できる必要がある。
• 安定なソートのためには、入れた順に取り出されなければならない
• バケツはキューでなければならない
可変長配列
リスト構造など
• FIFO（先入れ先出し）構造
1
2
3
4
5
6
・・・
97 98 99 100
Algorithms and Data Structures 2014
Sort.h
キーを返す関数:
データを与えると、そのデータの整数値を返す。
比較によらないソートでは、データは整数値を持
つ必要がある。
#ifndef __Sort__h
#define __Sort__h
/***
*** 並べ替え用
***/
#include <stdio.h>
#include <stdlib.h>
int (*key)(void *d){
PD *pd=(PD*)d;
return pd->age;
}
// プロトタイプ宣言
上の例では、個人情報の整数値として年齢を
使っている。
// 比較によるソート
void sortBubble(void*,int,int(*)(void*,void*));
// …(略)…
// 比較によらないソート
void sortBucket(void*,int,int(*)(void*));
int getCompCount();
int getExchgCount();
#endif // __Sort__h
比較によらないソートは、比較関数の代わ
りにキーを返す関数を与える。
Algorithms and Data Structures 2014
Sort.cc
// …(略)…
#include <limits.h>
#include <math.h>
#include <string.h>
// …(略)…
// バケットソート
void sortBucket(void *d0,int s,int (*key)(void*)){
void **d=(void**)d0;
// 最大と最小を求める
int min=INT_MAX;
int max=INT_MIN;
for(int i=0;i<s;i++){
int k=key(d[i]);
if(k<min) min=k;
if(k>max) max=k;
}
// 最小のキー
// 最大のキー
続く
Algorithms and Data Structures 2014
Sort.cc
// キーの個数を数える
int bn=max-min+1;
// キーの種類数＝バケツの数
int *kn=(int*)malloc(bn*sizeof(int)); // 各キーのデータの個数
for(int i=0;i<bn;i++) kn[i]=0;
for(int i=0;i<s;i++) kn[key(d[i])-min]++;
// 各キーの個数分のバケツの準備
void ***backet=(void***)malloc(bn*sizeof(void**)); // バケツ
for(int i=0;i<bn;i++)
backet[i]=(void**)malloc(kn[i]*sizeof(void*));
// バケツに入れる
int *ki=new int[bn];
for(int i=0;i<bn;i++) ki[i]=0;
for(int i=0;i<s;i++){
int k=key(d[i]);
backet[k-min][ki[k-min]++]=d[i];
}
キー：
キーが5～10の場合：
5
6
バケツの番号 = キー – 最小のキー
続く
7
8
9 10
バケツ： ０ １ ２ ３
４ ５
Algorithms and Data Structures 2014
Sort.cc
// バケツから取り出す
int p=0;
for(int i=0;i<bn;i++){
for(int j=0;j<kn[i];j++)
d[p++]=backet[i][j];
}
// メモリを解放
for(int i=0;i<bn;i++)
free(backet[i]);
free(backet);
free(kn);
free(ki);
}
Algorithms and Data Structures 2014
分布数え上げソート
• 原理
• 有限範囲の整数をキーとするデータの場合、キーの分布（どのキーが
何個あるか）がわかれば、そのデータが何番目であるかもわかる。
•例
• キーの範囲0～9
• キー＝3,7,2,4,3,5,1,2,5
• キーkは、b-1から前にa個分
キー k
0
1
2
3
4
5
6
7
8
9
出現回数 a
0
1
2
2
1
2
0
1
0
0
累計 b
0
1
3
5
6
8
8
9
9
9
キー
1
2
2
3
3
4
5
5
7
順番
0
1
2
3
4
5
6
7
8
Algorithms and Data Structures 2014
分布数え上げソートの実行１
• 3つの配列を使用する
• キーの範囲の数：n
• 累計の配列 b[n]
• データの個数：s
• もとのデータの配列 d[s]
• 整列用の一時データの配列 t[s]
• 手順
•
•
•
•
•
•
b[]←キーの累計
t[]←d[]
t[]を後ろからたどる i=s-1 → 0
t[i]のキーkに対するb[k]を得る
--b[k]
d[b[k]]←t[i]
• 安定性
• t[]を後ろからたどることにより、同一キーの安定性が確保される
Algorithms and Data Structures 2014
分布数え上げソートの実行２
t[i]
i
後ろからコピーする
3
0
7
1
2
2
4
3
3
4
5
5
1
6
8
7
1
5
4
3
3
4
2
2
1
0
8
2
5
7
1
2
2
3
3
4
5
5
累計
5
5
7
6
2
7
d[i]
整列！
実際に使うときは、縦に伸ばす必要はない。
k
0 1 2 3 4 5 6 7 8 9
b[k]
0 1 3 5 6 8 8 9 9 9
b[k]
3
b[k]
1 2
b[k]
0
7
7
b[k]
5
b[k]
4 6
b[k]
2
b[k]
1
6
5
9
b[k]
4
b[k]
3
8
Algorithms and Data Structures 2014
Sort.h
…(略)…
// プロトタイプ宣言
// 比較によるソート
void sortBubble(void*,int,int(*)(void*,void*));
// …(略)…
// 比較によらないソート
void sortBucket(void*,int,int(*)(void*));
void sortCounting(void*,int,int(*)(void*));
int getCompCount();
int getExchgCount();
#endif // __Sort__h
Algorithms and Data Structures 2014
Sort.cc
…(略)…
// 分布数え上げソート
void sortCounting(void *d0,int s,int (*key)(void*)){
void **d=(void**)d0;
// データを仮配列にコピーする
void **t=(void**)malloc(s*sizeof(void*));
memcpy(t,d,s*sizeof(void*));
// 最大と最小を求める
int min=INT_MAX;
int max=INT_MIN;
for(int i=0;i<s;i++){
int k=key(d[i]);
if(k<min) min=k;
if(k>max) max=k;
}
// 最小のキー
// 最大のキー
続く
Algorithms and Data Structures 2014
Sort.cc
// キーの累計を計算する
int n=max-min+1;
// キーの種類数
int *b=(int*)malloc(n*sizeof(int)); // 各キーのデータの個数
for(int i=0;i<n;i++) b[i]=0;
for(int i=0;i<s;i++) b[key(d[i])-min]++;
for(int i=1;i<n;i++) b[i]+=b[i-1];
// 並べ替え
for(int i=s-1;i>=0;i--){
int k=key(t[i]);
d[--b[k-min]]=t[i];
}
// メモリを解放
free(b);
free(t);
}
// t[]のデータをd[]に移動
Algorithms and Data Structures 2014
分布数え上げソートの性質
• 時間計算量
• 各処理の計算量は、
•
•
•
•
•
累計をクリア：O(m)
キーの出現数をカウント：O(n)
累計を計算：O(m)
作業用配列にコピー：O(n)
整列：O(n)
• トータルの計算量はO(n+m)
• メモリー量
• キーの分布累計：O(m)
• 作業用配列：O(n)
• 高速性の代償として、大きなメモリーが必要
• 安定性
• 作業用配列からコピーする際、配列の後ろからコピーすることで、同じキー
の要素の順番は変わらない
• 分布数え上げソートは安定である
Algorithms and Data Structures 2014
基数ソート（Radix sort）
• バケットソート等の問題点
• キーの種類が多い場合、バケツや累計用配列の大きさが
大きくなりすぎる
• テストの点数で並べ替える場合
• バケツは0点用～100点用の101個で済む
• 銀行の預金高で並べ替える場合
• 個人の預金高を最大100億円として
• 0円用～10,000,000,000円用の10,000,000,001個
• しかも、大きい値のほとんどのバケツは空であろう
• キーの種類が多すぎると、使えない
• 実用上は大きな問題
Algorithms and Data Structures 2014
基数ソートの考え方
• 3桁の数字が書かれたカードを並べ替えたい
• 10個の箱を準備し、
• 第1段階：一の位の数で分ける
• 第2段階：小さい箱から十の位の数で分ける
• 第3段階：小さい箱から百の位の数で分ける→整列！
043,438,798,120,012,888,378,210,903,375,221,050,421,580,703
0
1
2
3
4
5
6
7
第1段階
120,210,
050,580
221,421
012
043,903,
703
第2段階
903,703
210, 012
120,
221,421
438
043
050
375,378
580,888
798
第3段階
012,043,
050
120
210,221
375,378
421,
438
580
703,798
888
903
375
8
9
438,798,
888,378
Algorithms and Data Structures 2014
なぜうまくいくのか？
• 各桁の整列の安定性が必要
• 安定な整列ならば、前の桁の順序を保って整列する
• 前の桁の整列が生きる
一の位で整列
120,210,050,580,221,421,012,043,903,703,375,438,798,888,378
十の位で整列
一の位は整列されたまま
903,703,210,012,221,120,421,438,043,050,375,378,580,888,798
百の位で整列
十の位は整列されたまま
012,043,050,120,210,221,375,378,421,438,580,703,798,888,903
Algorithms and Data Structures 2014
Sort.h
…(略)…
// プロトタイプ宣言
// 比較によるソート
void sortBubble(void*,int,int(*)(void*,void*));
// …(略)…
// 比較によらないソート
// sortXXX(void *d0,int s,int (*key)(void*));
void sortBucket(void*,int,int(*)(void*));
void sortCounting(void*,int,int(*)(void*));
void sortRadix(void*,int,int(*)(void*),int=10);
int getCompCount();
int getExchgCount();
#endif // __Sort__h
デフォルトの基数は10
（プロトタイプ宣言の仮引数の後
に=に続いて値を書くと、その引数
は省略可能であり、省略した場合
はこの値が使われる）
Algorithms and Data Structures 2014
Sort.cc
…(略)…
// 桁cを分布数え上げソート
// d : 元データ配列、t : 仮データ配列、s : データ数、 r : 基数
// c : 桁、 b : キーの個数用配列、 key : キー関数
void radixSort(void **d,void **t,int s,int r,int c,int *b,int
(*key)(void*)){
int a=(int)pow(r,c);
// r進数c桁の数
// 仮配列にCOPY
memcpy(t,d,s*sizeof(void*));
// キーの累計を計算する
for(int i=0;i<r;i++) b[i]=0;
for(int i=0;i<s;i++) b[(key(t[i])/a)%r]++;
for(int i=1;i<r;i++) b[i]+=b[i-1];
// 並べ替え
for(int i=s-1;i>=0;i--){
int k=(key(t[i])/a)%r;
d[--b[k]]=t[i];
}
}
実際の並べ替えは
分布数え上げソート
続く
Algorithms and Data Structures 2014
Sort.cc
// 基数ソート
// r : 基数[10]
void sortRadix(void *d0,int s,int (*key)(void*),int r){
void **d=(void**)d0;
// 最大を求める
int max=INT_MIN;
for(int i=0;i<s;i++){
int k=key(d[i]);
if(k>max) max=k;
}
// 最大のキー
// 基数ソートする回数
int rsc=(int)ceil(log(max+1)/log(r));
基数が10で、最大値が
1000だった場合、4回の基
数ソートが必要
log10 1000 3
log10 1001 4
// 各桁のソート
int *b=(int*)malloc(r*sizeof(int));
// キーの個数配列
void **t=(void**)malloc(s*sizeof(void*)); // 仮配列
for(int c=0;c<rsc;c++)
radixSort(d,t,s,r,c,b,key);
free(t);
free(b);
}
Algorithms and Data Structures 2014
比較によらないソートの性能
1000
N人のPDデータ
キーは年齢（10～99）
100
10
bucket
counting
1
radix
O(N logN)
O(N)
0.1
10000
100000
1000000
Algorithms and Data Structures 2014
比較によらないソートの性能（2）
1000
100
N人のPDデータ
キーは、名前の4文字分を整
数化した264 (=331776)通り
10
bucket big
counting big
1
基数は100
radix big
O(N logN)
O(N)
0.1
10000
100000
1000000
Algorithms and Data Structures 2014
整列のまとめ
• 比較による整列
•
•
•
•
•
•
•
バブルソート
選択ソート
挿入ソート（★遅い並べ替えではおすすめ）
シェルソート（挿入ソートの改良）
ヒープソート
マージソート
クイックソート（★整列アルゴリズムの王様）
• 比較によらない整列
• バケットソート
• 分布数え上げソート（★整数キーの整列ではおすすめ）
• 基数ソート
Algorithms and Data Structures 2014
整列アルゴリズムの比較
bubble
selection
insertion
heap
merge
shell(knuth)
shell(tokuda)
quick1
quick2
bucket
counting
radix
bucket big
counting big
radix big
O(N)
O(N logN)
O(N^2)
10000
1000
100
10
1
0.1
0.01
100
1000
10000
100000
1000000
Algorithms and Data Structures 2014
比較によらない整列
終了
© Copyright 2024 ExpyDoc
