オブジェクト・プログラミング
第7回
アルゴリズム
前回多かった質問
要素が少ないとき、0msと出てしまう。
この方法ではms以下の時間は計れないので、
仕方がないです。コンピュータはmsより小さい
単位で動いています。
毎回かかる時間が微妙に違う
Windowsがマルチタスクなためです。
よって、この手の考察を行う場合、何回かの
平均を取るべきです。（そんなプログラムは簡
単に書けるでしょう！？）
前回の経験より
リニアサーチを使うのは次の場合に限られ
る。
要素が少ない時(数十個程度)
ソートされていないデータに対する時
だけどバイナリサーチはソート（順番に並
んでいる）されていなければ、使えない！
今日は、ソートを学びます。
今週の目標
ソートのアルゴリズムについて説明するこ
とができる。（教科書第3章）
Javaでソートをするプログラムが書けるように
なる。
Javaのテクニックを学ぶ
ランダムに商品情報を作る。
ファイルの入出力を行う。
今日は簡単なソートをやります
ソートは重要で時間のかかる処理なので、これま
でにも多くのコンピュータ科学者が研究に取り組
み、いくつかの高度な方法も発明されています。
その中で比較的簡単な3つの方法を紹介します。
バブルソート
選択ソート
挿入ソート
これらのテクニックは素朴で、遅いアルゴリズム
ですが、勉強する価値はあります。単に分かりや
すいだけでなく、データの並び方や数によって、
これらの方法のほうが速い場合もあるからです。
バブルソート
アルゴリズム
(1)2つの商品番号を比較する
(2)左側の方の番号が大きければ商品情報を入れ替
える。
(3)右へ一つ移動する。
ソートの終ってない部分(毎回小さくなる)に対して上
のステップを繰り返す
※配列の一番左の箱の中の番号が最小になるように並べ替
える場合です。
バブルソート
比較する
比較する
比較する
比較する
比較する
比較する
比較する
入れ替える
そのまま
入れ替える
入れ替える
そのまま
入れ替える
入れ替える
ソート済み
ソート済み
103
22 103
22
51
3 103
51
3 103
64
18
3 103
18 103
64
18
[0]
[1]
[2]
[3]
[4]
[5]
[6]
もう一度
一つ移動する
一つ移動する
一つ移動する
一つ移動する
一つ移動する
一つ移動する
始めから
[7]
[8]
[9]
とやっていくと、最後に
ソートされます。
※実際にはオブジェクトが入りますが、今日は見やすいように番号
だけが入っているように見せます。
コンピュータでの「入れ替え」
(Swap)
前ページの例では、「入れ替え」を一瞬で
行っていましたが、実はコンピュータはそ
のような操作はできません。
入れ替える
51
3
51
3
[0]
[1]
コンピュータでの「入れ替え」
(Swap)やり方
temporaryの箱を利用します。
入れ替え完了！
これを何回もやるのは
結構時間かかります。
コピー
コピー コピー
51
3
51
3
3
[0]
[1]
tmp
バブルソートの効率
問題：バブルソートの効率を考えなさい。
①比較の回数
②入れ替えの回数
を考えなさい。
バブルソートの効率（答え）
①比較の回数
2要素のとき→1回
3要素のとき→1+2回
4要素のとき→1+2+3回
N要素のとき→(N-1)+(N-2)+(N-3)…+1回
=N*(N-1)/2=N^2/2回
②入れ替えの回数
確率的に、比較したうちの半分を入れ替える。
よって、約N^2/2 /2 = N^2/4回
バブルソートの実装
//バブルソートをするメソッド(ItemInfoFolderクラス)
public void bubbleSort(){
for(int i=size-1;i>1;i--){//要素数回始めから作業を繰り返す
for(int j=0;j<i;j++){//ソート済みの所まで作業する
if(itemInfoArray[j].no > itemInfoArray[j+1].no){
swap(j,j+1);//もし右側のほうが大きかったら入れ替える
}
}
}
}
※swapメソッドは次のページ
入れ替え(swap)の実装
//要素を入れ替えるメソッド
public void swap(int target1,int target2){
ItemInfo temp;//temporaryの箱を用意する
temp = itemInfoArray[target1];
itemInfoArray[target1] = itemInfoArray[target2];
}
itemInfoArray[target2] = temp;
選択ソート
アルゴリズム
(1)全商品番号から、一番小さい番号を探す。
(2)見つかったものと、一番左の商品情報を入
れ替える。
ソートの終ってない部分(毎回小さくなる)に対
して上のステップを繰り返す。
選択ソート
比較する
比較する
比較する
比較する
比較する
比較する
比較する
比較する
比較する
入れ替える
入れ替える
ソート済み
ソート済み
103
3 18
22
51
103
3 64
18
22
[0]
[2]
[3]
[5]
[1]
[4]
[6]
[7]
[8]
[9]
最小値を更新する
ここからまた同じことをはじめる
このようにして、ソートが終わるまで
最小値が見つかった！
最小値が
5130
続けます。
みつかった
最小値の入っている
箱の番号
選択ソートの効率
①比較の回数
2要素のとき→1回
3要素のとき→1+2回
4要素のとき→1+2+3回
→バブルソートと同じ。約N^2/2回
②入れ替えの回数
2要素のとき→1回
3要素のとき→2回
4要素のとき→3回
→位置の入れ替えはN回ですむ
バブルソートより少しだけ速い。
選択ソートの実装
//選択ソートをするメソッド(ItemInfoFolderクラス)
public void selectionSort(){
for(int i=0;i<size-1;i++){//要素数回始めから作業を繰り返す
int minimum = i;//最小値の配列番号を保存しておく
for(int j=i+1;j<size;j++){//ソート済み以降を作業する
if(itemInfoArray[j].no < itemInfoArray[minimum].no){
minimum = j;//最小値より小さかったら、新しい最小値に
}
}
swap(i,minimum);//一番左の要素(ソート済み除く)と
//最小と入れ替える
}
}
挿入ソート
アルゴリズム
(1)途中までソートが終わっているとします。
（そのほうが理解しやすいので）
(2)ソートが終わっていない中で、一番左にあ
る商品情報をソート済みの商品情報の中で、
あるべき位置に挿入します。
ソートの終ってない部分(毎回小さくなる)に対
して上のステップを繰り返します。
挿入ソート
ソート済み
ソート済み部分が増えた！
移動
コピー
3
18
51
22
64
51
22
64
18
103
[0]
[1]
[2]
[3]
[4]
[5]
[6]
ここだ！
入れるところを探す
[8]
[9]
コピーする
次に挿入する
ターゲット
次に挿入すべき商品情報
22
これを繰り返します。
[7]
tmp
挿入ソートの効率
①比較回数
2要素のとき→1回
3要素のとき→1+2回
4要素のとき→1+2+3回
挿入ソートの場合、上記は最大比較回数で、確率的
に、だいたいそれより早く見つかるので、
N^2/2 /2=N^2/4となる。
N2乗のオーダーは変わらないが、バブル、選択ソートよ
り、約2倍速い。
②入れ替え回数
入れ替えも比較の回数とほぼ同じであるが、挿入ソー
トでは、入れ替えではなく、隣にコピーするだけである
ため、多少効率は良い。
場合によって効率が変わる！
挿入ソートは、ほとんどソートされていると
きには、とても効率的。
逆に、逆順にソートされている場合、最大
の比較回数と移動回数が実行されてしま
い、バブルソートと同じ遅さになってしまう。
挿入ソートのアルゴリズム
//挿入ソートをするメソッド(ItemInfoFolderクラス)
public void insertionSort(){
int target;//挿入する対象
for(target = 1;target<size;target++){
ItemInfo temp = itemInfoArray[target];//対象をコピーする
int i=target;
while(i>0 && itemInfoArray[i-1].no > temp.no){//挿入場所に
出会うまでシフトしつづける
itemInfoArray[i] = itemInfoArray[i-1];//右へシフト
i--;
}
itemInfoArray[i] = temp;//対象を挿入する
}
挿入ソートをあと少しだけ効率化
する。
//前ページのプログラムと同じです。
public void insertionSort(){
int target;
for(target = 1;target<size;target++){
ItemInfo temp = itemInfoArray[target];
int i=target;
while(i>0 && itemInfoArray[i-1].no > temp.no){
itemInfoArray[i] = itemInfoArray[i-1];
i--;
}
itemInfoArray[i] = temp;
この行に注目！！
}
}
非効率な条件文
while(i>0 && itemInfoArray[i-1].no > temp.no)
日本語に直すと、
①iが0以上で、
かつ、
②配列の中の商品番号が、対象商品番号より大きい間
となる。
ようは、挿入すべき場所を探しているのだが、この中で①
の条件は、ほとんど成り立たない（後述）にもかかわらず、
N^2/4回行われてしまう。これはNが増えたときにボトル
ネックにになってしまう。何とかして、条件は一つにしたい
な。
i<0の条件をなくすと何故まず
い？
ソート済み
18
35
2
46
8
[0]
[1]
[2]
[3]
[4]
挿入対象
[5]
[6]
[7]
[8]
[9]
こんな時、iは0以下になってしまい、
-1の配列をアクセスしてしまい、
ArrayIndexOutOfBoundsExceptionが
出てしまいます。
何故かは考えてみよう！
条件をなくしてもエラーをなくす
方法
-1
番兵くん登場！
18
35
2
46
8
[-1] [0]
[1]
[2]
[3]
[4]
番兵くん
[5]
[6]
[7]
[8]
[9]
こいつに絶対ありえない小さいの商品番号（この場合、
商品番号は必ず正だとすると-1とか-10000000とかを
入れておく）入れておけば、i>0の条件を抜いても、
絶対に配列からはみ出さない。
だけど-1なんていう配列は作れ
ない。
0番目を番兵用に空けます。
-1
18
35
2
46
8
[0]
[1]
[2]
[3]
[4]
[5]
番兵用
[6]
[7]
[8]
[9]
※０番目は番兵用に空けるため、挿入のときなどの
プログラムにも工夫が必要になります。
番兵を使うときの注意
番兵を使うと、使える配列は一つ少なくな
るので注意！
いっぱいにはしないとか、一つ増やした配列を
用意するなどの対応を取るのが一般的。
今回は配列の一番始めに番兵を立てます
が、アルゴリズムによっては、一番最後に
番兵を立てる場合もあります。
番兵を利用した場合のwhile文
番兵以前
while(i>0 && itemInfoArray[i-1].no > temp.no)
番兵以後
while(itemInfoArray[i-1].no > temp.no)
さらに、、
さっきはtemp用の箱を用意
しましたが、、、
18
-1
35
18
35
2
46
2
46
8
8
[0]
[1]
[2]
[3]
[4]
[5]
対象
[6]
[7]
[8]
[9]
2
temp
番兵を利用して、もっとスマート
なアルゴリズムに
18
-1
2
35
18
35
2
46
2
46
8
8
[0]
[1]
[2]
[3]
[4]
[5]
対象
[6]
[7]
[8]
[9]
自分自身を番兵として入れると
Tempの代わりになり、スマートです。
なぜ、自分自身を入れても、番兵として
の役割を果たせるのか考えてみよう！
今週の課題
今週はソートの時間を計ってもらいます。
ItemInfoFolderに
バブルソートを行うbubbleSort()メソッド
選択ソートを行うselectionSort()メソッド
挿入ソートを行うinsertionSort()メソッド
を加え、実装しなさい。
今週の課題（続き）
実装した３つのソートの性能を時間を計っ
て、比べなさい。
要素数は、最低4種類で行いなさい。
どれぐらいがよいかは自分で判断すること。
発展問題(必修ではない)
番兵付き挿入ソートを行う
insSortWithGuard()メソッドを作ってそれも考
察しなさい。
課題のために
今回の課題では、ソートされていない、商
品情報をたくさん作る必要があります。
ランダムに商品情報を作る方法を紹介しま
す。
ランダムに数値を発生させる
Math.random()メソッドを使います。
このメソッドの返り値はdouble型で、
0～1の間のランダムな数を返します。
1～Nまでのランダムな数を発生
させる。
double randomNo = Math.random();
int itemNo = (int)(randomNo*N)
double型をint型に
変換します。
実際の数字を入れます。
何回も同じ条件で実行したい
毎回ランダムに数字を発生させて実験す
ると、毎回違う条件になってしまいます。
→ソートは条件が変わると性能も変わる
毎回同じ条件で商品情報を生成できるよう
に、ランダムに数字を生成したら、ファイル
に書き出しておくことにします。
ファイルに書き出しておこう！
ランダムに数字を発生し、
ファイルに書き出すプログラム
書き出し
102
83
58
3
493
38
…
番号を書きとめておくファイル
randomNo.txt(名前は任意)
読み込み
ソートを実行するプログラム
(VendingMachineMain)
ファイルに読み書きする方法
Javaでは、簡単にできるように以下のクラスが用意されています。
書き出し
BufferedWriterクラス
OutputStreamクラス
FileOutputStreamクラス
ファイル
プログラム
読み込み
BufferedReaderクラス
InputStreamクラス
FileInputStreamクラス
Javaでファイルを扱う
これらのクラスを扱う際には、必ず、
import java.io.*;
と宣言します。（クラス宣言の前にするこ
と）
package vendingmachine;
import java.io.*;
public class RandomItemInfoMaker{
…
}
注：Package文は
なくてもよい。
ファイルの書き出し
書き出すファイル名
//ファイルの書き出し部分だけ抜粋
try{
//ファイル出力のためのBufferedWriterクラスを生成します。
FileOutputStream fos = new FileOutputStream("randomNo.txt");
OutputStreamWriter osw = new OutputStreamWriter(fos);
BufferedWriter bw = new BufferedWriter(osw);
bw.write(“Test”);//write()メソッドで書き込みます。
bw.newLine();//newLine()メソッドで改行します。
bw.close();//close()メソッドでファイルを閉じます。
}catch(Exception ex){
ex.printStackTrace();
全体をtry{ }catchで囲む必要があります。
これについては、後にやります。
ファイルの読み込み
読み込むファイル名
//ファイルの読み込み部分だけ抜粋
try{
//ファイル出力のためのBufferedReaderクラスを生成します。
FileInputStream fis = new FileInputStream("randomNo.txt");
InputStreamReader isr = new InputStreamReader(fis);
BufferedReader br = new BufferedReader(isr);
String line = br.readLine()//readLine()メソッドで一行読み込み、
読み込んだ文字列を返り値として返します。
bw.close();//close()メソッドでファイルを閉じます。
}catch(Exception ex){
ex.printStackTrace();
全体をtry{ }catchで囲む必要があります。
これについては、後にやります。
その他は質問どうぞ
以下の２つのプログラムを配ります。
Randomに数字を生成して、ファイルへの書き
出しができるプログラムの
RandomItemInfoMakerクラス
そのファイルを読み込んで、ランダムな商品番
号のItemInfoクラス生成できる
VendingMachineMainクラス
なるべくコメントを書いておきますが、分か
らない点はTAに質問してください。
提出方法
[email protected]宛て。
今回もソースのほかに、
実行結果、考察を書いて送ってください。
（ただし、ソースはItemInfoFolderだけでよい。)
Subjectはログイン名を必ず書いてください。
(感想を任意でお願いします。)
ex) t96844ym
余計な[]などをつけないでください。
水曜まで。
© Copyright 2024 ExpyDoc
