| 目次| 1234567891011121314
| 資料| 予定| 課題| 宿題|

整列アルゴリズム

大容量のデータを扱う際に,データはある規則に準じて整列し格納さ れていることが多い.我々が通常目にする多くの種類のデータは,たいていそ のようになっている.例えば,学生に関するデータは学籍番号順(五十音順) に並んで保管されている.図書館に行ってみても,蔵書目録カードは,書籍名 の五十音順と著者名の五十音順に並べられている.さらに,病院のカルテの保 管も生年月日順であったり,五十音順であったりする.このように,データを なんらかの目的に応じて,整列させていることがほとんどである.それは,デー タの検索や参照を考えると,より早い時間で目的のデータが得られ易いからで ある.

このように,並べ換え(整列)の問題は我々にとって身近な問題である.ここで は,代表的な並べ換えの方法を紹介するとともに,プログラムの効率(アルゴ リズムの速さ)について議論する.並べ換えを英語ではソート(sort)と呼ぶ. そのため,並べ換えのアルゴリズムをソーティングアルゴリズムとも言う.

整列アルゴリズムの種類と計算の手間

トランプ(ハートマークのみ13枚)を1から順に整列させることを考えてみよう. ある人は,13枚手に持ちまず1を見つけそれを一番左に移動させ,次に2を見つ け左から2番目に移動させ,・・・を繰り返し,最後には1から順に並べること をするでしょう.ある人は,手にとったカードで隣会ったカードを比べ,大き い方を右へずらし,順次全てのカードに対して行なうことにより,並び換える でしょう.またある人は,13枚床にばらまき1から順に拾って並べることをす るでしょう.このように,カードの並べ換えの方法はいろいろ考えられるよう に,コンピュータを使ったデータの並べ換えにも多くの手法(アルゴリズム)が 提案されている.代表的なものをまとめると,表1のようになる.

表1 整列アルゴリズムの種類

分類 低速アルゴリズム 高速アルゴリズム
選択法 単純選択ソート ヒープソート
挿入法 単純挿入ソート シェルソート(注意*1)
交換法 バブルソート クイックソート
併合法 ・・・ マージソート
注意*1:シェルソートを高速アルゴリズムに分類したが,計算量はO(n^1.2)で あることが知られている.

表1において低速,高速で分類しているが,アルゴリズムの速さとは実行に要 する計算の手間である.理論計算機科学の分野では,この計算の手間を計算量 (計算時間量)と呼び,アルゴリズムの計算量について多くの研究が行なわれ ている.この計算量はアルゴリズムの評価の第一の基準となっている.たとえ, どんなに簡単なアルゴリズムでも目的の結果が得られるまでに,何十年もかかっ てはまったく意味の無いものとなってしまう.

ソーティングアルゴリズムについて言うと,低速アルゴリズムはO(n^2),高速 アルゴリズムはO(nlogn)に分類できる.O(オーダーもしくはビッグオー)とは, 計算量を評価するときの単位で,「O(n)のアルゴリズム」と言う場合対象とす るデータの数nに比例して計算の手間が多くなることを意味する.ソーティン グアルゴリズムの場合は,比較演算あるいは交換演算の回数が対象データの数 の2乗もしくはnlognに比例して多くなる.例えば対象データの数を100倍する と,高速アルゴリズムでは約664 倍(100*log2(100))に,低速アルゴリズムで は10000倍(100*100)になる.

このように,データの数が多くなったときに与えたアルゴリズムが本当に有効 なものなのかを知る手掛かりとして,計算量を評価することは重要なことであ る.一般にアルゴリズムの計算量を評価する方法として,

  1. データの大きさに対する平均計算時間の増加率が小さいほどよい,
  2. 最悪ケースを考えた時のオーダーが小さいほどよい,
  3. 計算時間の分散が少ないほどよい,
の順に評価することがよいとされている.アルゴリズムの優劣は,計算時間量 の他にも,計算時の記憶域の少なさや,ステップ数,エレガントさなどがある.

今回は,ソートアルゴリズムの中から比較的単純な 3 つのアルゴリズム,す なわちバブルソート,選択ソート,挿入ソートについて触れる.これらのアル ゴリズムは,様々なソートアルゴリズムの中では比較的遅いアルゴリズムだが, ソートの基本的な要素がわかり易く表現されているという意味で学ぶ価値があ る.さらに,単にアルゴリズムを学ぶというだけでなく,その計算量(計算回 数)についても議論する.

例題プログラム

単純選択ソートを行うプログラムを以下に示す.
import java.util.*;

public class SelectSort { //プログラムクラス名

    //整列プログラム
    public static void main(String[] args){
	//整列用 int 型配列
	int[] target;
	int elems = KeyboardInput.askInt("要素数? ");

	//配列を乱数で初期化する
	target = setArray(elems);

	//初期状態を表示
	display(target);

	//整列メソッドの呼び出し
	sortArray(target);

	//整列結果の表示
	display(target);
    }

    //配列を乱数で初期化するメソッド
    static int[] setArray(int elems){
	// 要素数個の int 型変数の確保
	int[]  array = new int[elems];

	//乱数利用ための宣言
	Random generator = new Random();

	//乱数の最大値・最小値
	int max = 100;
	int min = 0;
	
	//generator.nextDouble() で 0から1までのdouble型乱数発生
	for(int i=0 ; i<array.length ; i++) {
	    array[i] = (int)((max-min)*(generator.nextDouble())+min);
	}
	
	return array;
    }

    //配列の状態を表示 
    static void display(int[] array){
	for(int i=0 ; i<array.length ; i++) {
	    System.out.print(array[i]+" ");
	}
	System.out.println("");
    }

    //選択ソート
    static void sortArray(int[] array){
	//配列のはじめから最後まで繰り返す
	for( int i = 0; i < array.length-1 ; i++){
	    int min_id = i;
	    int min = array[i];

	    //範囲中でもっとも小さい要素を探す
	    for( int j=i+1 ; j< array.length ; j++ ) {
		if( array[j] < min ){
		    min = array[j];
		    min_id = j ;
		}
	    }

	    //範囲の始めと置き換える
	    int tmp = array[i];
	    array[i] = array[min_id];
	    array[min_id] = tmp;
	    //display(array);
	}
    }
    
}
上のプログラムは次の4つのメソッドから構成されている.
mainメソッド
setArryメソッド
displayメソッド
sortArrayメソッド

単純選択ソート

 ソーティングのなかではもっとも簡単な手法が,単純選択ソートである.説明を簡単にするために,以下のようなデータの列を考えよう.
  49   66   11   37   84   6   22   73
与えられたデータの左から順に見ていき,最小のものを見つける.この場合6が最小データである.その最小データと一番左のデータを入れ換える.
  6   66    11   37   84   49   22   73
次に,左から2番目のデータから右へ順に最小のデータを捜す.11が最小である.2番目のデータ(66)と最小のデータ(11)を入れ換える.
  6   11   66   37   84   49    22   73
同様に左から3番目のデータから順に最小データを捜し,3番目(66)と最小データ(22)を入れ換える.
  6   11   22    37   84    49   66   73
以下,同様な操作を繰り返すと,
  
    6   11   22   37   49   84   66   73

  6   11   22   37   49   66   84   73

  6   11   22   37   49   66   73   84
    
となり,並べ換えが終了する.この考えを取り入れたプログラミングが次のプ ログラムである.

53      static void sortArray(int[] array){
54          //配列のはじめから最後まで繰り返す
55          for( int i = 0; i < array.length-1 ; i++){
56              int min_id = i;
57              int min = array[i];
58
59              //範囲中でもっとも小さい要素を探す
60              for( int j=i+1 ; j< array.length ; j++ ) {
61                  if( array[j] < min ){
62                      min = array[j];
63                      min_id = j ;
64                  }
65              }
66
67              //範囲の始めと置き換える
68              int tmp = array[i];
69              array[i] = array[min_id];
70              array[min_id] = tmp;
71              //display(array);
72          }
73      }
プログラムを簡単に説明する.

59〜65で最小データを捜し最小値とその配列の添字を求めている.67〜70 で,最小値と対象としている一番左側のデータとの入れ換えを行なっている.

選択ソートの各ステップの実行回数を評価してみよう.55〜72を見ると,55, 60のforの2重のループ(繰り返し)になっていることに気付く.55のforルー プにより,56,57, 67〜70はn回実行することがわかる.

60のforループの内側の実行回数を考える.55でi=0の時,60ではjは1からn-1 までを繰り返すので,この時61はn-1回実行する.続いて,55でi=1の時,60で はjは2からn-1まで繰り返すので,この時61はn-2回実行する.以下同様に, i=n-2まで繰り返すと,61の実行回数は(n-1)+(n-2)+...+1 となり,n*(n-1)/2 回となる.

62,63の実行回数は,61のifの判定に依存する.61の判定が真になる確率を考 えなければならないが,ここではラフに1/2としよう.すると,62,63の実行回 数は,61の実行回数の1/2と考えられるため,n*(n-1)/4回となる.これですべ ての実行回数が求まった.

プログラムの計算量は,比較演算回数と入れ換えの回数に着目すると, 61,62,63の実行回数を考えればよい.つまり,n*(n-1)/2とn*(n-1)/4である. 今,nの値をとてつもなく大きくすることを考えると,-1が無視できn=n-1と考 えられる.同様に,1/2も1/4 もnがすごく大きい時には,無視できる.nが大 きいとき61,62,63は,約n*n(n^2)回実行されると考えられる.

よって,56,57, 67〜70はn回実行されるが,n^2にくらべてnはnが十分大きけ れば無視できるのでプログラム全体の計算量はO(n^2)であることが言える.

バブルソート

バブルソートは単純選択ソートを少し変形したもので,最小値を求めることを せずに,左から順に隣会った左右のデータを比べ,左側のデータが大きい時に はすぐに入れ換えを行なう方法である.

バブルとは泡を意味していて,データが下から上へ泡立つ(左から右へ順に大 きくなる)ように並べ換えが行なわれることから,泡立ち法とも呼ばれている. 下記の例で,その動きを見よう.

49   66   11   37   84    6   22   73
まず,49と66を比べ49の方が小さいのでなにもしない.
49   66   11   37   84    6   22   73
続いて,66と11を比べ11の方が小さいので11と66を入れ換える.
49   11   66   37   84    6   22   73
さらに,66と37を比べ37の方が小さいので66と37を入れ換える.
49   11   37   66   84    6   22   73
                       ・
                          ・
                          ・
以下,一番右のデータまで繰り返す.
   49   11   37   66    6   22   73   84
すると,一番右側に最大のデータがくる.上記の操作を,左から順に右から2 番目までのデータに対して行なう.
    11   37   49    6   22   66   73   84
すると,右から2番目には2番目に大きいデータがくる.このように,上記操 作を続けると最後には左から昇順にデータは並ぶことになる.
 6   11   22   37   49   66   73   84
上記のデータの動きからも,泡立つ様子がうかがえたことでしょう. バブルソートも単純選択ソートと同様O(n^2)の計算量を持ちます.

単純挿入ソート

単純挿入ソートは,対象とするデータがリストのようなときにはとても有効で ある.しかし,単なる配列データの時には,基本的な考え方はバブルソートと 同じである.また,例をあげて解説しよう.
   49   66   11   37   84   6   22   73
単純挿入法では,あらかじめ並べ換えが済んでいるデータ列に新たにデータを 挿入する事を基本としている.そこで,まず左から1番目までが並べ換えが済 んでいるとして,2番目のデータをそこに挿入することを考える.この例では, 49が1つしかないデータ列に66を挿入することを考える.この場合は,なんの 変化もない.
   49   66   11   37   84   6   22   73
 
次に,49,66のデータ列に11を挿入することを考える.大きい方から小さい方 (右から左へ)に向かって比較していき,ソート済みのデータ列のどこに挿入 できるかを見ていく.この場合は,11が一番小さいため一番左に挿入されたこ とになる.
    11   49   66   37   84   6   22   73
  
次に,11,49,66のデータ列に37を挿入する.66から左へ順に見ていく.
    11   37   49   66   84   6   22   73
以下,同様な操作を行なう.
    11   37   49   66   84    6   22   73

     6   11   37   49   66   84   22   73

     6   11   22   37   49   66   84   73
 
     6   11   22   37   49   66   73   84
単純挿入ソートもO(n^2)の計算量を持ちます.

以上,3種類の低速アルゴリズムを示した.これらのアルゴリズムは単純であるが,O(n^2)の計算量を持つことが理解できたであろう.

このn^2のオーダーがどの程度のものなのかは,y=x^2のグラフを方眼紙に書い てみるとよい.xがある数値を越えると,yが急に大きくなり方眼紙をはみ出し てしまう.このように,データの個数がある点を越えると,ソートにとてつも なく時間を要するようになるということである.

課題

  1. 単純選択ソートアルゴリズムを入力し,実行してみる.
  2. バブルソートもしくは単純挿入ソートのプログラムに変更する.

| 目次| 1234567891011121314
| 資料| 予定| 課題| 宿題|