home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Power Programming
/
powerprogramming1994.iso
/
progtool
/
pctech
/
hlsrc.arc
/
HLSRTSUB.C
< prev
next >
Wrap
C/C++ Source or Header
|
1988-09-09
|
2KB
|
65 lines
/*+
Name: HLSRTSUB.C
Author: Kent J. Quirk
(c) Copyright 1988 Ziff Communications Co.
Abstract: This file contains a relatively general-purpose Shell sort
routine for files of fixed-length records. It is completely
disk based, and has no particular limitations, except speed.
(But since we're using it to test disk I/O, we almost want it
to be slow. We certainly want it to be diskbound.)
History: 09-Sep-88 kjq Version 1.00
-*/
#include <stdio.h>
#include <stdlib.h>
#define ALLOC_ITEM(v,sz) if ((v = malloc(sz)) == NULL) exit(1)
#define READREC(v,f,n,sz) fseek(f, (n)*(long)(sz), SEEK_SET); \
fread(v, sz, 1, f); rd_cnt++
#define WRITEREC(v,f,n,sz) fseek(f, (n)*(long)(sz), SEEK_SET); \
fwrite(v, sz, 1, f); wt_cnt++
long rd_cnt=0L;
long wt_cnt=0L;
void shellsort(f, nrecs, recsize, compare)
FILE *f;
long nrecs;
int recsize;
int (*compare)();
{
long i,j,h;
char *v, *t;
ALLOC_ITEM(v,recsize);
ALLOC_ITEM(t, recsize);
for (h=1; h<nrecs; h = 3*h + 1)
; /* calculate starting h */
do
{
h /= 3;
for (i=h; i<nrecs; i++)
{
READREC(v, f, i, recsize); /* a[i] is in v */
j = i;
READREC(t, f, j-h, recsize); /* a[j-h] is in t */
while((*compare)(t,v) > 0)
{
WRITEREC(t, f, j, recsize); /* write a[j] */
j = j-h;
if (j < h)
break;
READREC(t, f, j-h, recsize); /* read new element */
}
WRITEREC(v, f, j, recsize); /* write the last */
}
} while (h > 1); /* end of do loop */
free(v);
free(t);
printf("Shellsort: %ld reads, %ld writes.\n", rd_cnt, wt_cnt);
}