低速アルゴリズム

 

単純選択ソート ( Selectsort )

 ソーティングのなかではもっとも簡単な手法が、単純選択ソートである。説明を簡単にするために、以下のようなデータの列を考えよう。
  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
    
  
となり、並べ換えが終了する。
この考えを取り入れたプログラミングが次のプログラムである。

 1:  void Selectsort(int data[], int n) {
 2:  	int min, tmp, i, j, min_id;
 3: 
 4:  	for (i=0; i < n-1; i++) {
 5:  		min = data[i];
 6:  		for (j=i+1; j < n; j++)
 7:  			if(data[j] < min) {
 8:  				min = data[j];
 9:  				min_id = j;
10:  			}
11:  		tmp = data[i];
12:  		data[i] = data[min_id];
13:  		data[min_id] = tmp;
14:  	}
15:  }
 プログラムを簡単に説明する。
Selectsort() により、生成したデータを単純選択ソートにより並べ換えをする。  Selectsort() においては、5〜10で最小データを捜し最小値とその配列の添字を求めている。11〜13で、最小値と対象としている一番左側のデータとの入れ換えを行なっている。
 Selectsortの各ステップの実行回数を評価してみよう。4〜14を見ると、4,6のforの2重のループ(繰り返し)になっていることに気付く。4のforループにより、4, 5,11,12,13はn回実行することがわかる。
 6のforループの内側の実行回数を考える。4でi=0の時、6ではjは1からn−1までを繰り返すので、この時7はn−1回実行する。続いて、4でi=1の時、6ではjは2からn−1まで繰り返すので、この時7はn−2回実行する。以下同様に、i=n−2まで繰り返すと、7の実行回数は(n−1)+(n−2)+・・・+1となり、n*(n−1)/2回となる。
 8,9の実行回数は、7のifの判定に依存する。7の判定が真になる確率を考えなければならないが、ここではラフに1/2としよう。すると、8,9の実行回数は、7の実行回数の1/2と考えられるため、n*(n−1)/4回となる。これですべての実行回数が求まった。
 プログラムの計算量は、比較演算回数と入れ換えの回数に着目すると、7,8,9の実行回数を考えればよい。つまり、n*(n−1)/2とn*(n−1)/4である。今、nの値をとてつもなく大きくすることを考えると、−1が無視できn=n−1と考えられる。同様に、1/2も1/4もnがすごく大きい時には、無視できる。nが大きいとき7,8,9は、約n*n(n^2)回実行されると考えられる。よって、プログラムの計算量はO(n^2)であることが言える。

戻る

アプレットに戻る

a93sj030@j.dendai.ac.jp