先日、知人の大学生にソートプログラムの課題についての相談を受けました。ASCIIテキストのみのワードリストファイルを入力し、ソートして出力するという簡単なものだったので、そこそこ早くてかつコードがシンプルなコムソート(comb sort)でコーディングしてみました。

combsort.c (Gist)

#include <stdio.h>
#include <stdlib.h>
// #include <string.h>

#ifndef _STRING_H
int strlen(const char* s)
{
  int i = 0;
  while (s[++i])
    ;
  return i;
}
int strcpy(char* a, const char* b)
{
  for (; *b; a++,b++) {
    *a = *b;
  }
  return *a = 0;
}
int strcmp(const char* a, const char* b)
{
  while ((*a || *b) && *a == *b) {
    a++, b++;
  }
  return *a - *b;
}
#endif

int main(int ac, char** av)
{
  int i, j, k;
  int s;
  char b[1024];
  char** d;
  char* c;

  // ファイル名が指定されなかったら標準入力を読む
  FILE* f = stdin;
  if (ac == 2 && (f = fopen(av[1], "r")) == NULL) {
    fprintf(stderr, "Failed to open file: %s", av[1]);
    return 1;
  }

  // バッファに読み込む
  for (s = 0; fgets(b, sizeof(b), f) != NULL; s++) {
    if (strlen(b)) {
      b[strlen(b) - 1] = '\0'; // chomp
    }
    d = (char**)(s ? realloc(d, sizeof(char*)*(s + 1)) : malloc(sizeof(char*)));
    d[s] = (char*)malloc(sizeof(b));
    strcpy(d[s], b);
  }

  // コムソート実行
  i = s * 10 / 13;
  for (;;) {
    j = 0;
    for (k = 0; k + i < s; k++) {
      if (strcmp(d[k], d[k + i]) > 0) {
        c = d[k];
        d[k] = d[k + i];
        d[k + i] = c;
        j++;
      }
    }
    if (i == 1) {
      if (!j) {
        break;
      }
    }
    else {
      i = i * 10 / 13;
    }
  }

  // 印字
  for (i = 0; i < s; i++) {
    printf("%s\n", d[i]);
  }

  if (s) {
    free(d);
  }
  if (f != stdin) {
    fclose(f);
  }

  return 0;
}

大学の課題ということで、ひょっとしてstring.hすら使えないんじゃないかな、と思い strlen()、strcpy()、strcmp()も自前で準備してみました。これらの文字列用の関数は ASCII 文字列に対しては動いてはいるものの、変なものを食わせたらすぐにお腹を壊すと思います。 使い方は、標準入力にワードリストを食わせてやるか、オプションにリストのパスを指定します。

gcc -o csort csort.c
./csort < wordlist.dic
abc
bbb
dcc
# もしくは ./csort wordlist.dic