アルゴリズムとプログラミング

アルゴリズムとプログラミング
(Algorithms and Programming)
第８回：多次元配列、ソーティング
•多次元配列
行列クラスのサンプルプログラム
•ソーティングアルゴリズム
選択ソート
マージソート
クイックソート
講義資料等： http://www.pe.titech.ac.jp/~watanabe/lecture/ap/index-j.html
2次元配列
• 行列は２次元配列で表すことができる
a[ ][ ]
例）3x3行列
 a11

 a21
a
 31
a12
a22
a32
a13 

a23 
a33 
(添え字：0,1,2,3.....)
 a[0][0] a[0][1] a[0][2] 


 a[1][0] a[1][1] a[1][2] 
 a[2][0] a[2][1] a[2][2] 


２次元配列(3x3)の宣言(要素がdoubleの場合)：
double a[ ][ ] = new double[3][3] ;
多次元配列
• ３次元配列：
a[ ][ ][ ]
• ４次元配列：
a[ ][ ][ ][ ]
(各添え字をx,y,z座標と対応させて3
次元静電ポテンシャルなどを表現)
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] );
}
}
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
多次元配列の宣言（長さが不均一な場合）
数値計算では使わないが文字列を配列に格納する際に多用する
double
m[0] =
m[1] =
m[2] =
m[][] = new double[3][] ;
new double[2];
new double[4];
空白のまま
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]
多次元配列の初期化
初期化要素を直接指定する場合
int
{
{
{
};
n[][] = {
3, 2 },
1, 8, 9, -1 },
0, 6, 4 }
n[ ][0]
n[ ][1]
n[ ][2]
n[ ][3]
-1
n[0]
3
2
n[1]
1
8
9
n[2]
0
6
4
配列長を知る(.length)
例）
int
{
{
{
};
n[][] = {
3, 2 },
1, 8, 9, -1 },
0, 6, 4, 1, 7 }
それぞれの次元の配列長は下記のようになる
n.length
n[0].length
n[1].length
n[2].length
3になる．new int[3][]に対応
2になる． new int[2]に対応
4になる． new int[4]に対応
5になる． new int[5]に対応
ソーティングアルゴリズム
•選択ソート
•マージソート
•クイックソート
•バブルソート
•ヒープソート
選択ソートの考え方
問題：
与えられた配列の要素を、大きい順に並べ替
えなさい
方針(例)：配列の先頭から、一つ一つ順番に値を比べて、
大きい値と出会ったら入れ替える
a[0]
a[1]
a[2]
a[3]
a[4]
配列添え字i
配列添え字j
work 入れ替え用
一時記憶変数
選択ソートのアルゴリズム
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 のオーダーの計算量が必要となる．
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] );
}
}
}
マージソートの考え方
ソーティングされた複数のデータをまとめて、
１つのソーティングしたデータにすることを
マージ（merge,併合）と呼ぶ
+
＝
２つのデータグループが既にソーティング
されている場合、これらをまとめて順番に
並べる変えるのは、ばらばらなデータを並
べ直すのよりはるかに少ない手数で可能。
マージの手順
+
小さい順（昇順）の場合なら、
常に一番小さい先頭データ同士のみを
比較すれば十分である
マージの手順
+
小さい順（昇順）の場合なら、
常に一番小さい先頭データ同士のみを
比較すれば十分である
比較の上、小さい方を持ってくる
マージの手順
+
小さい順（昇順）の場合なら、
常に一番小さい先頭データ同士のみを
比較すれば十分である
マージの手順
+
小さい順（昇順）の場合なら、
常に一番小さい先頭データ同士のみを
比較すれば十分である
マージの手順
+
小さい順（昇順）の場合なら、
常に一番小さい先頭データ同士のみを
比較すれば十分である
マージの手順
+
小さい順（昇順）の場合なら、
常に一番小さい先頭データ同士のみを
比較すれば十分である
マージの手順
+
小さい順（昇順）の場合なら、
常に一番小さい先頭データ同士のみを
比較すれば十分である
マージの手順
+
小さい順（昇順）の場合なら、
常に一番小さい先頭データ同士のみを
比較すれば十分である
マージの手順
+
小さい順（昇順）の場合なら、
常に一番小さい先頭データ同士のみを
比較すれば十分である
マージの手順
+
小さい順（昇順）の場合なら、
常に一番小さい先頭データ同士のみを
比較すれば十分である
マージの手順
+
小さい順（昇順）の場合なら、
常に一番小さい先頭データ同士のみを
比較すれば十分である
マージの手順
+
小さい順（昇順）の場合なら、
常に一番小さい先頭データ同士のみを
比較すれば十分である
マージの手順
+
小さい順（昇順）の場合なら、
常に一番小さい先頭データ同士のみを
比較すれば十分である
マージソートの考え方（例）
８つの要素を４つづつに分解
それぞれ
マージソートの考え方（例）
先の手順を、分解されたグループに繰り返し適用する
マージの
繰り返し
マージソートの計算量
要素数N
log2N段
各段でN回のオーダー
の比較と代入
の操作が必要
∴N・log2Nのオーダー
まとめ
•多次元配列
宣言と初期化
配列の長さ知る方法
行列クラスのサンプルプログラム
•ソーティング(並べ替え)アルゴリズム
選択ソート
マージソート
クイックソート

Download Report