壊れたクイックソート
仕事で海外に出ていて時間があいてしまった。こういうことって一度途切れると中断時間の1.5乗に比例してやる気がなくなる。もっとエントリの粒度を下げたほうがやる気が出そうなので、中途半端でもともかく更新を続けることを優先してみる。
最後にやろうとしていたのは、自分でソートを試してみるということだった。クイックソートをやって、pthreadでそれを2コアに分散できるのか試してみたい。もしかして先に2つに分けてクイックソートしてからマージソートがいいのかな、とか。
ところが、いきなりクイックソートでつまづいたらしい。原理はよく分かったしと思って自分で書いてみたら、ちゃんと動かない。何だか境界条件辺りでおかしなことになっているらしく、ソート後の配列に変な値が1つ混じるし、大きな配列になると無茶苦茶時間がかかってる感じ。
#include <stdio.h> #include <stdlib.h> #define SWAP(type, x, y) do {type tmp = x; x = y; y = tmp;}while(0) int myqsort(int ary[], int begin, int end) { int left = begin; int right = end; int tmp; if (left >= right) { return -1; } int pivot = ary[(left + right) / 2]; while (1) { while(ary[left] < pivot) { left++; } while(ary[right] > pivot) { right--; } if (left >= right) { break; } SWAP(int, ary[left], ary[right]); left++; right--; } if (left - begin >= 2) { myqsort(ary, 0, left - 1); } if (end - right >= 2) { myqsort(ary, right + 1, end); } } int show_ary(int ary[], int size) { int i; for (i = 0; i < size; i++) { printf("%d:", ary[i]); } printf("\n"); } int main (int argc, char *argv[]) { // int x[] = {13, 12, 4, 2, 7, 8, 9, 5, 10, 1, 6, 3, 11}; // int size = sizeof(x) / sizeof(int); int size; if (argc < 1) exit(1); size = atoi(argv[1]); int x[size], i, r; for (i = 0; i < size; i++) { x[i] = rand() % size; } show_ary(x, size); myqsort(x, 0, size); printf("--sort--\n"); show_ary(x, size); }