ビューティフルコードを読み進める その2

ビューティフルコード (THEORY/IN/PRACTICE)

ビューティフルコード (THEORY/IN/PRACTICE)

3章を読み進めて分からなかったのは例3-2から。この章の本質は、配列の大きさNに対して計算量がどのぐらいか、メモリ使用量はどのぐらいかを求めることで、ソートができるかどうかは二の次であるということだ。

という前提を心にとめておいて、話を進めてみると例3-2のソース(該当関数部分のみ)は以下のようになる。

void quicksort(int l,int u){
  int i,m,tmp;
  if( l >= u ){
    return;
  }
  tmp = randint(l,u);
  swap2(l,tmp);
  m = l;
  for( i = l+1 ; i <= u ; i++ ){
    comps++;
    if(list[i] < list[l]){
      ++m;
      swap2(m,i);
    }
  }
  swap2(l,m);
  quicksort(l,m-1);
  quicksort(m+1,u);
}

ここで、compsが計算回数を計算するグローバル変数。で、毎回毎回+1するのではなくて、for文では計算する回数は決まっている。終了条件-開始条件で計算回数は求められるので、compsを外に出してやれば計算回数は1回で済む。これが例3-3。

void quicksort(int l,int u){
  int i,m,tmp;
  if( l >= u ){
    return;
  }
  tmp = randint(l,u);
  swap2(l,tmp);
  m = l;
  comps += u-l;
  for( i = l+1 ; i <= u ; i++ ){
    if(list[i] < list[l]){
      ++m;
      swap2(m,i);
    }
  }
  swap2(l,m);
  quicksort(l,m-1);
  quicksort(m+1,u);
}

とりあえず、今日はここまで。この章を読み進めるのに、クイックソートの正しさではなく、計算量だけに焦点を定めることに気がつくのがポイント。