第９回　並び替えアルゴリズム ～さまざまなアルゴリズムを比較しよう～

学習目標 適切なアルゴリズムを用いたプログラムが書ける 並び替え（ソート）アルゴリズムの性能について比較検討し、説明できる Javaでソートのプログラムが書ける 問題が与えられたとき、適切なアルゴリズムでプログラムを書ける

9.1 並び替えの 性能比較プログラム 9.1.1 今回扱うアルゴリズム 9.1.2 実験環境の構築 ①ソート性能比較プログラムの設計 ②ランダムな数値を発生させる

9.1.1 今回扱うアルゴリズム リニアサーチを使えるのは次の場合に限られる 要素が少ない時(数十個程度) ソートされていないデータに対する時 バイナリサーチを使うには、ソート済み （順番に並んでいる状態）である必要あり 今回は、ソートを考えましょう

今回は簡単なソートをやります ソートは重要で時間のかかる処理なので、これまでにも多くのコンピュータ科学者が研究に取り組み、いくつかの高度な方法も発明されています 今回はその中で比較的簡単な3つの方法を紹介します バブルソート 選択ソート 挿入ソート これらのテクニックは素朴で、遅いアルゴリズムですが、やってみる価値はあります 単に分かりやすいだけでなく、データの並び方や数によって、これらの方法のほうが 速い場合もあるからです

9.1.2 実験環境の構築 ①クラス設計 ②ランダムに数値を発生させる

①クラス設計 sort()メソッド － ソートする isSort()メソッド － ソート済みか調べる ItemTypeListにメソッドを追加します

クラス設計(2) アルゴリズムをクラスに、ポリモーフィズムで設計します

②ランダムに数値を発生させる 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 バブルソート 9.2.2 選択ソート 9.2.3 挿入ソート 9.2.4 挿入ソートの効率化 ①コンピュータでの「入れ替え」(Swap) 9.2.2 選択ソート 9.2.3 挿入ソート 9.2.4 挿入ソートの効率化

9.2.1 バブルソート アルゴリズム 2つの商品番号を比較する 左側の方の番号が大きければ商品種類を入れ替える。 右へ一つ移動する ソートの終ってない部分(毎回小さくなる)に対して上のステップを繰り返す ※配列の一番左の箱の中の番号が最小になるように並べ替える場合です

バブルソート 一つ移動する 一つ移動する 一つ移動する 一つ移動する 一つ移動する 一つ移動する 一つ移動する 一つ移動する 一つ移動する 22 51 そのまま 22 103 入れ替える 3 51 入れ替える 51 103 入れ替える 51 64 そのまま 3 103 入れ替える 18 64 入れ替える 64 103 入れ替える 18 103 入れ替える 比較する 比較する 比較する 比較する 比較する 比較する 比較する 比較する 比較する ソート済み ソート済み 103 22 51 3 64 18 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] もう一度 始めから とやっていくと、最後に ソートされます ※実際にはオブジェクトが入りますが、今日は見やすいように番号 だけが入っているように見せます

①コンピュータでの 「入れ替え」(Swap) 前ページの例では、「入れ替え」を一瞬で行っていましたが、実はコンピュータはそのような操作はできません 3 51 入れ替える 51 3 [0] [1]

コンピュータでの「入れ替え」 (Swap)やり方 一時的に箱を用意します 入れ替え完了！ これを何回もやるのは 結構時間かかります 3 コピー 51 コピー 3 コピー 51 3 [0] [1] tmp

練習問題 バブルソートの効率を考えなさい 特に ①比較の回数 ②入れ替えの回数 を考えなさい

バブルソートの効率 （考えてみましょう） ①比較の回数 ②入れ替えの回数

バブルソートの実装 ※swapメソッドは次のページ 例題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 最小値を更新する 入れ替える 比較する ソート済み 入れ替える 103 22 51 3 64 18 3 103 18 22 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] 最小値が見つかった！ 3 最小値を更新する 5 最小値を更新する 1 最小値を更新する このようにして、ソートが終わるまで 続けます。 最小値の入っている 箱の番号

練習問題２ 選択ソートの効率を考えなさい 特に ①比較の回数 ②入れ替えの回数 を考えなさい

選択ソートの効率 （考えてみましょう） ①比較の回数 ②入れ替えの回数

選択ソートの実装 例題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 挿入ソート アルゴリズム 途中までソートが終わっているとします （そのほうが理解しやすいので） ソートが終わっていない中で、一番左にある商品種類をソート済みの商品種類の中で、あるべき位置に挿入します ソートの終ってない部分(毎回小さくなる)に対して上のステップを繰り返します

挿入ソート [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] 3 18 22 51 64 103 [0] ソート済み ソート済み部分が増えた！ 22 コピー 移動 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] 3 18 22 51 64 103 3 18 51 64 22 103 コピーする 22 51 64 ここだ！ これを繰り返します。 次に挿入する ターゲット 次に挿入すべき商品種類 入れるところを探す tmp

練習問題３ 挿入ソートの効率を考えなさい 特に ①比較の回数 ②入れ替えの回数 を考えなさい

挿入ソートの効率 （考えてみましょう） ①比較回数 ②入れ替え回数

場合によって効率が変わる！ 挿入ソートは、ほとんどソートされているときには、とても効率的 逆に、逆順にソートされている場合、最大の比較回数と移動回数が実行されてしまい、バブルソートと同じ遅さになってしまう

挿入ソートのアルゴリズム 例題9-1 (InsertionSort.java) 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.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;//対象を挿入する

非効率な条件文 挿入すべき場所を探したい しかし①の条件は、ほとんど成り立たない（後述） にもかかわらず、N^2/4回行われてしまう 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番目は番兵用に空けるため、追加アルゴリズムにも変更が必要 いっぱいにはしないとか、一つ増やした配列を用意するなどの対応を取るのが一般的 0番目は番兵用に空けるため、追加アルゴリズムにも変更が必要 ソートのときだけずらすやり方でまずはやってみましょう（ただし効率は少し落ちる） 今回は配列の一番始めに番兵を立てますが、アルゴリズムによっては、一番最後に番兵を立てる場合もあります。その場合は他のアルゴリズムの変更が不要

番兵を利用した場合のwhile文 番兵導入前 while(i>0 && itemTypeArray[i-1].id > temp.id) 番兵導入後 while(itemTypeArray[i-1].id > temp.id)

さらにスマートなアルゴリズムに さっきはtemp用の箱を用意 しましたが、、、 -1 18 35 18 35 2 46 8 2 46 8 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] 2 対象 temp

自分自身を番兵とする 自分自身も番兵になります 何故そうなるのか考えてみよう 18 -1 2 35 18 35 2 46 8 2 46 8 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] 対象