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

オライリーから出ているBeautiful Codeを一日中読んでいた。

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

さくさく読み進めれる本ではないし、通勤電車の中で読み進めれるような本ではないので、この連休中にまとめて読むことにする。でも、あんまり休めないんだよなぁ。夜ちょっと早く帰って読み進めるのが関の山かな？

で、現在第三章。クイックソートに関する記事なのだが、ちょうど良い機会だ。久しぶりにC言語のソースを書いてみることにする。とりあえず、例3-1で示されたソースの完全版。

#include <stdio.h>
#include <stdlib.h>

#define LIST_MAX 100

int list[LIST_MAX];

void swap(int *a,int *b);
void swap2(int i,int j);
void quicksort(int l,int u);

int randint(int min,int max);

int main(void)
{
  int i = 0;
  int new_i;

  for( i = 0 ; i < LIST_MAX ; i++ ){
    list[i] = i;
  }

  for( i = 0 ; i < LIST_MAX ; i++ ){
    new_i = rand() / (RAND_MAX / LIST_MAX + 1);
    swap(list+i,list+new_i);
  }

  for( i = 0 ; i < LIST_MAX ; i++ ){
    printf("[before]i = %d , list[i] = %d\n",i,list[i]);
  }

  quicksort(0,LIST_MAX - 1);

  for( i = 0 ; i < LIST_MAX ; i++ ){
    printf("[after]i = %d , list[i] = %d\n",i,list[i]);
  }

  return 0;

}

void swap(int *a,int *b){
  int tmp;
  tmp = *a;
  *a = *b;
  *b = tmp;
}

int randint(int min,int max){
  int tmp = min + (int)(rand()*(max-min+1.0)/(1.0+RAND_MAX));
  return tmp;
}

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++ ){
    if(list[i] < list[l]){
      ++m;
      swap2(m,i);
    }
  }
  swap2(l,m);
  quicksort(l,m-1);
  quicksort(m+1,u);
}

void swap2(int i,int j){
  int tmp = list[i];
  list[i] = list[j];
  list[j] = tmp;
}

うん。汚いけど、とりあえずこれで進めよう。気力が続けば、続きます。