2つに分けてソートしてからマージソート
与えられた配列を真ん中で2つに分けて、それぞれを並列にクイックソートしてからマージソートするという方針で書いてみた。といいつつ並列化のところだけ後回し。配列が自分の長さを知らないなんておかしいぞと思ったので、arrayという構造体を定義してみた。しかし、1つのメモリ上のオブジェクトを仮想的に分割して2つのオブジェクトに見立てたりして、なんかお行儀悪い感じ。
#include <stdio.h> #include <stdlib.h> #include <time.h> #include <pthread.h> #define INIT_NUM 0 #define SWAP(type, x, y) do {type tmp = x; x = y; y = tmp;}while(0) typedef struct { int *ary; int size; } array; array *init_array(int size) { array *ptr; int i; ptr = (array *)malloc(sizeof(array)); ptr->ary = (int *)malloc(sizeof(int)*size); ptr->size = size; for (i = 0; i < size; i++) { ptr->ary[i] = INIT_NUM; } return ptr; } void show_array(array *p) { int i; for (i = 0; i < p->size; i++) { printf("%d:", p->ary[i]); } printf("\n"); } void set_random(array *p) { int i; for (i = 0; i < p->size; i++) { p->ary[i] = (rand() % 100); } } int intcmp(const void *a, const void *b) { return (*(int *)a > *(int *)b); } 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, begin, left - 1); } if (end - right >= 2) { myqsort(ary, right + 1, end); } } array *msort(array *p1, array *p2) { array *new; int i, j, k; i = j = k = 0; new = init_array(p1->size + p2->size); while ((i < p1->size) && (j < p2->size)) { if (p1->ary[i] < p2->ary[j]) { new->ary[k++] = p1->ary[i++]; } else { new->ary[k++] = p2->ary[j++]; } } while (i < p1->size) new->ary[k++] = p1->ary[i++]; while (j < p2->size) new->ary[k++] = p2->ary[j++]; return new; } array *psort(array *p) { int center; array *a, *b, *c; int ret1, ret2; a = (array *)malloc(sizeof(array)); b = (array *)malloc(sizeof(array)); if (p->size == 1) return; if (p->size < 10) { qsort(p->ary, p->size, sizeof(int), intcmp); } center = p->size / 2; a->ary = p->ary; a->size = center; b->ary = p->ary + center; b->size = p->size - center; myqsort(a->ary, 0, a->size - 1); // This can be parallelized. myqsort(b->ary, 0, b->size - 1); // c = msort(a, b); free(a); free(b); return c; } int main (int argc, char *argv[]) { array *a, *b, *c; int i, j, size; srand(time(NULL)); if (argc <= 1) { printf("we need an int parameter\n"); exit(1); } size = atoi(argv[1]); a = init_array(size); set_random(a); show_array(a); c = psort(a); show_array(c); }