バブルソート，バケツソート，クイックソート

Presentation on theme: "バブルソート，バケツソート，クイックソート"— Presentation transcript:

1 バブルソート，バケツソート，クイックソート
プログラミング論 バブルソート，バケツソート，クイックソート

2 概要 バブルソート，バケツソート 簡単 クイックソート 難しいが重要．

3 数字を降順/昇順に並び替える アルゴリズム． バブルソート，バケツソート，クイックソート
ソート SORT 数字を降順/昇順に並び替える アルゴリズム． バブルソート，バケツソート，クイックソート

4 ソート 数を並び替える． ４，８，０，５，７ ↓ソート ０，４，５，７，８

5 ソート 例 int a[10] に10個の整数が格納されているとする． これを小さい順に並び替えて表示する．

6 ソートアルゴリズム バブルソート，バケツソート，クイックソートを紹介する． 以下，数値を昇順に並び替えるとする．
降順への並び替えも基本は同じ．

7 バブルソート 「隣接する2要素の大小を比較し，正しくない状態だったらその2要素を交換する」ことを繰り返す．
O(n2)であり，一般には遅いソートアルゴリズムと認識されている． 実装(プログラムの作成)はとても楽 7

8 バブルソートの概要 ソート結果はa[0]≦a[1]のはずである． 同様に a[1]≦a[2]のはず，a[2]≦a[3]のはず，
「a[i]≦a[i+1]」が成り立つはず． 8

9 バブルソートの概要 「もし，a[i]>a[i+1]であったら，この2個を交換する」
注意：配列長が10なら， iは0～9では無くて，iは0～8． i=9の時，a[9]とa[10]の処理になる． 上記「『もし逆なら交換する』を全てのiについて行う」を何回も行うと，ソートができる． 9

10 バブルソートの例 「9,3,5,2」をソートする． 9 3 5 2 比較 順序が逆なので，交換する． 3 9 5 2 10

11 バブルソートの例 「9,3,5,2」をソートする． 3 9 5 2 3 5 9 2 3 5 2 9 「調査＆交換」を 左から右に向かって
繰り返す． これ1回を「走査」と 呼ぶこととする． 比較＆交換する． 3 5 9 2 比較＆交換する． 3 5 2 9 ←初期状態より，ソートが進んだ． これで，「a[i]とa[i+1]を比較し，逆なら交換する」 を左から右まで「全てのa[i]とa[i+1]の組」に行った． 11

12 バブルソートの例 「9,3,5,2」をソートする． 3 5 2 9 3 5 2 9 3 2 5 9 3 2 5 9 もう1回，左から右に
「調査＆交換」繰り返した． 3 5 2 9 比較＆交換しない． 3 5 2 9 比較＆交換する． 3 2 5 9 比較＆交換しない. 3 2 5 9 12

13 バブルソートの例 「9,3,5,2」をソートする． ←ソート完了 3 2 5 9 2 3 5 9 2 3 5 9 2 3 5 9
もう1回，左から右に 「調査＆交換」繰り返した． 3 2 5 9 比較＆交換する． 2 3 5 9 ←ソート完了 比較＆交換しない． 2 3 5 9 比較＆交換しない. 2 3 5 9 13

14 バブルソート 「『a[i]とa[i+1]を比較して交換』を 左から右に繰り返す」 ことを繰り返せば，ソートが完了する．
さて，何回繰り返せば完了するかを考える． 14

15 バブルソートの比較回数 「比較＆交換」を左から右に1回走査する． すると，必ず最大値が一番右に移動する．よって，一番右は決定！
9 3 5 2 「比較＆交換」を左から右に1回走査する． すると，必ず最大値が一番右に移動する．よって，一番右は決定！ それ以外は，まだ決定していない． 3 9 5 2 3 5 9 2 3 5 2 9 15

16 バブルソートの比較回数 「比較＆交換」を左から右．2走査目． すると，右の2個が決定する． それ以外は，まだ完了していない． 3 5 2 9
実は，3回目の「比較＆交換」は不要 16

17 バブルソートの比較回数 「比較＆交換」を左から右．3走査目． すると，右の3個が決定する． 実は，一番左も決定している． よってこれで終了．
2 5 9 「比較＆交換」を左から右．3走査目． すると，右の3個が決定する． 実は，一番左も決定している． よってこれで終了． 2 3 5 9 3 2 5 9 3 2 5 9 実は，2,3回目の「比較＆交換」は不要 17

18 バブルソートの比較回数 a[100](a[0]～a[99])のバブルソートの例 1走査目．以下が必要．
a[0]とa[1]の比較，a[1]とa[2]の比較, (略) a[98]とa[99]の比較． よって，99回比較する. 注意：100回ではない． 18

19 バブルソートの比較回数 2走査目．以下が必要． a[0]とa[1]の比較，a[1]とa[2]の比較, (略) a[97]とa[98]の比較．
よって，98回比較する. 1走査目より1回減っている． 最後の1個は既に決定しているので． 19

20 バブルソートの比較回数 3走査目．以下が必要． a[0]とa[1]の比較，a[1]とa[2]の比較, (略) a[96]とa[97]の比較．
よって，97回比較する. 2走査目よりさらに1回減っている． 最後の2個は既に決定しているので． 20

21 バブルソートの比較回数 n走査目．以下が必要． a[0]とa[1]の比較，a[1]とa[2]の比較, (略)
a[99-n]とa[100-n]の比較． よって，100-n回比較する. 最後のn-1個は既に決定しているので． 21

22 バブルソートの比較回数 99走査目．以下が必要． a[0]とa[1]の比較． よって，1回比較する. 右の98個は既に決定しているので．
22

23 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; } 23

24 バケツソート O(n)でソートできるアルゴリズム． 最速のアルゴリズムと言えるが， 大量のメモリが必要，
データの範囲(最小値，最大値)が既知であることが必要． 値の範囲が大きいほど大量のメモリが必要． 同じ値が2個以上あるとやりづらい． 浮動小数点には使いづらい． 24

25 バケツソートの例 a[5]をソートする．各値は，0～9の整数であることが分かっているとする． 以下のデータをソートする例を考える． 9 3
2 25

26 バケツソートの例 値の範囲が0～9の10種類なので， 「バケツ0」～「バケツ9」の 10個のバケツを用意する． 9 3 5 2 バケツの中
バケツ 0 空 バケツ 1 空 a[0] a[1] a[2] a[3] a[4] バケツ 2 空 バケツ 3 空 9 3 5 2 バケツ 4 空 バケツ 5 空 バケツ 6 空 バケツ 7 空 バケツ 8 空 バケツ 9 空 26

27 バケツソートの例 9 3 5 2 バケツの中 バケツ 0 空 バケツ 1 空 バケツ 2 空 バケツ 3 空 バケツ 4 空 バケツ 5 空
a[0] a[1] a[2] a[3] a[4] バケツ 2 空 バケツ 3 空 9 3 5 2 バケツ 4 空 バケツ 5 空 バケツ 6 空 バケツ 7 空 a[0]に着目． 値は"9"なので， バケツ9に入れる． バケツ 8 空 バケツ 9 1個 27

28 バケツソートの例 9 3 5 2 バケツの中 バケツ 0 空 バケツ 1 空 バケツ 2 空 バケツ 3 1個 バケツ 4 空 バケツ 5
a[0] a[1] a[2] a[3] a[4] バケツ 2 空 バケツ 3 1個 9 3 5 2 バケツ 4 空 バケツ 5 空 バケツ 6 空 バケツ 7 空 a[1]に着目． 値は"3"なので， バケツ3に入れる． バケツ 8 空 バケツ 9 1個 28

29 バケツソートの例 9 3 5 2 バケツの中 バケツ 0 空 バケツ 1 空 バケツ 2 空 バケツ 3 1個 バケツ 4 空 バケツ 5
a[0] a[1] a[2] a[3] a[4] バケツ 2 空 バケツ 3 1個 9 3 5 2 バケツ 4 空 バケツ 5 1個 バケツ 6 空 バケツ 7 空 a[2]に着目． 値は"5"なので， バケツ5に入れる． バケツ 8 空 バケツ 9 1個 29

30 バケツソートの例 9 3 5 2 バケツの中 バケツ 0 空 バケツ 1 空 バケツ 2 1個 バケツ 3 1個 バケツ 4 空 バケツ 5
a[0] a[1] a[2] a[3] a[4] バケツ 2 1個 バケツ 3 1個 9 3 5 2 バケツ 4 空 バケツ 5 1個 バケツ 6 空 バケツ 7 空 a[3]に着目． 値は"2"なので， バケツ2に入れる． バケツ 8 空 バケツ 9 1個 30

31 バケツソートの例 9 3 5 2 バケツの中 バケツ 0 1個 バケツ 1 空 バケツ 2 1個 バケツ 3 1個 バケツ 4 空
a[0] a[1] a[2] a[3] a[4] バケツ 2 1個 バケツ 3 1個 9 3 5 2 バケツ 4 空 バケツ 5 1個 バケツ 6 空 バケツ 7 空 a[4]に着目． 値は"0"なので， バケツ0に入れる． バケツ 8 空 バケツ 9 1個 31

32 バケツソートの例 各値の登場回数の表が完成した． この表を上から下に読んでいけば ソート終了． 0,2,3,5,9 バケツの中 バケツ 0
1個 バケツ 1 空 バケツ 2 1個 バケツ 3 1個 バケツ 4 空 バケツ 5 1個 バケツ 6 空 バケツ 7 空 バケツ 8 空 バケツ 9 1個 32

33 バケツソート 以下の手順でプログラミング可能 [1]バケツ0～バケツ9を作成する.
　各バケツには，「登場回数」を記録するので，intで長さ10の配列を宣言すればよい． [2]全バケツの値を0個として初期化する． 　バケツの長さ(10)でfor分を使う． [3]全データをそれぞれのバケツに振り分けていく．データの長さ(5)でfor分を使う．

34 バケツソート [4]全バケツに入ったデータを上から読んでいく．バケツの長さ(10)でfor分を使う．
for(i=0; i<10; i++){ for(j=0; j<bucket[i]; j++){ ... }

35 #include <stdio.h>
#define DATA_NUM 5 #define VALUE_MAX 100 void main(){ int data[DATA_NUM], bucket[VALUE_MAX], i, v, cnt, score; 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; } for(i=0; i<DATA_NUM; i++){ score = data[i]; bucket[score] ++; for(i=0; i<bucket[v]; i++){ printf("%d\n“, v); [1]バケツ0～バケツ9を作成する [2]全バケツの値を0個として初期化する [3]全データを それぞれのバケツに振り分けていく [4]全バケツに入ったデータを 上から読んでいく

36 #include <stdio.h>
#define DATA_NUM 5 #define VALUE_MAX 100 void main(){ int data[DATA_NUM], bucket[VALUE_MAX], i, v, cnt, score; 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; } for(i=0; i<DATA_NUM; i++){ score = data[i]; bucket[score] ++; cnt=0; for(i=0; i<bucket[v]; i++){ data[cnt] = v; cnt ++; printf("%d\n", data[i]); [1]バケツ0～バケツ9を作成する [2]全バケツの値を0個として初期化する [3]全データを それぞれのバケツに振り分けていく [4]全バケツに入ったデータを 上から読んでいく

37 バケツソート データの取り得る範囲の数だけバケツが必要． 例えば，多くの場合int型は32bitだが，
データの範囲が2^32通りある場合は，43億個のバケツが必要． バケツ1個が1バイトとしても，4GBの記憶領域が必要． 可変長文字列のソートなど，バケツを用意しようが無い場合は適応不可能． バケツが無限通りになってしまう． 37

38 クイックソート 通常，O(nlog(n))でソート可能なアルゴリズム． かなり高速で，制限も無いため非常によく使われるアルゴリズム．
ただし，不安定なソートアルゴリズムである． つまり，同一の値が2個以上あったとき， それらの順位は保証されない．(どうなるか分からない) 38

39 クイックソート 配列の中から，キーとなる枢軸(pivot)を決定する． 枢軸の決定方法は後述． 枢軸は，データの中間値が好ましい． 39

40 クイックソート 左半分が枢軸未満，右半分が枢軸以上となるようにデータ交換を繰り返す．
具体的には，左端からデータを調査していき枢軸以上の値を探す．右端から枢軸未満の値を探す．そして，この2個を交換する． 左に枢軸以上があってはならない．右も同様． 左からの走査と，右からの走査が出会ったら，走査1回終わり． 必ずしも，左半分のデータの個数と，右半分のデータの個数が等しくない． 40

41 クイックソート 1回捜査をすると，「左半分が枢軸未満，右半分が枢軸以上」となっている． 左グループと右グループに分割し，
それぞれをそれぞれの枢軸で再度走査し， それぞれをまた分割する． 分割グループ内の数値が全部同じになるまで分割を繰り返す．(グループの大きさが1になった場合も，「数値が全部同じ」) 41

42 クイックソートの例 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 42

43 クイックソートの例 2 1 1 4 5 9 3 6 5 3 分割する 2 1 1 4 5 9 3 6 5 3 枢軸2で分割 枢軸5で分割 1
終了 終了 枢軸4で分割 枢軸9で分割 3 3 4 5 6 5 9 3 3 4 5 6 5 9 枢軸6 終了 終了 終了 5 5 6 終了 終了 43

44 枢軸の決定方法 枢軸未満と枢軸以上に分割するため， 片方のグループの要素数が0個となってはならない．
例えば，「異なる数字を左から2個探し，その大きい方を枢軸とする」とすれば，「枢軸未満」「枢軸以上」ともに最低1個存在することになる． 異なる数がなければ(全部同じなら)分割不要． 失敗例 4 5 9 一番左の4を枢軸として採用 枢軸未満 枢軸以上 分割できなかった． 4 5 9 44

45 好ましい枢軸の決定方法 ちょうど，2分割されることが好ましい． そのためには，データの中間値に近い値を枢軸とすると良い．
例えば，ランダムに選んだ3個の中間値を採用． 好ましい例 45

46 好ましい枢軸の決定方法 分割に偏りがあると，計算時間が長くなる． 好ましくない例 46

47 好ましい枢軸の決定方法 はじめからソートされている配列をソートしようとすると，このような現象が発生する． 1 2 3 4 5 6 7
1 2 3 4 5 6 7 枢軸=1 1 2 3 4 5 6 7 枢軸=2 1 2 3 4 5 6 7 枢軸=3 2 3 4 5 6 7 枢軸=4 3 4 5 6 7 4 5 6 7 47

48 クイックソート 「枢軸でグループを分割」という処理を行い，2個のグループを作る． そして，両グループを再度「枢軸で分割」を行う．
そして，再度「枢軸で分割」を行う... 通常，(C言語などでは)再帰により実装する． 48

49 補足 通常のプログラミング言語では，ソートや検索のような基本的な機能は標準で提供されている． ソートの場合 検索では，
C言語では，qsort()関数がある． Java,Ruby,Perlなどにもある．RDBMSにソート機能が用意されている． 検索では， Java,Ruby,Perlなどには，Hashがある． Hashは，O(1)で検索できる手法． 49

50 課題 4個の数字 12,7,1,9をバブルソートで並び変えたとき,各数の推移を記せ.

51 課題 int a[100] に整数が100個入っている．負の数も含まれる． (い) a[0]～a[99] の合計を求めるプログラムを作成せよ
(ろ) a[X]～a[Y] の合計を求めるプログラムを作成せよ． (は) a[X]～a[Y] の合計が最大になるのは，XとYがいくつの場合か求めるプログラムを作成せよ．負の数も含まれるため，範囲が広いほど合計が大きくなるわけではない． オーダーはいくつか？ (に) a[] の中に 0 が何個あるか数えるプログラムを作成せよ．