LIST 4 (ラディックスソート)

/*------------------------------------------------------------------
        SORT 4  radix sort
--------------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_MEM   65535U
#define MAX_LINE  32767U

int loffset = 0;
unsigned short fsize,lcount = 0;
unsigned short *lp;
unsigned char *fbuff;

/*--- insert sort ---*/
void inssort(unsigned short *lp,int lower,int upper)
{
    int i,j;
    unsigned short tmpp;

    for (i = lower+1; i <= upper; i++) {
        tmpp = lp[i];
        for (j=i-1;j>=lower && strcmp(fbuff+tmpp,fbuff+lp[j])<0;j--)
            lp[j + 1] = lp[j];
        lp[j + 1] = tmpp;
    }
}

/*--- radix sort ---*/
void radsort(unsigned short *lp,int lower,int upper)
{
    int i;
    unsigned short *wlp;
    static int count[256];

    wlp = (unsigned short *)malloc(lcount * sizeof(unsigned short));
    for (i = 0; i <= 255; i++) count[i] = 0;
    for (i = lower; i <= upper; i++) count[*(fbuff+lp[i]+1)]++;
    for (i = 1; i <= 255; i++) count[i] += count[i-1];
    for (i = upper; i >= lower; i--) wlp[--count[*(fbuff+lp[i]+1)]]=lp[i];
    for (i = 0; i <= 255; i++) count[i] = 0;
    for (i = lower; i <= upper; i++) count[*(fbuff+wlp[i])]++;
    for (i = 1; i <= 255; i++) count[i] += count[i-1];
    for (i = upper; i >= lower; i--) lp[--count[*(fbuff+wlp[i])]]=wlp[i];
	free(wlp);
}

void read_data(FILE *fp)
{
    int llen, i = 0;
    unsigned short txtp = 0;
    unsigned char *tp;

    *fbuff++ = '\0';
    
    fsize = fread(fbuff,1,MAX_MEM-2,fp);
    fclose(fp);
    
    while (fsize > txtp) {
        lp[i++] = txtp;
        tp = strchr(fbuff+txtp,'\n');
        *tp = '\0';
        txtp =(unsigned short)(tp - fbuff)+1;
        lcount++;
    }
    lp[i++] = txtp;

    if (loffset > 0) {
        loffset--;
        for (i = 0; i < lcount; i++) {
            llen = lp[i+1] - lp[i] - 2;
            if (llen < loffset) lp[i] = lp[i+1]-2;
            else lp[i] += loffset;
        }
    }
}

void write_data(int reverse)
{
    int i;
    unsigned char *fpp;

    if (reverse)
        if (loffset > 0)
            for (i = lcount-1; i >=0; i--) {
                fpp = fbuff + lp[i] - 1;
                while (*fpp-- != '\0');
                fputs(fpp+2,stdout);
                fputc('\n',stdout);
            }   
        else
            for (i = lcount-1; i >=0; i--) {
                fputs(fbuff+lp[i],stdout);
                fputc('\n',stdout);
            }
    else
        if (loffset > 0)
            for (i = 0; i < lcount; i++) {
                fpp = fbuff + lp[i] - 1;
                while (*fpp-- != '\0');
                fputs(fpp+2,stdout);
                fputc('\n',stdout);
            }
        else
            for (i = 0; i < lcount; i++) {
                fputs(fbuff+lp[i],stdout);
                fputc('\n',stdout);
            }
}

int main(int argc,char *argv[])
{
    int i, reverse = 0;
    FILE *fp;

/*--- get parameter ---*/
    if (argc > 4) {
        fputs("Usage: hayasort [/R] [/+n] [filename]\n",stderr);
        exit(1);
    }

    fp = stdin;
    for (i = 1; i < argc; i++) {
        if (argv[i][0]=='-' || argv[i][0]=='/') {
            if (argv[i][1]=='+') loffset = atoi(argv[i]+2);
            else if (argv[i][1]=='r' || argv[i][1]=='R') reverse = 1;
        } else
            if ((fp = fopen(argv[i],"rt")) == NULL) {
                fputs("File not found\n",stderr);
                exit(1);
            }
    }

/*--- alloc memory ----*/
    fbuff = (unsigned char *)malloc(MAX_MEM);
    lp = (unsigned short *)malloc(MAX_LINE);

/*--- read data ----*/
    read_data(fp);

/*--- sort ---------*/
    radsort(lp,0,lcount - 1);
    inssort(lp,0,lcount - 1);

/*--- write data ---*/
    write_data(reverse);

    free(fbuff);
    free(lp);
    return 0;

}