壊れたクイックソート

仕事で海外に出ていて時間があいてしまった。こういうことって一度途切れると中断時間の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);
}