My Linux Diary : クイックソート

Link クイックソート

　学校の宿題でC言語標準装備のクイックソートを作れというのがあった。
　仕様は void my_qsort(void *base, size_t num, size_t width, int (*compare)(char*,char*)) であるがvoid型のポインタの処理が結構難しかった。

　スワップ関数

void my_swap(void *base, int x, int y, size_t width){
　　char *temp = (char*)malloc(width);
　　memcpy(temp,base+x*width,width);
　　memcpy(base+x*width,base+y*width,width);
　　memcpy(base+y*width,temp,width);
　　free(temp);
}

　left番目からright番目までrightを基準値にして大小を分割する関数

int partition(void *base, size_t width, int left, int right, int (*compare)(char*, char*)){
　　int i,j;
　　i = left - 1;
　　j = right;
　　char *pivot = (char*)(base+right*width);
　　while(1){
　　　　while((*compare)((char*)(base+(++i)*width),pivot) < 0)
　　　　;
　　　　while(i < j-- && (*compare)(pivot,(char*)(base+j*width)) < 0)
　　　　;
　　　　if(i >= j)
　　　　　　break;
　　　　my_swap(base,i,j,width);
　　}
　　my_swap(base,i,right,width);
　　return i;
}

　クイックソート本体 　

void my_qsort(void *base, size_t num, size_t width, int (*compare)(char*, char*)){
　　int right,left,mid,sp;
　　int low[STACK_SIZE], high[STACK_SIZE];

　　low[0] = 0;
　　high[0] = num - 1;
　　sp = 1; 　　while(sp > 0){
　　　　sp--;
　　　　left = low[sp];
　　　　right = high[sp];
　　　　if(left > right)
　　　　;
　　　　else{
　　　　　　mid = partition(base,width,left,right,compare);
　　　　　　if(mid - left < right - mid){
　　　　　　　　low[sp] = mid +1;
　　　　　　　　high[sp++] = right;
　　　　　　　　low[sp] = left;
　　　　　　　　high[sp++] = mid - 1;
　　　　　　} else{
　　　　　　　　low[sp] = left;
　　　　　　　　high[sp++] = mid - 1;
　　　　　　　　low[sp] = mid + 1;
　　　　　　　　high[sp++] = right;
　　　　　　}
　　　　}
　　}
}

2004,11,07 : 16:49 | 修正 | コメント (0)

Comments

::Comment::