LIST 3 (クイックソート 基準要素改良版)

/*------------------------------------------------------------------
        SORT 3  quick sort 2
--------------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

extern _stklen = 32767U;

#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;
    }
}

/*--- quick sort 2 ---*/
void quicksort2(unsigned short *lp,int lower,int upper)
{
    int i,j;
    static int t;
    static unsigned short tmpp,x1,x2,x3,xd;
	static unsigned char *xp;

	xd = upper - lower;
	if (xd <= 16) return;
	
    x1 = lp[lower + (xd>>2)];
    x2 = lp[lower + (xd>>1)];
    x3 = lp[lower + (xd>>1)+(xd>>2)];
    
    if (strcmp(fbuff+x1, fbuff+x2) > 0) {
    	tmpp = x1; x1 = x2; x2 = tmpp;
    } 
    if (strcmp(fbuff+x1, fbuff+x3) > 0) {
    	tmpp = x1; x1 = x3; x3 = tmpp;
    } 
    if (strcmp(fbuff+x2, fbuff+x3) > 0) {
    	tmpp = x2; x2 = x3; x3 = tmpp;
    } 
	
	xp = fbuff + x2;
	i = lower; j = upper;
	for (;;) {    
		while ((t = strcmp(xp, fbuff+lp[i])) >= 0) {
			if (t == 0)
			    if (xp <= fbuff+lp[i]) break;
			i++;
		}
			
		while ((t = strcmp(xp, fbuff+lp[j])) <= 0) {
			if (t == 0)
				if (xp >= fbuff+lp[j]) break;
			j--;
		}
        
        if (i >= j) break;
        tmpp = lp[i]; lp[i] = lp[j]; lp[j] = tmpp;
        i++; j--;
    }
	if (lower < i - 1) quicksort2(lp, lower, i - 1);
	if (upper > j + 1) quicksort2(lp, j + 1, upper);
	
}


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 ---------*/
    quicksort2(lp,0,lcount - 1);
    inssort(lp,0,lcount - 1);

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

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

}