home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
The Fred Fish Collection 1.5
/
ffcollection-1-5-1992-11.iso
/
ff_disks
/
300-399
/
ff306.lzh
/
Tree
/
sort.c
< prev
next >
Wrap
C/C++ Source or Header
|
1990-01-11
|
5KB
|
214 lines
/*
* A quicksort routine; nothing special. Only works on machines
* which store the most significant byte of a longword in the
* first byte, and so on.
*/
#include "stdio.h"
char **lineptrs ;
long numlines ;
long lineptrsize ;
char inbuf[255] ;
char **ssmin[25], **ssmax[25] ;
int stval ;
void *lmalloc() ;
#define MEMCHUNK 4096
#define swap(a, b) {t= a;a= b;b= t;}
char *tbuf ;
int bytesleft ;
int reverse ;
char *saveit(s)
register char *s ;
{
int len = (strlen(s) + (2*sizeof(long)-1)) & ~(sizeof(long)-1) ;
register char *p ;
if (len > bytesleft) {
tbuf = (char *)lmalloc((long)MEMCHUNK) ;
if (tbuf == NULL)
error("! couldn't allocate memory") ;
bytesleft = MEMCHUNK ;
}
p = tbuf ;
while (*p++ = *s++) ;
s = tbuf ;
tbuf += len ;
while (p < tbuf)
*p++ = 0 ;
bytesleft -= len ;
return(s) ;
}
long strlcmp(a, b)
register long *a, *b ;
{
while (*a == *b && *a) {
a++ ;
b++ ;
}
return(*b - *a) ;
}
error(s)
char *s ;
{
fputs("sort: ", stdout) ;
puts(s) ;
if (*s == '!')
exit(1) ;
}
getlines() {
register int c ;
register char *p ;
register long i ;
char **olineptrs ;
lineptrsize = 0 ;
numlines = 0 ;
while (1) {
p = inbuf ;
while ((c=getchar())!=EOF && c != 10) {
*p++ = c ;
if (p > inbuf + 250)
error("! input line too long") ;
}
*p = 0 ;
if (c==EOF && p==inbuf)
break ;
p = saveit(inbuf) ;
if (numlines >= lineptrsize) {
olineptrs = lineptrs ;
lineptrsize = lineptrsize + (MEMCHUNK/sizeof(char *)) ;
lineptrs = (char **)lmalloc((long)sizeof(char *)*lineptrsize) ;
if (lineptrs == NULL)
error("! couldn't allocate memory") ;
for (i=0; i<lineptrsize-MEMCHUNK/sizeof(char *); i++)
lineptrs[i] = olineptrs[i] ;
free(olineptrs) ;
}
lineptrs[numlines++] = p ;
}
}
sortlines() {
register char **i, **j ;
register char *medp ;
char **min, **max, **med ;
register char *t ;
stval = 0 ;
min = lineptrs ;
max = lineptrs + numlines - 1 ;
while (1) {
if (max < min + 3) {
if (max > min) {
if (strlcmp(*max, *min)<0)
swap(*max, *min) ;
if (max == min + 2) {
if (strlcmp(*(min+1), *min)<0)
swap(*(min+1),*min) ;
if (strlcmp(*max, *(min+1))<0)
swap(*max,*(min+1)) ;
}
}
if (stval > 0) {
stval-- ;
min = ssmin[stval] ;
max = ssmax[stval] ;
} else
break ;
} else {
med = min + (max - min) / 2 ;
if (strlcmp(*max, *min)<0)
swap(*max, *min) ;
if (strlcmp(*med, *min)<0)
swap(*med, *min) ;
if (strlcmp(*max, *med)<0)
swap(*max, *med) ;
i = min + 1 ;
j = max - 1 ;
medp = *med ;
while (1) {
if (strlcmp(medp, *i)>=0) {
i++ ;
if (i>j)
break ;
} else
goto checkj ;
if (strlcmp(*j, medp)>=0) {
j-- ;
if (i>j)
break ;
} else
goto checki ;
continue ;
checki:
while (strlcmp(medp, *i)>=0 && i<=j)
i++ ;
goto over ;
checkj:
while (strlcmp(*j, medp)>=0 && i<=j)
j-- ;
over:
if (i < j) {
swap(*i, *j)
i++ ;
j-- ;
if (i>j)
break ;
} else
break ;
}
if (j-min > max-i) {
ssmin[stval] = min ;
ssmax[stval] = j ;
stval++ ;
min = i ;
} else {
ssmin[stval] = i ;
ssmax[stval] = max ;
stval++ ;
max = j ;
}
}
}
}
putlines() {
register long i ;
if (reverse)
for (i=0; i<numlines; i++)
puts(lineptrs[i]) ;
else
for (i=numlines-1; i>=0; i--)
puts(lineptrs[i]) ;
}
main(argc, argv)
int argc ;
char *argv[] ;
{
while (argc > 1 && argv[1][0]=='-') {
argc-- ;
argv++ ;
switch(argv[0][1]) {
case 'r' : reverse = 1 ;
break ;
default : break ;
}
}
if (argc > 1) {
argc-- ;
argv++ ;
if (freopen(argv[0], "r", stdin) == NULL)
error("! couldn't open input file") ;
}
if (argc > 1) {
argc-- ;
argv++ ;
if (freopen(argv[0], "w", stdout) == NULL)
error("! couldn't open output file") ;
}
getlines() ;
if (numlines > 1)
sortlines() ;
putlines() ;
fclose(stdout) ;
}
_wb_parse() {}