整列アルゴリズムの基礎

Algorithms and Data Structures on C
整列アルゴリズムの基礎
Algorithms and Data Structures on C
この回の要点
• 整列とは？
• 整列処理の意味
• 整列の種類
• 整列の計算量
• 整列の安定性
• 単純な整列アルゴリズム
• バブルソート
• 選択ソート
• 挿入ソート
• それぞれのソートの特徴と実装
Algorithms and Data Structures on C
整列（Sorting）とは
• 整列という操作
• レコードの集まりを、キーの値の大小関係に従って並べ替える操作
• 小さい→大きい＝昇順（ascending order）
• 大きい→小さい＝降順（descending order）
• データには、同じキーを持つものがあってもよい
• 同じキーのデータは連続して整列される
• 整列アルゴリズムの種類
• 比較による整列
• バブルソート、選択ソート、挿入ソート：O(n2)
• シェルソート：O(n1.5)
• ヒープソート、マージソート、クイックソート：O(n log n)
• 比較によらない整列（デジタルソート）
• バケットソート（ビンソート）、分布数え上げソート、基数ソート：O(n)
Algorithms and Data Structures on C
整列の計算量
• 比較による整列
• n個のデータを整列するときに必要な処理
• 2つのデータの大小を判定する（比較）
• 必要ならばそれらを入れ替える（交換）
• アルゴリズムによって、2つの処理の回数の比率が異なる
• 扱うデータがどちらにコストがかかるか、によって使い分ける
• データのサイズが大きい場合、データそのものを交換するのにコストが
かかる
• キーの構造が複雑な場合、比較にコストがかかる
• 計算量だけでなく、定数項部分も重要
• 高速なアルゴリズムは処理が複雑である傾向がある
• nが小さいときは、単純なアルゴリズムのほうが速いこともある
• 比較によらない整列
• 時間的にはO(n)で整列可能であるが、メモリ量もO(n)である
• 時間的にも、O(n)とO(n log n)とは、実用的にはそれほど差はない
Algorithms and Data Structures on C
O(n)とO(n log n)とO(n2)との比較
1E+13
1E+11
1E+09
n
n log(n)
n*n
10000000
100000
1000
10
0.1 1
100
10000
1000000
Algorithms and Data Structures on C
安定な整列
• 安定な（stable）整列とは
• 同じキーを持つデータがある場合に、それらの順序関係が保たれる整列
• すべての整列アルゴリズムが安定であるとは限らない
• 単純な（遅い）アルゴリズムは安定の傾向
• 複雑な（速い）アルゴリズムは非安定の傾向
• ただし、サブキーを利用することで、確実に安定にできる
• 安定性の利点
• 複数のエントリーを持つレコードを、1つのキーによって整列するような場合
整列前：７
９
５a
４
８
５b
２
安定なソートは
必ずこうなる
整列後①：２
４
５a
５b
７
８
９
整列後②：２
４
５b
５a
７
８
９
非安定なソートは
どちらになるか
わからない
Algorithms and Data Structures on C
単純な整列アルゴリズム
• 以下の3種類
• バブルソート
• 選択ソート
• 挿入ソート
• いずれもO(n2)の計算量
• プログラムとして実装した場合、データ数nに対して2重のforループ構造とな
る。
• nが大きいと遅くて使いものにならない
• アルゴリズムが簡単ですぐに実装できる
• 少ないデータを整列するには重宝
Algorithms and Data Structures on C
ソート関数の形
• 任意のポインタの配列を並べ替える関数
• sortXXXXX(配列,サイズ,比較関数)
• XXXXXは並べ替えのタイプ
• 配列は任意のポインタの配列
• サイズは配列の要素数
• 比較関数
• int *compare(void *d1,void *d2)
• d1=d2ならばゼロ
• d1<d2ならば負の数
• d1>d2ならば正の数、を返す
Algorithms and Data Structures on C
Sort.h
#ifndef __Sort__h
#define __Sort__h
/***
*** 並べ替え用
***/
#include <stdio.h>
#include <stdlib.h>
// プロトタイプ宣言
void sortBubble(void*,int,int(*)(void*,void*));
void sortSelection(void*,int,int(*)(void*,void*));
void sortInsertion(void*,int,int(*)(void*,void*));
#endif // __Sort__h
Algorithms and Data Structures on C
バブルソート
• 原理
• 配列の後ろから先頭に向かってスキャンし、隣り合う要素の大小関係
が逆なら入れ替える
6
2
7
1
5
1
4
1
1
1
3
3
4
5
7
1
1
1
6
2
2
2
7
3
5
3
4
3
3
4
5
7
2
6
3
3
3
7
4
5
4
4
5
4
7
時間
Algorithms and Data Structures on C
Sort.cc
/*** ソートの実装 ***/
#include "Sort.h"
// バブルソート
void sortBubble(void *d0,int s,int (*comp)(void*,void*)){
void **d=(void**)d0;
次のスライドで説明
for(int i=0;i<s-1;i++){
for(int j=s-1;j>i;j--){
if(comp(d[j-1],d[j])>0){
void *t=d[j];
②
①
③
d[j]=d[j-1];
d[j-1]=t;
}
}
}
}
Algorithms and Data Structures on C
整列データの受け渡し
• 整列するためのデータ
• 任意のポインタであるvoid*の配列
• これは、void**と表すことができる
• 実際に並べ替えるデータ
• PDのポインタ配列であるPD**など
• PD**からvoid**への変換が必要となる
• この変換は暗黙には行われない
• そのための工夫
•
•
•
•
sortXXXXX(void*,int,…)のようにvoid*で受ける
void*は任意のポインタであるからPD**でも良い
これを受け取った後にvoid**にキャストする
ただし、これによりコンパイラによる型チェックの恩恵にはあずかれなくなる
Algorithms and Data Structures on C
整列データの受け渡し
PD**
PD*
山田
18
PD*
整列関数
void sortXXXXX(void *d0,…){
void **d=(void**)d0;
PD*
PD*
PD*
void**
void*
void*
void*
void*
void*
void*
void*
void*
PD*
森
55
中村
33
PD*
PD*
整列するデータ
関数の中ではvoid*の配列として取り扱う
今井
60
Algorithms and Data Structures on C
バブルソートの計算量
• 二重ループ構造（①と②）
• ①のループは n－1 回 → O(n－1)
• ②のループは、平均 n/2 回 → O(n/2)
• ③の処理は、nに無関係 → O(1)
• 計算量
• O(n－1)×O(n/2)×O(1)=O(n2) となる
• 安定な整列アルゴリズム
• 「前の要素が大きければ入れ替える」
• 等しい場合は入れ替わらない
• 等しい要素の順番は保存される
• データの交換回数が多い
• ループ②の中で、データが上位に上がるとデータの交換が起こる
• 処理効率の低下
Algorithms and Data Structures on C
SortTest.java
/***
*** 整列のテスト
***/
#include "Sort.h"
#include "PD.h"
// 比較関数
int comp(void *d1,void *d2){
PD *pd1=(PD*)d1;
PD *pd2=(PD*)d2;
return pd1->age-pd2->age;
}
// 表示
void print(PD **d,int s){
for(int i=0;i<s;i++)
printf("%s(%d)-",d[i]->name,d[i]->age);
printf("¥n");
}
続く
Algorithms and Data Structures on C
SortTest.java
// メイン
int main(int argc,char **argv){
PD *data[6];
data[0]=makePD("山田",18);
data[1]=makePD("森",55);
data[2]=makePD("中村",33);
data[3]=makePD("石田",27);
data[4]=makePD("東村",31);
data[5]=makePD("牧",12);
print(data,6);
// 並べ換える前の表示
sortBubble(data,6,comp); // 並べ換え
print(data,6);
// 並べ換えた後の表示
}
Algorithms and Data Structures on C
実行結果
$ ./TestSort
山田(18)-森(55)-中村(33)-石田(27)-東村(31)-牧(12)牧(12)-山田(18)-石田(27)-東村(31)-中村(33)-森(55)-
Algorithms and Data Structures on C
選択ソート
• 原理
• 整列されていない部分から最小の要素を選び、それを先頭に移動する
•
•
•
•
•
a[0]～a[n-1]の最小の要素をa[0]と交換
a[1]～a[n-1]の最小の要素をa[1]と交換
a[2]～a[n-1]の最小の要素をa[2]と交換
・・・
a[n-2]～a[n-1]の最小の要素をa[n-2]と交換
整列済み
未整列
最小を探す
整列済み
先頭に持ってくる（交換）
Algorithms and Data Structures on C
Sort.cc（続き）
// 選択ソート
void sortSelection(void *d0,int s,int (*comp)(void*,void*)){
void **d=(void**)d0;
for(int i=0;i<s-1;i++){
int min=i;
for(int j=i+1;j<s;j++){
if(comp(d[j],d[min])<0)
③
②
min=j;
①
}
void *t=d[i];
d[i]=d[min];
④
d[min]=t;
}
}
Algorithms and Data Structures on C
選択ソートの計算量
• 二重ループ構造
•
•
•
•
①のループは n－1 回 → O(n－1)
②のループは、平均 n/2 回 → O(n/2)
③の処理は、nに無関係 → O(1)
④の処理も、nに無関係 → O(1)
• 計算量
• O(n－1)×O(n/2)×O(1) ×O(1)=O(n2) となる
• 非安定な整列アルゴリズム
• 先頭要素との交換時に、同じ値を持つ要素の並びが変化する
• データの交換回数が少ない
• ループ①が1回まわると、交換が1回だけ起こる
• バブルソートより高速
Algorithms and Data Structures on C
挿入ソート
• 原理
• 配列の一部を整列済みにし、残りの要素を１つずつその中の適切な位
置に挿入する
整列前
14 8
3 18 21 4 31 7 11 24 16
先頭要素だけ整列済み
1回ループ後
8 14 3 18 21 4 31 7 11 24 16
整列済みに、8を挿入（比較1回）
2回ループ後
3
8 14 18 21 4 31 7 11 24 16
整列済みに、3を挿入（比較2回）
3回ループ後
3
8 14 18 21 4 31 7 11 24 16
整列済みに、18を挿入（比較1回）
4回ループ後
3
8 14 18 21 4 31 7 11 24 16
整列済みに、21を挿入（比較1回）
5回ループ後
3
4
整列済みに、4を挿入（比較4回）
・
・
・
8 14 18 21 31 7 11 24 16
整列済み
Algorithms and Data Structures on C
InsertionSort.java
// 挿入ソート
void sortInsertion(void *d0,int s,int (*comp)(void*,void*)){
void **d=(void**)d0;
for(int i=1;i<s;i++){
for(int j=i;j>0 && comp(d[j-1],d[j])>0;j--){
void *t=d[j];
d[j]=d[j-1];
②
①
③
d[j-1]=t;
}
}
}
Algorithms and Data Structures on C
挿入ソートの計算量
• 二重ループ構造
• ①のループは n－1 回 → O(n－1)
• ②のループは、平均 n/2 回 → O(n/2)
• ③の処理は、nに無関係 → O(1)
• 計算量
• O(n－1)×O(n/2)×O(1) =O(n2) となる
• 安定な整列アルゴリズム
• 挿入するとき、1つ前の要素が大きければ入れ替える
• 同じの場合は入れ替えないので、同じ要素の順番は保持される
• ほとんど整列済みのデータに有利
• 既に並んでいるデータについては比較と交換が発生しない
• この場合、ループ②は1回もまわらない
• ほとんど整列済みのデータに対しては、ほぼO(n)で整列可能
Algorithms and Data Structures on C
単純な整列アルゴリズムの比較
• 実験用プログラム
• 3つのソートを実行し、以下の情報を測定
• 実行時間
• データの比較回数
• データの交換回数
Sort.ccに変数を作成する（後で）
• 与えるデータ
• データ数を可変（200個～10000個）
• データの分布を可変（ランダム、ほぼ整列済み）
Algorithms and Data Structures on C
比較と交換の回数のカウント（1）
• Sort.ccにカウント用の変数を追加
• 整列前に0に初期化する
• 各アルゴリズムのsortXXXX()関数内で、比較と交換の回数をカウント
/***
*** ソートの実装
***/
#include "Sort.h"
int comp_count;
int exchg_count;
Sort.hの中でextern宣言して
ないので、Sort.ccの中でしか
使えない変数
// 比較回数
// 交換回数
続く
Algorithms and Data Structures on C
比較と交換の回数のカウント（2）
// バブルソート
void sortBubble(void *d0,int s,int (*comp)(void*,void*)){
comp_count=exchg_count=0;
void **d=(void**)d0;
for(int i=0;i<s-1;i++){
for(int j=s-1;j>i;j--){
comp_count++;
if(comp(d[j-1],d[j])>0){
exchg_count++;
void *t=d[j];
d[j]=d[j-1];
d[j-1]=t;
}
}
}
}
続く
Algorithms and Data Structures on C
比較と交換の回数のカウント（３）
// 選択ソート
void sortSelection(void *d0,int s,int (*comp)(void*,void*)){
comp_count=exchg_count=0;
void **d=(void**)d0;
for(int i=0;i<s-1;i++){
int min=i;
for(int j=i+1;j<s;j++){
comp_count++;
if(comp(d[j],d[min])<0)
min=j;
}
exchg_count++;
void *t=d[i];
d[i]=d[min];
d[min]=t;
}
}
続く
Algorithms and Data Structures on C
比較と交換の回数のカウント（４）
// 挿入ソート
void sortInsertion(void *d0,int s,int (*comp)(void*,void*)){
comp_count=exchg_count=0;
void **d=(void**)d0;
for(int i=1;i<s;i++){
for(int j=i;j>0;j--){
comp_count++;
if(comp(d[j-1],d[j])>0){
exchg_count++;
カウントするために、判断
void *t=d[j];
構造を少し変えた
d[j]=d[j-1];
本質的には同じ
d[j-1]=t;
}
else
break;
}
}
}
続く
Algorithms and Data Structures on C
比較と交換の回数のカウント（５）
• 各回数を得るための関数を追加
// 比較回数を得る
int getCompCount(){ return comp_count; }
// 交換回数を得る
int getExchgCount(){ return exchg_count; }
Algorithms and Data Structures on C
比較と交換の回数のカウント（６）
• Sort.hにプロトタイプ宣言を追加
#ifndef __Sort__h
#define __Sort__h
/***
*** 並べ替え用
***/
#include <stdio.h>
#include <stdlib.h>
// プロトタイプ宣言
void sortBubble(void*,int,int(*)(void*,void*));
void sortSelection(void*,int,int(*)(void*,void*));
void sortInsertion(void*,int,int(*)(void*,void*));
int getCompCount();
int getExchgCount();
#endif // __Sort__h
Algorithms and Data Structures on C
テスト用TestSort2.cc
/***
*** 並べ換えのテスト2
***/
#include "Sort.h"
#include "PD.h"
#include <string.h>
#include <time.h>
// 比較関数
// 名前で比較し、同じなら年齢で比較する
int compare(void *d1,void *d2){
PD *pd1=(PD*)d1;
PD *pd2=(PD*)d2;
int c=strcmp(pd1->name,pd2->name);
if(c==0) return pd1->age-pd2->age;
return c;
}
続く
Algorithms and Data Structures on C
テスト用TestSort2.cc
// メイン
int main(int argc,char **argv){
int loop=1;
double rand_rate=1.0;
// 引数処理
if(argc!=3 && argc!=4 && argc!=5){
fprintf(stderr,
"Usage: %s type max [rand=1.0] [loop=1]",argv[0]);
exit(1);
}
int type=atoi(argv[1]);
int max=atoi(argv[2]);
if(argc>=4) rand_rate=atof(argv[3]);
if(argc>=5) loop=atoi(argv[4]);
PD **data=(PD**)malloc(max*sizeof(PD*));
srand(time(NULL));
続く
Algorithms and Data Structures on C
テスト用TestSort2.cc
// 実験
double lap=0;
double comp_count=0;
double exchg_count=0;
for(int i=0;i<loop;i++){
// シリアルデータの準備
char s[]={ 'a','a','a','a','a',0 };
for(int i=0;i<max;i++){
int a=rand()%60+10;
// 年齢はランダム
data[i]=makePD(s,a);
for(int j=4;j>=0;j--){
if(s[j]<'z'){
s[j]++;
break;
}
s[j]='a';
}
}
続く
Algorithms and Data Structures on C
テスト用TestSort2.cc
// シャッフル
int c=(int)(max*rand_rate);
for(int i=0;i<c;i++){
int r1=(int)(((double)rand()/RAND_MAX)*max);
int r2=(int)(((double)rand()/RAND_MAX)*max);
PD *t=data[r1];
data[r1]=data[r2];
data[r2]=t;
}
続く
Algorithms and Data Structures on C
テスト用TestSort2.cc
// 並べ替え
clock_t t1=clock();
switch(type){
case 0: sortBubble(data,max,compare); break;
case 1: sortSelection(data,max,compare); break;
case 2: sortInsertion(data,max,compare); break;
}
clock_t t2=clock();
lap+=((double)t2-t1)/CLOCKS_PER_SEC;
comp_count+=getCompCount();
exchg_count+=getExchgCount();
}
printf("%f %f %f ",lap*1000,comp_count/loop,exchg_count/loop);
}
Algorithms and Data Structures on C
データ数と並べ替え時間
1000000
b-lap
100000
s-lap
i-lap
10000
n^2/100
1000
100
10
1
100
1000
10000
Algorithms and Data Structures on C
データ数と比較回数
100000000
10000000
1000000
100000
b-comp
s-comp
10000
i-cmop
1000
100
1000
10000
Algorithms and Data Structures on C
データ数と交換回数
100000000
b-exchg
10000000
s-exchg
1000000
i-exchg
100000
10000
1000
100
100
1000
10000
Algorithms and Data Structures on C
比較回数・交換回数
• 選択ソートはデータの交換回数が少ない
• 挿入ソートはデータの比較回数が少ない
num
b-lap
b-comp
b-exchg
s-lap
s-comp s-exchg i-lap
i-cmop
9078.65
i-exchg
200
15
19900
8882.7
0
19900
199
0
8882.7
300
15
44850
20223.45
15
44850
299
0
500
46
124750
56795.45
31
124750
499
15 57289.95 56795.45
700
32
244650
110607.8
62
244650
699
31 111303.3 110607.8
1000
171
499500
223885.2
140
499500
999
78 224880.3 223885.2
2000
703
1999000
907912.4
546
1999000
1999
265 904197.5 902201.7
3000 1593
4498500
2035679
1203
4498500
2999
546 2032459 2029464
5000 4452 12497500
5659682
3296 12497500
4999 1453 5642875 5637880
7000 8751 24496500 11069605
6422 24496500
6999 2859 11110157 11103161
10000 18300 49995000 22607757
13332 49995000
9999 5828 22507657 22497662
20519 20223.45
Algorithms and Data Structures on C
ほぼ揃ったデータの整列
100000
ランダム
ほぼ揃っている
10000
1000
b-lap
s-lap
i-lap
100
0
0.2
0.4
0.6
0.8
1
Algorithms and Data Structures on C
ほぼそろったデータに対する
比較回数・交換回数
• データ数は10000に固定
• 挿入ソートは、比較回数が極端に少ない
• それに応じて、交換回数も少なくなる
rand b-lap
b-comp
b-exchg
s-lap
s-comp s-exchg i-lap
i-cmop
i-exchg
0.01 11453 49995000
657297 8736 49995000
9999
171
650484
640485
0.05 12141 49995000
3085772 9079 49995000
9999
749
3052251
3042252
0.1 12814 49995000
5715629 9623 49995000
9999 1499
5780676
5770677
0.2 14172 49995000 10128342 10500 49995000
9999 2718 10134480 10124482
0.5 16875 49995000 17734631 12306 49995000
9999 4577 17701200 17691204
1 18301 49995000 22551811 13383 49995000
9999 5891 22645149 22635154
ランダム率
Algorithms and Data Structures on C
課題150105
• この回に実装した整列プログラムは、void*の配列を整列するので、通常の
intの配列は整列できない。
• そこで、バブルソートでintの配列を整列する関数
sortBubble(int*,int,int(*)(int,int))を実装せよ。
• 実装は、Sort.hにプロトタイプ宣言し、Sort.ccにコードを追加すること。
• 降順に整列する比較関数を書き、10個のランダムな整数を降順に並べ替
えるテストプログラムTestSort3.ccも示せ。
• 提出方法：
• レポートはワードで作成し、メールに添付すること。
• ファイル名は scXXXXXX-al150105.docx とすること。レポートには学籍番号と氏名
を必ず書くこと。
• メールで渕田まで送付すること。
• 提出先：[email protected]
• メールタイトル：”アルゴリズム課題150105”
• メール本文にも学籍番号と氏名を必ず書くこと。
• 期限：2015年1月18日（日）
Algorithms and Data Structures on C
整列アルゴリズムの基礎
終了

Download Report