第９回 並び替えアルゴリズム
～さまざまなアルゴリズムを比較しよう～
学習目標
適切なアルゴリズムを用いたプログラムが
書ける
並び替え（ソート）アルゴリズムの性能につい
て比較検討し、説明できる
Javaでソートのプログラムが書ける
問題が与えられたとき、適切なアルゴリズムで
プログラムを書ける
9.1 並び替えの
性能比較プログラム
9.1.1 今回扱うアルゴリズム
9.1.2 実験環境の構築
①ソート性能比較プログラムの設計
②ランダムな数値を発生させる
9.1.1 今回扱うアルゴリズム
リニアサーチを使えるのは次の場合に限ら
れる
要素が少ない時(数十個程度)
ソートされていないデータに対する時
バイナリサーチを使うには、ソート済み
（順番に並んでいる状態）である必要あり
今回は、ソートを考えましょう
今回は簡単なソートをやります
ソートは重要で時間のかかる処理なので、これま
でにも多くのコンピュータ科学者が研究に取り組
み、いくつかの高度な方法も発明されています
今回はその中で比較的簡単な3つの方法を紹介
します
バブルソート
選択ソート
挿入ソート
これらのテクニックは素朴で、遅いアルゴリズムですが、やってみる価値はあります
単に分かりやすいだけでなく、データの並び方や数によって、これらの方法のほうが
速い場合もあるからです
9.1.2 実験環境の構築
①クラス設計
②ランダムに数値を発生させる
①クラス設計
ItemTypeList
+ add()
+ isSort()
+ sort()
•sort()メソッド － ソートする
•isSort()メソッド － ソート済みか調べる
ItemTypeListにメソッドを追加します
クラス設計(2)
アルゴリズムをクラスに、ポリモーフィズム
で設計します
ItemTypeList
SortAlgorism
+ add()
+ isSort()
+ sort()
+ sort()
BubbleSort
+ sort()
SelectionSort
+ sort()
InsertionSort
+ sort()
②ランダムに数値を発生させる
Math.random()メソッドを使います
double randomId = Math.random();
メソッドの返り値はdouble型で、
0～1の間のランダムな数を返します
1～Nまでの
ランダムな数を発生させる
int randomRange = 1000000;//ランダムの範囲
（100万なら1～100万の範囲のランダムな数字を生成する）
double randomNo = Math.random();
int randomInt = (int)(randomNo*randomRange);
double型をint型に
変換(キャスト)します
ランダム生成した0以上～1未満
の少数をN倍して0～(N-1)にします
9.2 ソートのアルゴリズム
9.2.1 バブルソート
①コンピュータでの「入れ替え」(Swap)
9.2.2 選択ソート
9.2.3 挿入ソート
9.2.4 挿入ソートの効率化
9.2.1 バブルソート
アルゴリズム
1.
2.
3.
4.
2つの商品番号を比較する
左側の方の番号が大きければ商品種類を入れ替え
る。
右へ一つ移動する
ソートの終ってない部分(毎回小さくなる)に対して上
のステップを繰り返す
※配列の一番左の箱の中の番号が最小になるように並べ
替える場合です
バブルソート
比較する
比較する
比較する
比較する
比較する
比較する
比較する
入れ替える
そのまま
入れ替える
入れ替える
そのまま
入れ替える
入れ替える
ソート済み
ソート済み
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)やり方
一時的に箱を用意します
入れ替え完了！
これを何回もやるのは
結構時間かかります
コピー
コピー コピー
51
3
51
3
3
[0]
[1]
tmp
練習問題
バブルソートの効率を考えなさい
特に
①比較の回数
②入れ替えの回数
を考えなさい
バブルソートの効率
（考えてみましょう）
①比較の回数
②入れ替えの回数
バブルソートの実装
例題9-1
(BubbleSort.java)
public class BubbleSort implements SortAlgorithm{
/**
* 並び替え（ソート）をするメソッド
*/
public void sort(ItemType[] itemTypeArray,int size){
for(int i=size-1;i>1;i--){//要素数回始めから作業を繰り返す
for(int j=0;j<i;j++){//ソート済みの所まで作業する
if(itemTypeArray[j].getId() > itemTypeArray[j+1].getId()){
swap(itemTypeArray,j,j+1);//もし右側のほうが大きかったら入れ替える
}
}
}
}
}
※swapメソッドは次のページ
入れ替え(swap)の実装
例題9-1
(BubbleSort.java)
/**
* 要素を入れ替えるメソッド
*/
private void swap(ItemType[] itemTypeArray,int target1,int target2){
ItemType temp;//temporaryの箱を用意する
temp = itemTypeArray[target1];
itemTypeArray[target1] = itemTypeArray[target2];
itemTypeArray[target2] = temp;
}
9.2.2 選択ソート
アルゴリズム
1.
2.
全商品番号から、一番小さい番号を探す。
見つかったものと、一番左の商品種類を入
れ替える。
ソートの終ってない部分(毎回小さくなる)に
対して上のステップを繰り返す。
選択ソート
比較する
比較する
比較する
比較する
比較する
比較する
比較する
比較する
比較する
入れ替える
入れ替える
ソート済み
ソート済み
103
3 18
22
51
103
3 64
18
22
[0]
[2]
[3]
[5]
[1]
[4]
[6]
[7]
[8]
[9]
最小値を更新する
ここからまた同じことをはじめる
このようにして、ソートが終わるまで
最小値が見つかった！
最小値が
5130
続けます。
みつかった
最小値の入っている
箱の番号
練習問題２
選択ソートの効率を考えなさい
特に
①比較の回数
②入れ替えの回数
を考えなさい
選択ソートの効率
（考えてみましょう）
①比較の回数
②入れ替えの回数
選択ソートの実装
例題9-1
(SelectionSort.java)
public class SelectionSort implements SortAlgorithm{
/**
* 並び替え（ソート）をするメソッド
*/
public void sort(ItemType[] itemTypeArray,int size){
for(int i=0;i<size-1;i++){//要素数回始めから作業を繰り返す
int minimum = i;//最小値の配列番号を保存しておく
for(int j=i+1;j<size;j++){//ソート済み以降を作業する
if(itemTypeArray[j].getId() < itemTypeArray[minimum].getId()){
minimum = j;//最小値より小さかったら、新しい最小値に
}
}
swap(itemTypeArray,i,minimum);//一番左の要素(ソート済み除く)と最小と入れ替える
}
}
}
9.2.3 挿入ソート
アルゴリズム
1.
2.
途中までソートが終わっているとします
（そのほうが理解しやすいので）
ソートが終わっていない中で、一番左にある
商品種類をソート済みの商品種類の中で、
あるべき位置に挿入します
ソートの終ってない部分(毎回小さくなる)に
対して上のステップを繰り返します
挿入ソート
ソート済み
ソート済み部分が増えた！
移動
コピー
3
18
51
22
64
51
22
64
18
103
[0]
[1]
[2]
[3]
[4]
[5]
[6]
ここだ！
入れるところを探す
[8]
[9]
コピーする
次に挿入する
ターゲット
次に挿入すべき商品種類
22
これを繰り返します。
[7]
tmp
練習問題３
挿入ソートの効率を考えなさい
特に
①比較の回数
②入れ替えの回数
を考えなさい
挿入ソートの効率
（考えてみましょう）
①比較回数
②入れ替え回数
場合によって効率が変わる！
挿入ソートは、ほとんどソートされていると
きには、とても効率的
逆に、逆順にソートされている場合、最大
の比較回数と移動回数が実行されてしま
い、バブルソートと同じ遅さになってしまう
挿入ソートのアルゴリズム
public class InsertionSort implements SortAlgorithm{
例題9-1
(InsertionSort.java)
/**
* 並び替え（ソート）をするメソッド
*/
public void sort(ItemType[] itemTypeArray,int size){
int target;//挿入する対象
for(target = 1;target<size;target++){
ItemType temp = itemTypeArray[target];//対象をコピーする
int i=target;
while(i>0 && itemTypeArray[i-1].getId() > temp.getId()){//挿入場所に出会うまで
シフトしつづける
itemTypeArray[i] = itemTypeArray[i-1];//右へシフト
i--;
}
itemTypeArray[i] = temp;//対象を挿入する
}
}
9.2.4 挿入ソートの効率化
挿入ソートをあと少しだけ効率化すること
を考えましょう
条件文に注目する
挿入ソートのプログラム抜粋
/**
* 並び替え（ソート）をする
*/
public void sort(ItemType[] itemTypeArray,int size){
int target;//挿入する対象
for(target = 1; target<size; target++){
ItemType temp = itemTypeArray[target];//対象をコピーする
int i=target;
while(i>0 && itemTypeArray[i-1].getId() > temp.getId()){
//挿入場所に出会うまでシフトしつづける
itemTypeArray[i] = itemTypeArray[i-1];//右へシフト
i--;
}
itemTypeArray[i] = temp;//対象を挿入する
}
}
非効率な条件文
while(i>0 && itemTypeArray[i-1].id > temp.id)
①
②
iが0以上 かつ 配列の中の商品番号が、対象商品番号より大きい
間繰り返す
挿入すべき場所を探したい
しかし①の条件は、ほとんど成り立たない（後述）
にもかかわらず、N^2/4回行われてしまう
条件文を変えられないか
「i<0」条件文が何故必要なのか、考えて
みましょう
「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など）
を利用すれば絶対に配列からはみ出さない
配列[0]は番兵用
0番目は番兵を常に入れておきます
-1
18
35
2
46
8
[0]
[1]
[2]
[3]
[4]
[5]
番兵用
[6]
[7]
[8]
[9]
番兵を使うときの注意
番兵を使うと、使える配列は一つ少なくなる
いっぱいにはしないとか、一つ増やした配列を用意する
などの対応を取るのが一般的
0番目は番兵用に空けるため、追加アルゴリズム
にも変更が必要
ソートのときだけずらすやり方でまずはやってみましょう
（ただし効率は少し落ちる）
今回は配列の一番始めに番兵を立てますが、アルゴリ
ズムによっては、一番最後に番兵を立てる場合もありま
す。その場合は他のアルゴリズムの変更が不要
番兵を利用した場合のwhile文
番兵導入前
while(i>0 && itemTypeArray[i-1].id > temp.id)
番兵導入後
while(itemTypeArray[i-1].id > temp.id)
さらにスマートなアルゴリズムに
さっきは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]
© Copyright 2024 ExpyDoc
