ビューティフルコード (THEORY/IN/PRACTICE)
- 作者: Brian Kernighan,Jon Bentley,まつもとゆきひろ,Andy Oram,Greg Wilson,久野禎子,久野靖
- 出版社/メーカー: オライリージャパン
- 発売日: 2008/04/23
- メディア: 大型本
- 購入: 30人 クリック: 617回
- この商品を含むブログ (171件) を見る
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); }
とりあえず、今日はここまで。この章を読み進めるのに、クイックソートの正しさではなく、計算量だけに焦点を定めることに気がつくのがポイント。