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