Sort

プログラミング論 II
2008年10月09日
バブルソート，バケツソート，クイックソート
http://www.ns.kogakuin.ac.jp/~ct13140/Prog.2008/
F-1
1
概要
• バブルソート，バケツソート
– 簡単
• クイックソート
– 難しいが重要．
F-2
2
ソート SORT
数字を降順/昇順に並び替える
アルゴリズム．
バブルソート，バケツソート，クイックソート
F-3
3
ソート
• 数を並び替える．
４，８，０，５，７
↓ソート
０，４，５，７，８
F-4
4
ソート
•例
int a[10] に10個の整数が格納されて
いるとする．
これを小さい順に並び替えて表示する．
F-5
5
ソートアルゴリズム
• バブルソート，バケツソート，クイックソート
を紹介する．
• 以下，数値を昇順に並び替えるとする．
– 降順への並び替えも基本は同じ．
F-6
6
バブルソート
• 「隣接する2要素の大小を比較し，正しくな
い状態だったらその2要素を交換する」こと
を繰り返す．
• O(n2)であり，一般には遅いソートアルゴリ
ズムと認識されている．
• 実装(プログラムの作成)はとても楽
F-7
7
バブルソートの概要
• ソート結果はa[0]≦a[1]のはずである．
• 同様に
a[1]≦a[2]のはず，a[2]≦a[3]のはず，
a[3]≦a[4]のはず，...
「a[i]≦a[i+1]」が成り立つはず．
F-8
8
バブルソートの概要
• 「もし，a[i]>a[i+1]であったら，この2個
を交換する」
という操作を全てのa[i],a[i+1]につい
て行う．
– 注意：配列長が10なら，
iは0～9では無くて，iは0～8．
i=9の時，a[9]とa[10]の処理になる．
• 上記「『もし逆なら交換する』を全てのiに
ついて行う」を何回も行うと，ソートができる．
F-9
9
バブルソートの例
• 「9,3,5,2」をソートする．
9
3
5
2
比較
順序が逆なので，交換する．
3
9
5
2
F-10
10
バブルソートの例
• 「9,3,5,2」をソートする．
3
9
5
2
比較＆交換する．
3
5
9
2
「調査＆交換」を
左から右に向かって
繰り返す．
これ1回を「走査」と
呼ぶこととする．
比較＆交換する．
3
5
2
9
←初期状態より，ソートが進んだ．
これで，「a[i]とa[i+1]を比較し，逆なら交換する」
を左から右まで「全てのa[i]とa[i+1]の組」に行った．
F-11
11
バブルソートの例
• 「9,3,5,2」をソートする．
3
5
2
9
もう1回，左から右に
「調査＆交換」繰り返した．
比較＆交換しない．
3
5
2
9
比較＆交換する．
3
2
5
9
比較＆交換しない.
3
2
5
9
F-12
12
バブルソートの例
• 「9,3,5,2」をソートする．
3
2
5
9
もう1回，左から右に
「調査＆交換」繰り返した．
比較＆交換する．
2
3
5
9 ←ソート完了
比較＆交換しない．
2
3
5
9
比較＆交換しない.
3
2
5
9
F-13
13
バブルソート
• 「『a[i]とa[i+1]を比較して交換』を
左から右に繰り返す」
ことを繰り返せば，ソートが完了する．
• さて，何回繰り返せば完了するかを考える．
F-14
14
バブルソートの比較回数
9
3
5
2
3
9
5
2
3
5
9
2
3
5
2
9
• 「比較＆交換」を左か
ら右に1回走査する．
すると，必ず最大値が
一番右に移動する．
よって，一番右は決
定！
• それ以外は，まだ決
定していない．
F-15
15
バブルソートの比較回数
3
5
2
9
3
5
2
9
3
2
5
9
3
2
5
9
• 「比較＆交換」を左か
ら右．2走査目．
すると，右の2個が決
定する．
• それ以外は，まだ完
了していない．
実は，3回目の「比較＆交換」は不要
F-16
16
バブルソートの比較回数
3
2
5
9
2
3
5
9
3
2
5
9
3
2
5
9
• 「比較＆交換」を左か
ら右．3走査目．
すると，右の3個が決
定する．
• 実は，一番左も決定し
ている．
• よってこれで終了．
実は，2,3回目の「比較＆交換」は不要
F-17
17
バブルソートの比較回数
• a[100](a[0]～a[99])のバブルソートの例
• 1走査目．以下が必要．
a[0]とa[1]の比較，a[1]とa[2]の比較,
(略)
a[98]とa[99]の比較．
よって，99回比較する.
– 注意：100回ではない．
F-18
18
バブルソートの比較回数
• 2走査目．以下が必要．
a[0]とa[1]の比較，a[1]とa[2]の比較,
(略)
a[97]とa[98]の比較．
よって，98回比較する.
– 1走査目より1回減っている．
最後の1個は既に決定しているので．
F-19
19
バブルソートの比較回数
• 3走査目．以下が必要．
a[0]とa[1]の比較，a[1]とa[2]の比較,
(略)
a[96]とa[97]の比較．
よって，97回比較する.
– 2走査目よりさらに1回減っている．
最後の2個は既に決定しているので．
F-20
20
バブルソートの比較回数
• n走査目．以下が必要．
a[0]とa[1]の比較，a[1]とa[2]の比較,
(略)
a[99-n]とa[100-n]の比較．
よって，100-n回比較する.
– 最後のn-1個は既に決定しているので．
F-21
21
バブルソートの比較回数
• 99走査目．以下が必要．
a[0]とa[1]の比較．
よって，1回比較する.
– 右の98個は既に決定しているので．
– 左の2個(a[0]とa[1])を決定して終了．
F-22
22
for(i=0; i<SIZE-1; i++){
for(j=0; j<SIZE-1-i; j++){
if( data[j+1] < data[j] ){
tmp = data[j+1];
data[j+1] = data[j];
data[j] = tmp;
}
}
}
F-23
23
バケツソート
• O(n)でソートできるアルゴリズム．
• 最速のアルゴリズムと言えるが，
大量のメモリが必要，
データの範囲(最小値，最大値)が既知で
あることが必要．
– 値の範囲が大きいほど大量のメモリが必要．
– 同じ値が2個以上あるとやりづらい．
– 浮動小数点には使いづらい．
F-24
24
バケツソートの例
• a[5]をソートする．各値は，0～9の整数
であることが分かっているとする．
• 以下のデータをソートする例を考える．
a[0] a[1] a[2] a[3] a[4]
9
3
5
2
0
F-25
25
バケツソートの例
• 値の範囲が0～9の10種類なので，
「バケツ0」～「バケツ9」の
バケツの中
10個のバケツを用意する．バケツ 0
空
a[0] a[1] a[2] a[3] a[4]
9
3
5
2
0
バケツ
バケツ
バケツ
バケツ
バケツ
バケツ
バケツ
バケツ
バケツ
1
2
3
4
5
6
7
8
9
空
空
空
空
空
空
空
空
空
F-26
26
バケツソートの例
a[0] a[1] a[2] a[3] a[4]
9
3
5
2
a[0]に着目．
値は"9"なので，
バケツ9に入れる．
0
バケツ
バケツ
バケツ
バケツ
バケツ
バケツ
バケツ
バケツ
バケツ
バケツ
0
1
2
3
4
5
6
7
8
9
バケツの中
空
空
空
空
空
空
空
空
空
1個
F-27
27
バケツソートの例
a[0] a[1] a[2] a[3] a[4]
9
3
5
2
a[1]に着目．
値は"3"なので，
バケツ3に入れる．
0
バケツ
バケツ
バケツ
バケツ
バケツ
バケツ
バケツ
バケツ
バケツ
バケツ
0
1
2
3
4
5
6
7
8
9
バケツの中
空
空
空
1個
空
空
空
空
空
1個
F-28
28
バケツソートの例
a[0] a[1] a[2] a[3] a[4]
9
3
5
2
a[2]に着目．
値は"5"なので，
バケツ5に入れる．
0
バケツ
バケツ
バケツ
バケツ
バケツ
バケツ
バケツ
バケツ
バケツ
バケツ
0
1
2
3
4
5
6
7
8
9
バケツの中
空
空
空
1個
空
1個
空
空
空
1個
F-29
29
バケツソートの例
a[0] a[1] a[2] a[3] a[4]
9
3
5
2
a[3]に着目．
値は"2"なので，
バケツ2に入れる．
0
バケツ
バケツ
バケツ
バケツ
バケツ
バケツ
バケツ
バケツ
バケツ
バケツ
0
1
2
3
4
5
6
7
8
9
バケツの中
空
空
1個
1個
空
1個
空
空
空
1個
F-30
30
バケツソートの例
a[0] a[1] a[2] a[3] a[4]
9
3
5
2
a[4]に着目．
値は"0"なので，
バケツ0に入れる．
0
バケツ
バケツ
バケツ
バケツ
バケツ
バケツ
バケツ
バケツ
バケツ
バケツ
0
1
2
3
4
5
6
7
8
9
バケツの中
1個
空
1個
1個
空
1個
空
空
空
1個
F-31
31
バケツソートの例
• 各値の登場回数の表が完成した．
• この表を上から下に読んでいけば
ソート終了．
バケツ
バケツ
0,2,3,5,9
バケツ
バケツ
バケツ
バケツ
バケツ
バケツ
バケツ
バケツ
0
1
2
3
4
5
6
7
8
9
バケツの中
1個
空
1個
1個
空
1個
空
空
空
1個
F-32
32
バケツソート
• 以下の手順でプログラミング可能
[1]バケツ0～バケツ9を作成する.
各バケツには，「登場回数」を記録するので，
intで長さ10の配列を宣言すればよい．
[2]全バケツの値を0個として初期化する．
バケツの長さ(10)でfor分を使う．
[3]全データをそれぞれのバケツに振り分け
ていく．データの長さ(5)でfor分を使う．
F-33
バケツソート
[4]全バケツに入ったデータを上から読んで
いく．バケツの長さ(10)でfor分を使う．
1個のバケツに2個以上のデータが入って
いることもあので，各バケツについて「バケ
ツの中の値を長さとするfor文」を使う必
要がある．
for(i=0; i<10; i++){
for(j=0; j<bucket[i]; j++){
...
}
}
F-34
#include <stdio.h>
#define DATA_NUM 5
#define VALUE_MAX 100
[1]バケツ0～バケツ9を作成する
void main(){
int data[DATA_NUM], bucket[VALUE_MAX], i, v, cnt;
data[0]=72; data[1]=46; data[2]=50; data[3]=46; data[4]=22;
for(v=0; v<VALUE_MAX; v++){
bucket[ v ] = 0;
[2]全バケツの値を0個として初期化する
}
for(i=0; i<DATA_NUM; i++){
[3]全データを
bucket[ data[i] ] ++;
それぞれのバケツに振り分けていく
}
cnt=0;
for(v=0; v<VALUE_MAX; v++){
for(i=0; i<bucket[v]; i++){
data[cnt] = v;
[4]全バケツに入ったデータを
cnt ++;
上から読んでいく
}
}
for(i=0; i<DATA_NUM; i++){
printf("%d\n", data[i]);
}
}
F-35
バケツソート
• データの取り得る範囲の数だけバケツが
必要．
– 例えば，多くの場合int型は32bitだが，
データの範囲が2^32通りある場合は，43億
個のバケツが必要．
バケツ1個が1バイトとしても，4GBの記憶領域
が必要．
– 可変長文字列のソートなど，バケツを用意しよ
うが無い場合は適応不可能．
• バケツが無限通りになってしまう．
F-36
36
クイックソート
• 通常，O(nlog(n))でソート可能なアルゴ
リズム．
– 最悪の場合，O(n2)となってしまう．
• かなり高速で，制限も無いため非常によく
使われるアルゴリズム．
– ただし，不安定なソートアルゴリズムである．
– つまり，同一の値が2個以上あったとき，
それらの順位は保証されない．(どうなるか分
からない)
F-37
37
クイックソート
• 配列の中から，キーとなる枢軸(pivot)
を決定する．
– 枢軸の決定方法は後述．
– 枢軸は，データの中間値が好ましい．
F-38
38
クイックソート
• 左半分が枢軸未満，右半分が枢軸以上と
なるようにデータ交換を繰り返す．
– 具体的には，左端からデータを調査していき
枢軸以上の値を探す．右半分から枢軸未満
の値の値を探す．そして，この2個を交換する．
• 左に枢軸以上があってはならない．右も同様．
– 左からの走査と，右からの走査が出会ったら，
走査1回終わり．
• 必ずしも，左半分のデータの個数と，右半分の
データの個数が等しくない．
F-39
39
クイックソート
• 1回捜査をすると，「左半分が枢軸未満，
右半分が枢軸以上」となっている．
左グループと右グループに分割し，
それぞれをそれぞれの枢軸で再度走査し，
それぞれをまた分割する．
分割グループ内の数値が全部同じなるま
で分割を繰り返す．(グループの大きさが1
になった場合も，「数値が全部同じ」)
F-40
40
クイックソートの例
3 1 4 1 5 9 2 6 5 3
枢軸を決める."3"とする．枢軸決定方法は後述．
左から枢軸以上の値を，右から枢軸未満の値を探す．
3 1 4 1 5 9 2 6 5 3
両者を交換する
2 1 4 1 5 9 3 6 5 3
左右からの検索の続きを行う．
2 1 4 1 5 9 3 6 5 3
両者を交換する
2 1 1 4 5 9 3 6 5 3
左右からの検索の続きを行う．
2 1 1 4 5 9 3 6 5 3
出会ってしまったので走査終了．「左半分枢軸未満，
2 1 1 4 5 9 3 6 5 3
右半分枢軸以上」
が達成された． F-41
41
クイックソートの例
2 1 1 4 5 9 3 6 5 3
分割する
2 1 1
枢軸2で分割
1 1 2
1 1
終了
2
終了
3 3
終了
4 5 9 3 6 5 3
枢軸5で分割
4 3 3 9 6 5 5
4 3 3
枢軸4で分割
3 3 4
4
終了
枢軸6
5 5
終了
9 6 5 5
枢軸9で分割
5 6 5 9
5 6 5
6
終了
9
終了
F-42
42
枢軸の決定方法
• 枢軸未満と枢軸以上に分割するため，
片方のグループの要素数が0個となってはな
らない．
– 例えば，「異なる数字を左から2個探し，その大
きい方を枢軸とする」とすれば，「枢軸未満」「枢
軸以上」ともに最低1個存在することになる．
– 異なる数がなければ(全部同じなら)分割不要．
失敗例
枢軸未満
4 5 9
一番左の4を枢軸として採用
枢軸以上
4 5 9
分割できなかった．
F-43
43
好ましい枢軸の決定方法
• ちょうど，2分割されることが好ましい．
– そのためには，データの中間値に近い値を枢軸
とすると良い．
– 例えば，ランダムに選んだ3個の中間値を採用．
好ましい例
F-44
44
好ましい枢軸の決定方法
• 分割に偏りがあると，計算時間が長くなる．
好ましくない例
F-45
45
好ましい枢軸の決定方法
• はじめからソートされている配列をソートしよ
うとすると，このような現象が発生する．
0 1 2 3 4 5 6 7
枢軸=1
0
1 2 3 4 5 6 7
枢軸=2
2 3 4 5 6 7
1
枢軸=3
3 4 5 6 7
2
枢軸=4
3
4 5 6 7
4
5 6 7
F-46
46
クイックソート
• 「枢軸でグループを分割」という処理を行い，
2個のグループを作る．
そして，両グループを再度「枢軸で分割」を
行う．
そして，再度「枢軸で分割」を行う...
• 通常，(C言語などでは)再帰により実装す
る．
F-47
47
補足
• 通常のプログラミング言語では，ソートや
検索のような基本的な機能は標準で提供
されている．
• ソートの場合
– C言語では，qsort()関数がある．
– Java,Ruby,Perlなどにもある．RDBMSに
ソート機能が用意されている．
• 検索では，
– Java,Ruby,Perlなどには，Hashがある．
– Hashは，O(1)で検索できる手法．
48
F-48
課題
• 4個の数字 12,7,1,9をバブルソートで
並び変えたとき,各数の推移を記せ.
F-49
49
課題
• int a[100] に正数が100個入っている．負の数も含
まれる．
– (い) a[0]～a[99] の合計を求めるプログラムを作成せよ
– (ろ) a[X]～a[Y] の合計を求めるプログラムを作成せよ．
– (は) a[X]～a[Y] の合計が最大になるのは，XとYがいくつ
の場合か求めるプログラムを作成せよ．負の数も含まれるた
め，範囲が広いほど合計が大きくなるわけではない．オーダ
ーはいくつか？
– (に) a[] の中に 0 が何個あるか数えるプログラムを作成
せよ．
– (ほ) a[] が全て 0 であるか，否かを数えるプログラムを
作成せよ．
F-50

Download Report