データ構造

Transcription

1 アルゴリズム及び実習 3 馬青 1

2 バブルソート 考え方 : 隣接する二つのデータを比較し データの大小関係が逆のとき 二つのデータの入れ替えを行って整列を行う方法である 2

3 バブルソートの手順 配列 a[0],a[1],,a[n-1] をソートする場合 ステップ 1: 配列 a[0] と a[1],a[1] と a[2],,a[n-2] と a[n-1] と となり同士を比較 ( 大小が逆であれば ) 交換していき その結果 最大値が a[n-1] に入る ステップ 2: a[0] と a[1],a[1] と a[2],, a[n-3] と a[n-2] と 比較 ( 大小が逆であれば ) 交換していき その結果 (2 番目の ) 最大値が a[n-2] に入る ステップ n-1: a[0] と a[1] を比較 ( 大小が逆であれば ) 交換し その結果 (n-1 番目の ) 最大値が a[1] に入る 以上で ソート済みの配列が得られる 3

4 例 :(23, 18, 25, 20, 10) を ステップ 1 ソートする (1/4) 1 件目から 5 件目までのデータの最大値を 5 件目に移動する 逆順のため交換 正順のためそのまま 逆順のため交換 逆順のため交換

5 例 (2/4) ステップ 2 1 件目から 4 件目までのデータの最大値を 4 件目に移動する 正順のためそのまま 逆順のため交換 逆順のため交換

6 例 (3/4) ステップ 3 1 件目から 3 件目までのデータの最大値を 3 件目に移動する 正順のためそのまま 逆順のため交換

7 例 (4/4) ステップ 4 1 件目から 3 件目までのデータの最大値を 3 件目に移動する 正順のためそのまま

8 Questions 1.1 件目からn 件目までのデータの最大値をn 件目に移動させるために 何回の比較が必要か? 交換回数は? 2. 上記操作でソートは完了か? 3. 上記操作を1ステップと数えると n 個のデータのソートには何ステップ必要か? 4. n 個のデータのソートには何回の比較が必要か? 5. 各ステップ内の ( 比較 交換すべき ) 処理対象データの個数は同じか? なぜ? 8

9 大まかなループ ( 繰り返し ) 化 各ステップに対応するループ ステップ内で最大値を右に移動させるループ 9

10 最大値を右に移動させるループ n 個のデータa[0],,a[n-1] の場合繰り返しに変数 iを用いる 1. i=? から? について以下を繰り返す 1.1? であれば a[?] とa[?] を交換する 10

11 演習問題 次のバブルソートのアルゴリズム ( 基本版 ) を完成させなさい ただし 中の 最大値を右に移動させるループ は その対象データの範囲はステップごとに縮小していくことに注意 11

12 バブルソートアルゴリズム ( 基本版 ) 入力 : ソートされていない配列 a[0],...,a[n-1] 出力 : ソートされた配列 a[0],...,a[n-1] 補助 :i: ステップ数, j: 配列の要素番号 各ステップに対応するループ 1. i=? から? について 次の操作を繰り返す 1.1 { 比較 交換 } j=? から? について 次の処理を繰り返す もし? であれば? と? を交換する ステップ内の最大値を右に移動させるループ 12

13 バブルソート ( 基本版 ) の問題点 整列済みのデータも最初から最後まで比較が行われる 例えば 1,3,5,8,10 のようなデータのソート 13

14 バブルソートの改良 途中のステップで交換が一度も起こらなかったら処理を打ち切る ( 改良 1) 改良 1 に加え さらに 可能な場合はステップごとの確定データが 2 個以上する ( 言い換えると 途中のステップをとばす ) ( 改良 2) すなわち ステップ内に交換がなければ終了 あっても可能な場合は複数のデータを確定 シェーカーソート 14

15 改良 1 ステップごとに交換あったか / なかったかについての変数 ( フラッグ ) を導入すると簡単にできる 15

16 Question アルゴリズム ( 基本版 ) をどう直せばアルゴリズム ( 改良版 1) になるか? 16

17 改良 2 必要に応じて各ステップにおいて 複数個のデータを一括してソート済みとして確定する方法 ( 改良 2 は実質的に改良 1 を含む ) 17

18 考え方その 1 例 :(10, 40, 30, 50, 60) を昇順に ソートする (1/2) ステップ1 a[0] a[1] a[2] a[3] a[4] 交換があった位置 (s) を覚えておく a[2] 以降は交換ないので a[2]-a[4] をソート済みとして確定 18

19 考え方その 1 例 :(10, 40, 30, 50, 60) を昇順に ソートする (2/2) ステップ 2 a[0] a[1] a[2] a[3] a[4] 交換がないので ソート済みとして確定 ソート終了 19

20 Question アルゴリズム ( 基本版 ) をどう直せばアルゴリズム ( 改良版 2) になるか? 20

21 プログラミングのポイント 最後に交換のあったデータの位置 s を次のステップの右の範囲として用いるとよい つまり 以下の構造を用いるとよい high=n-1; while(high>0){ } // 各ステップに対応 s=0; for(j=0; j<high; j++){ // ステップ内の比較交換に対応交換あればs=j; // 交換ある度にsが更新 } high=s; 21

22 考え方その 1 つまり アルゴリズム ( 改良版 2) は バブルソートアルゴリズム ( 基本版 ) を 前のスライドの プログラミングのポイント で修正するとよい 22

23 考え方その 2 例 :(10, 40, 30, 50, 60) を昇順に ソートする (1/2) ステップ1 a[0] a[1] a[2] a[3] a[4] 交換があった位置 (s) を覚えておく a[2] 以降は交換ないので a[2]-a[4] をソート済みとして確定 23

24 考え方その 2 例 :(10, 40, 30, 50, 60) を昇順に n-1-s 個 (3 個 ) のデータが確定したので バブルソートで考えると n-s-1 ステップが完成したと見なしてよい したがって 次はステップ n-s( ステップ 4) にとばしてよい ステップ 4 ソートする (2/2) a[0] a[1] a[2] a[3] a[4] a[0] 以降交換ないので ソート済みとして確定 ソート終了 24

25 プログラミングのポイント (1/2) バブルソートアルゴリズム ( 基本版 ) に対し j に関する for 文 ( ステップ内の処理 ) はこのままで i に関する for 文 ( ステップに対応 ) は i をとばせるようにすればよい 前の例では i=1 の次は i=4 となる そのため for 文を while 文に直した方が便利かもしれない 25

26 プログラミングのポイント (2/2) i=1; while(i<=n-1){ s=0; for(j=0; ){ 交換あればs=j; } i=n-s; } // これは基本版のまま 26

27 考え方その 2 つまり アルゴリズム ( 改良版 2) は バブルソートアルゴリズム ( 基本版 ) を 前のスライドの プログラミングのポイント で修正するとよい 27

28 改良 3 シェーカーソート シェーカーソートは 前方から後方への比較と後方から前方への比較を交互に実行することによって 後方だけでなく前方の整列ずみの配列を比較せずに済む ( つまり 改良 2 の双方向版と思えばよい ) 28

29 例 :(10,16,18,21,17,23,25,30) を 昇順にソートする (1/3) ステップ 1: 左から右に向かってバブルソート a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7]

30 例 (2/3) a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] 上の図をみればわかるが a[4] 以降はデータ交換なく すなわち ソートずみとして確定する 30

31 例 (3/3) ステップ 2:a[0]-a[3] に対し 右から左に向かってバブルソート a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[2] 以前 ( つまりa[2]-a[0] まで ) はデータ交換がなく すなわち a[0]-a[2] はソート済みとして確定する 残りのデータは1 個しかないので ソート終了 ( データが2 個以上あれば ステップ3として左から右に向かってバブルソート ) 31

32 Question 上記例を改良 2 でソートすると 何ステップ必要か? 32

33 シェーカーソートアルゴリズム 入力 : ソートされていない配列 a[0],...,a[n-1] 出力 : ソートされた配列 a[0],...,a[n-1] 補助 :i, s, low, high 1. low=0, high=n-1, s=0{ 入れ替えはどこまであった } 2. high>low が成立している間 次の操作を繰り返す i=low から high-1 についての処理 ( 左 右 ) high=s i=high から low+1 についての処理 ( 右 左 ) low=s 33

34 改良版の計算量について バブルソートに比べ データが整列済みの部分が多い場合に比較回数を減らすことが可能である 一方 データの比較回数を減らすことはできるが データの交換の回数を減らすことはできない したがって データの入れ替えに時間がかかる場合は シェーカソートなどの改良手法でも時間をあまり短縮できない 最大 ( 最悪 ) 計算量は同じくO(n 2 ) である 34

35 Question 選択ソートとバブルソートの共通点と相違点を列挙しなさい どっちが速そう? 35

36 第 3 回実習課題 (1/3) 1. バブルソートアルゴリズム ( 基本版 ) を実行する関数 void BubbleSort(int n, int a[]) を作成し その動作を確認できるプログラム (ex03-bsort.c) を作成しなさい ただし n はデータの個数 a[] はデータ配列である 2. 比較回数と交換回数をグローバル変数で宣言し ( 後ろのページを参照 ) void BubbleSort(int n, int a[]) の中で比較回数と交換回数をカウントするように関数を改良する 求めた比較回数を main() で出力するように動作確認プログラム ( ex03-bsortc.c ) を改良しなさい 36

37 第 3 回実習課題 (2/3) 3. アルゴリズム ( 改良版 1) を実行する関数 void BubbleSortI(int n, int a[]) を作成し その動作を確認できるプログラム (ex03-bsorti.c) を作成しなさい ただし 2. と同様 比較と交換の回数が出力できるようにすること 4. アルゴリズム ( 改良版 2) を実行する関数 void BubbleSortII(int n, int a[]) を作成し その動作を確認できるプログラム (ex03-bsortii.c) を作成しなさい ただし 2. と同様 比較と交換の回数が出力できるようにすること 37

38 第 3 回実習課題 (3/3) 5. シェーカーソートアルゴリズムを実行する関数 void ShakerSort(int n, int a[]) を作成し その動作を確認できるプログラム (ex03-shakersort.c) を作成しなさい ただし 2. と同様 比較と交換の回数が出力できるようにすること 発展課題 38

39 グローバル変数の宣言方法 int CNT1, CNT2; void BubbleSort(int a[], int n) { } main() { } 39

40 ex03-bsorti.c の実行例./a.out Input the data (end with Ctrl-D) (Ctrl-D) Sorted data Number of Comparing and Exchanging: 6 6./a.out Input the data (end with Ctrl-D) (Ctrl-D) Sorted data Number of Comparing and Exchanging: