直ったクイックソートとテスト

人間の心理って（って自分の心理だけど）、すごく不思議だ。「そういえばmyqsort.cを書いてみたはいいけど動かなかったなー、何が悪いのか分からんし、どう手をつけていいのかも分からんしなぁ」と思って放置していた。ものすごくイヤーな印象だけが残って、コードを見る気にもならなくなっていた。

ところが、いざ日記にして再び強制的にコードを見て実行してみると、たいしたことなさそうな気がしてきて、実際、少し考えてみたらたいしたことがなかった。

1つめの問題は、配列の領域を超えてアクセスしていることだった。ソートする関数の宣言あたりは、

int myqsort(int ary[], int begin, int end) {
  int left = begin;
  int right = end;
  int tmp;

となっているのに呼び出し側は、

myqsort(x, 0, size);

となっていた。典型的な（？）、インデックスアクセスの添字の問題。サイズが10のときの最大の添字は9だから、

myqsort(x, 0, size - 1);

として呼び出すのが正解だった。

これで直ってふつうにソートできてるように見えたけど、配列サイズが90を超えたあたりから、急激にソートに時間がかかるようになった。これもよくよく読み直してみたら、

  if (left - begin >= 2) {
    myqsort(ary, 0, left - 1);
  }
  if (end - right >= 2) {
    myqsort(ary, right + 1, end);
  }

と再帰の呼び出し時の引数がおかしいことに気づいた。2行目は、

myqsort(ary, begin, left - 1);

と、0じゃなくてbeginとしないと、毎回配列のはじっこまで見ることになってしまっておかしかった。

動いたので、今度はテストを書いてみた。qsort(3)は信用していいだろうということで、標準qsortの結果と比べるようにしてみた。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <assert.h>
#include <stdbool.h>
#include "mysort.h"

#define SIZE 100
#define LOOP 1000

int test_qsort (int ary[], int size) {
  int ary1[size], ary2[size];

  memcpy(ary1, ary, sizeof(int)*size);
  memcpy(ary2, ary, sizeof(int)*size);

  myqsort(ary1, 0, size - 1);
  qsort(ary2, size, sizeof(int), isLarger);

  return memcmp(ary1, ary2, sizeof(int)*size);
}

bool test_rand (void) {
  int size = SIZE, test_loop = LOOP, res = 0;
  int ary[size], i;

  while (test_loop--) {

    for (i = 0; i < size; i++) {
      ary[i] = rand() % size;
    }
    res += test_qsort(ary, size);
  }

  if (res == 0) {
    return true;
  } else {
    return false;
  }
}

bool test_same (void) {
  int size = SIZE, test_loop = LOOP, res = 0;
  int ary[size], i, val;

  while (test_loop--) {

    val = rand() % size;

    for (i = 0; i < size; i++) {
      ary[i] = val;
    }
    res += test_qsort(ary, size);
  }

  if (res == 0) {
    return true;
  } else {
    return false;
  }
}

int main (int argc, char *argv[]) {

  srand(time(NULL));

  assert(test_rand());
  assert(test_same());

}

とりあえずランダムな配列と、すべてが同値の配列のパターンをチェック。

ソートのテストなら、昇順、降順とか「010101」のようなシマシマパターン、「00001111」のような領域パターンをテストすれば充分という気もする。どっちにしてもこういうテストパターンはRubyとかで生成するほうが生産的だろうなあ。