Sort

プログラミング論 II
2008年10月09日
バブルソート,バケツソート,クイックソート
http://www.ns.kogakuin.ac.jp/~ct13140/Prog.2008/
F-1
1
概要
• バブルソート,バケツソート
– 簡単
• クイックソート
– 難しいが重要.
F-2
2
ソート SORT
数字を降順/昇順に並び替える
アルゴリズム.
バブルソート,バケツソート,クイックソート
F-3
3
ソート
• 数を並び替える.
4,8,0,5,7
↓ソート
0,4,5,7,8
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