アルゴリズムとプログラミング (Algorithms and Programming)

Presentation on theme: "アルゴリズムとプログラミング (Algorithms and Programming)"— Presentation transcript:

1 アルゴリズムとプログラミング (Algorithms and Programming)
第８回：多次元配列、ソーティング 多次元配列 行列クラスのサンプルプログラム ソーティングアルゴリズム 選択ソート マージソート クイックソート 講義資料等：

2 ２次元配列(3x3)の宣言(要素がdoubleの場合)：
2次元配列 行列は２次元配列で表すことができる a[ ][ ] (添え字：0,1,2,3.....) 例）3x3行列 ２次元配列(3x3)の宣言(要素がdoubleの場合)： double a[ ][ ] = new double[3][3] ;

3 (各添え字をx,y,z座標と対応させて3次元静電ポテンシャルなどを表現)
多次元配列 ３次元配列：　　a[ ][ ][ ]　 (各添え字をx,y,z座標と対応させて3次元静電ポテンシャルなどを表現) ４次元配列：　　a[ ][ ][ ][ ]

4 2x2行列を表現するクラス定義の例） class Max2 { // 2x2配列クラス(配列要素はdouble)
private double m[][]; // フィールドとして配列参照変数を宣言 //コンストラクタ (配列の実体を生成し、初期値を与える) Max2(double a00,double a01,double a10, double a11 ){ m = new double[2][2] ; //newで配列の実体を生成する m[0][0] = a00; m[0][1] = a01; m[1][0] = a10; m[1][1] = a11; } void add( Max2 max ) { // 引数の配列を自身に加算 m[0][0] += max.m[0][0]; m[0][1] += max.m[0][1]; m[1][0] += max.m[1][0]; m[1][1] += max.m[1][1]; void printMatrix() { System.out.print( "a00=" + m[0][0] ); System.out.println( " a01=" + m[0][1] ); System.out.print( "a10=" + m[1][0] ); System.out.println( " a11=" + m[1][1] );

5 a00=1.0 a01=2.0 a10=3.0 a11=4.0 SampleMax2.java 続き class SampleMax2 {
public static void main(String[] args) { Max2 m1 = new Max2(1,0,3,0); Max2 m2 = new Max2(0,2,0,4); m1.add(m2); //add()の定義からm1=m1+m2と等価 m1.printMatrix(); // 行列要素の表示 } 実行結果 a00=1.0 a01=2.0 a10=3.0 a11=4.0

6 多次元配列の宣言（長さが不均一な場合） m[0] m[0][0] m[0][1] m[1] m[1][0] m[1][1] m[1][2]
数値計算では使わないが文字列を配列に格納する際に多用する double m[][] = new double[3][] ; m[0] = new double[2]; m[1] = new double[4]; m[2] = new double[3]; 空白のまま m[0] m[0][0] m[0][1] m[1] m[1][0] m[1][1] m[1][2] m[1][3] m[2] m[2][0] m[2][1] m[2][2]

7 多次元配列の初期化 n[0] 3 2 n[1] 1 8 9 -1 n[2] 6 4 int n[][] = { { 3, 2 },
初期化要素を直接指定する場合 int n[][] = { { 3, 2 }, { 1, 8, 9, -1 }, { 0, 6, 4 } }; n[ ][0] n[ ][1] n[ ][2] n[ ][3] n[0] 3 2 n[1] 1 8 9 -1 n[2] 6 4

8 配列長を知る(.length) n.length 3になる．new int[3][]に対応
例） int n[][] = { { 3, 2 }, { 1, 8, 9, -1 }, { 0, 6, 4, 1, 7 } }; それぞれの次元の配列長は下記のようになる n.length 　 3になる．new int[3][]に対応 n[0].length 2になる． new int[2]に対応 n[1].length 4になる． new int[4]に対応 n[2].length 5になる． new int[5]に対応

9 ソーティングアルゴリズム 選択ソート マージソート クイックソート バブルソート ヒープソート

10 選択ソートの考え方 問題： 与えられた配列の要素を、大きい順に並べ替えなさい
方針(例)： 配列の先頭から、一つ一つ順番に値を比べて、大きい値と出会ったら入れ替える 配列添え字i a[0] work 入れ替え用 一時記憶変数 a[1] 配列添え字j a[2] a[3] a[4]

11 選択ソートのアルゴリズム 1. i = 0からはじめる．
2. A[i+1]からA[N-1]までの要素A[j]と、A[i]の大きさを比較して、 3. もし、A[i]よりも大きい要素に出会ったら、 4. A[i]とA[j]を入れ替える． 5. i = i + 1とする． 6. i == N - 1ならば処理を終了する．そうでなければ，2へ戻る． 計算量 N×N = N2 のオーダーの計算量が必要となる．

12 SampleAPP0701.java class SampleAPP0701 { public static void main(String[] args) { int array[] = {20,100,-40,500,70};//与えられた配列 int work; //入れ替え用の一時メモリ for(int i = 0; i < array.length - 1; i++ ){ for(int j = ; j < ; j++ ){ if( array[i] < array[j] ) { //大きな数字と出会ったら work = array[ ]; //入れ替える array[ ] = array[ ]; array[ ] = work; } } //以下は結果の表示 for(int i=0; i < array.length; i++ ){ System.out.println( "array[" + i + "]= " + array[i] );

13 マージソートの考え方 ソーティングされた複数のデータをまとめて、 １つのソーティングしたデータにすることを マージ（merge,併合）と呼ぶ + ＝ ２つのデータグループが既にソーティング されている場合、これらをまとめて順番に 並べる変えるのは、ばらばらなデータを並 べ直すのよりはるかに少ない手数で可能。

14 マージの手順 + 小さい順（昇順）の場合なら、 常に一番小さい先頭データ同士のみを 比較すれば十分である

15 マージの手順 + 小さい順（昇順）の場合なら、 常に一番小さい先頭データ同士のみを 比較すれば十分である 比較の上、小さい方を持ってくる

16 マージの手順 + 小さい順（昇順）の場合なら、 常に一番小さい先頭データ同士のみを 比較すれば十分である

17 マージの手順 + 小さい順（昇順）の場合なら、 常に一番小さい先頭データ同士のみを 比較すれば十分である

18 マージの手順 + 小さい順（昇順）の場合なら、 常に一番小さい先頭データ同士のみを 比較すれば十分である

19 マージの手順 + 小さい順（昇順）の場合なら、 常に一番小さい先頭データ同士のみを 比較すれば十分である

20 マージの手順 + 小さい順（昇順）の場合なら、 常に一番小さい先頭データ同士のみを 比較すれば十分である

21 マージの手順 + 小さい順（昇順）の場合なら、 常に一番小さい先頭データ同士のみを 比較すれば十分である

22 マージの手順 + 小さい順（昇順）の場合なら、 常に一番小さい先頭データ同士のみを 比較すれば十分である

23 マージの手順 + 小さい順（昇順）の場合なら、 常に一番小さい先頭データ同士のみを 比較すれば十分である

24 マージの手順 + 小さい順（昇順）の場合なら、 常に一番小さい先頭データ同士のみを 比較すれば十分である

25 マージの手順 + 小さい順（昇順）の場合なら、 常に一番小さい先頭データ同士のみを 比較すれば十分である

26 マージの手順 + 小さい順（昇順）の場合なら、 常に一番小さい先頭データ同士のみを 比較すれば十分である

27 マージソートの考え方（例） ８つの要素を４つづつに分解 それぞれ

28 先の手順を、分解されたグループに繰り返し適用する
マージソートの考え方（例） 先の手順を、分解されたグループに繰り返し適用する マージの 繰り返し

29 マージソートの計算量 要素数N log2N段 各段でN回のオーダー の比較と代入 の操作が必要 ∴N・log2Nのオーダー

30 まとめ 多次元配列 ソーティング(並べ替え)アルゴリズム 宣言と初期化 配列の長さ知る方法 行列クラスのサンプルプログラム 選択ソート
マージソート クイックソート