第四回レポート総評



sort_func 関数に関して

やや長いですが、プログラム本体の正解例を書いておきます。 
#include <stdio.h>
#include <stdlib.h>

#define SIZE 10000

void swap_r(int &x, int &y);

void sort_func(int *x, int N);

int main(void){

  int x[SIZE];

  srand(1);
  for(int i=0 ; i<SIZE ; i++){
    x[i] = rand()%SIZE;
  }

/*  printf("--------before--------\n");
  for(int i=0 ; i<SIZE ; i++){
    printf("%d\n",x[i]);
  }*/

  sort_func(x,SIZE);

/*  printf("--------after--------\n");
  for(int i=0 ; i<SIZE ; i++){
    printf("%d\n",x[i]);
  }*/

  printf("done.\n");

  return 0;

}

void swap_r(int &x, int &y){
  int tmp;

  tmp = y;
  y = x;
  x = tmp;

}

void sort_func(int *x, int N){

  for(int i=0 ; i<N-1 ; i++){
    for(int j=i+1 ; j<N ; j++){
      if(x[j] < x[i]){
	swap_r(x[i], x[j]);
      }
    }
  }

}
もちろん、ポイントになるのは sort_func 関数の内部です。
上の sort_func 関数の記述が、第四回資料の図 3 に対応していることは 理解しておいて下さい。

なお、for 文の条件が 

  for(int i=0 ; i<N ; i++){  /* ← N-1 が N になっている */
    for(int j=i+1 ; j<N ; j++){


になっている人がいましたが、これは問題ありません。
(i=N-1 のときは j に関する for 文の内部が実行されないため)

また、for 文の条件が 

  for(int i=0 ; i<N-1 ; i++){
    for(int j=i ; j<N ; j++){  /* ← i+1 が i になっている */


になっている人もいました。これも正しく動作するので問題ないのですが、
i=j の時 (つまり x[i] と x[i] ) も比較されていることは注意しておいた方が良いでしょう。

さらに、 

  for(int i=0 ; i<N-2 ; i++){
    for(int j=i+1 ; j<N-1 ; j++){


となっている人がいました。これは、x[N-2] と x[N-1] が比較されないので間違いです。なお、以下のように「＜」ではなく「＜＝」を用いれば正解になります。 

  for(int i=0 ; i<=N-2 ; i++){
    for(int j=i+1 ; j<=N-1 ; j++){


他にも、for 文の条件の間違いはいろいろありました。
正解例と自分のプログラムを良く比較しておいて下さい。

致命的な間違いとしては以下のものがありました。 なお、参照引数の swap_r ではなく、ポインタ引数の swap_p を用いる場合は 

	swap_p(&x[i], &x[j]);


のように呼び出すことになります。興味のある人はなぜこのような記述になるか 考えてみて下さい。

sort_func 関数の計算時間について

SIZE を 10000 まで調べて見るようにいいましたが、20000、30000 くらいまで 実行した方がクイックソートとの違いが良く分かったかもしれません。

sort_func 関数の比較回数

上記 sort_func 関数の比較回数は、 

(N-1) + (N-2) + … + 1 = N(N-1)/2


になります。

N が大きい時は N2 の項の影響が強く現れるため、 この sort_func は「オーダー N2」のアルゴリズムである、 などと呼ばれます。

それに対し、クイックソートは (平均的に) オーダー N logN のアルゴリズム です。

なお、フーリエ変換を高速に行うアルゴリズムとして FFT (Fast Fourier Transform) が知られていますが、FFT もオーダー N logN です。

また、言い忘れましたが N logN の log の底は 2 (すなわち N log2N) です)。
とは言っても、log2N = logaN/loga2 であり、計算のオーダーを考える場合、定数は重要ではないので、 底の違いはあまり気にする必要はないのですが。

最後に

というわけで、選択ソート (課題 1 の sort_func) よりも クイックソート (課題 2 。標準ライブラリ) の方が効率が良いことが 体感してもらえたと思います。

ただ、今回の例だけでは「ライブラリは万能である」というような印象を与えてしまったかも知れません。

しかし、実際に (卒論などで) プログラムを書く際、 そのプログラムに必要なアルゴリズムがライブラリに 含まれているとは限りません。

その場合、有効なアルゴリズムが存在するかどうかアルゴリズムの教科書などで調べ、
そのアルゴリズムを自分でプログラミングすることが必要となります。
その際には「課題 1」で行ったようなプログラミングをすることになるでしょう。 (システムの授業はそのような授業になっています)

もちろん、有効なアルゴリズムが存在しないことも多くあるでしょう。
その場合は、1 日、1 週間、場合によっては 1 ヵ月以上 (！) プログラムを 動かし続けて結果を得ることもあります。


C から入る C++ に戻る