さあ次は二分探索挿入ソート+バケツソートだ

バケツソート+単純挿入ソートの実装完了
キー値の生成の計算とかハッシュテーブルのアクセスとかいろいろカン違いしてた
gdbってアロケートされてるかされてないか正確にはわからないんだね
freeすんのめんどくせ

このコードにはバグがあります
mysort.c

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

struct NVtab
{
  int num;
  struct NVtab *next;
};

struct Lines
{
  unsigned int length;
  char **line;
};

enum
  {
    INIT = 4096,
    GROW = 2
  };

char* fileGetLine(FILE*);
static int endofline(FILE*, int);
void mysort(int*,int);
int main(int args, char *argv[])
{
  int i;
  char *line = NULL;
  struct Lines lines;
  int *nums = NULL;
  lines.length = 0;
  lines.line = NULL;
  FILE *f;
  if(argv[1] == NULL)
    {
      f = stdin;
    }
  else if((f = fopen(argv[1], "r")) == NULL)
    {
      fprintf(stderr, "ファイルがないよ\n");
      exit(1);
    }
  for (i = 0; (line = fileGetLine(f)) != NULL; i++)
    {
      lines.length += 1;
      lines.line = (char**)realloc (lines.line, sizeof(char*) * lines.length);
      lines.line[i] =  line;
    }

  for(i = 0; i < lines.length; i++)
    {
      nums = realloc(nums, sizeof(int) * i+1);
      nums[i] = atoi(lines.line[i]);
    }

  mysort(nums, lines.length);

  free(nums);
  for(i = 0; i < lines.length; i++)
    {
      free(lines.line[i]);
    }

  free(lines.line);
  return 0;
}
int hash(int num, int nhash)
{
  if(num < nhash)
    {
      return 0;
    }
  
  return (num / (1000 * 1000 * 10));
}


void mysort(int *nums, int len)
{
  int i, j;
  int h;
  int maxchain;
  int maenum;
  int nhash;
  struct NVtab **val;
  struct NVtab *newchain;
  struct NVtab *tmpchain;


  nhash = (1000 * 1000 * 10);

  val = (struct NVtab**)malloc(sizeof(struct NVtab*) * nhash);  
  for(i = 0; i < nhash; i++)
    {
      val[i] = NULL;
    }

  for(i = 0; i < len; i++)
    {
      h = hash(nums[i],nhash);
      newchain = (struct NVtab*)malloc(sizeof(struct NVtab));

      maenum = -1;

      for(tmpchain = val[h]; tmpchain != NULL; tmpchain = tmpchain->next)
	{
	  if(maenum < nums[i])
	    {
	      newchain->next = tmpchain->next;
	      tmpchain->next = newchain;
	      break;
	    }
	  maenum = tmpchain->num;
	}

      newchain->num = nums[i];
      
      if(tmpchain == NULL)
	{
	  newchain->next = NULL;
	  val[h] = newchain;
	}

      printf("%d\n",h);
    }

  for(i = 0; i < nhash; i++)
    {
      for(tmpchain = val[i]; tmpchain != NULL; tmpchain = tmpchain->next)
	{
	  printf("%d\n",tmpchain->num);
	}
    }

  maxchain = 0;
  for(i = 0; i < nhash; i++)
    {
      j = 0;
      for (tmpchain = val[i]; tmpchain != NULL; tmpchain = tmpchain->next)
	{
	  j++;
	}
      if(maxchain < j)
	{
	  maxchain = j;
	}
    }
  fprintf(stderr, "%d\n", maxchain);
}

char* fileGetLine(FILE *fin)
{
  int i, c;
  int maxline = INIT;
  char *line = (char*)malloc (sizeof(char) * maxline);

  for (i = 0;(c = getc(fin)) != EOF && !(endofline(fin, c)); i++)
    {
      if (i >= maxline - 1)
	{
	  maxline *= GROW;
	  line = (char*) realloc(line, sizeof(char) * maxline);
	}
      line[i] = (char)c;
    }

  return (c == EOF && i == 0) ? NULL : line;
}

static int endofline(FILE *fin, int c)
{
  int eol;
  eol = (c == '\r' || c == '\n');

  if (c == '\r')
    {
      c = getc(fin);
      if (c != '\n' && c != EOF)
	{
	  ungetc(c, fin);
	}
    }
  return eol;
}