Mega Code Archive

 

Categories / C / Data Structure Algorithm

 

A Quicksort for files

/* C: The Complete Reference, 4th Ed. (Paperback) by Herbert Schildt ISBN: 0072121246 Publisher: McGraw-Hill Osborne Media; 4 edition (April 26, 2000) */ #include <stdio.h> #include <stdlib.h> #include <string.h> #define NUM_ELEMENTS 4  /* This is an arbitrary number                            that should be determined                            dynamically for each list. */ struct address {   char name[30];   char street[40];   char city[20];   char state[3];   char zip[11]; } ainfo; struct address addrs[NUM_ELEMENTS] = {   "A. Alexander", "101 1st St", "Olney", "Ga", "55555",   "B. Bertrand", "22 2nd Ave", "Oakland", "Pa", "34232",   "C. Carlisle", "33 3rd Blvd", "Ava", "Or", "92000",   "D. Dodger", "4 Fourth Dr", "Fresno", "Mi", "45678" }; void quick_disk(FILE *fp, int count); void qs_disk(FILE *fp, int left, int right); void swap_all_fields(FILE *fp, long i, long j); char *get_zip(FILE *fp, long rec); int main(void) {   FILE *fp;   /* first, create a file to sort */   if((fp=fopen("mlist", "wb"))==NULL) {     printf("Cannot open file for write.\n");     exit(1);   }   printf("Writing unsorted data to disk.\n");   fwrite(addrs, sizeof(addrs), 1, fp);   fclose(fp);   /* now, sort the file */   if((fp=fopen("mlist", "rb+"))==NULL) {     printf("Cannot open file for read/write.\n");     exit(1);   }   printf("Sorting disk file.\n");   quick_disk(fp, NUM_ELEMENTS);   fclose(fp);   printf("List sorted.\n");   return 0; } /* A Quicksort for files. */ void quick_disk(FILE *fp, int count) {   qs_disk(fp, 0, count-1); } void qs_disk(FILE *fp, int left, int right) {   long int i, j;   char x[100];   i = left; j = right;   strcpy(x, get_zip(fp, (long)(i+j)/2)); /* get the middle zip */   do {     while((strcmp(get_zip(fp,i),x) < 0) && (i < right)) i++;     while((strcmp(get_zip(fp,j),x) > 0) && (j > left)) j--;     if(i <= j) {       swap_all_fields(fp, i, j);       i++; j--;     }   } while(i <= j);   if(left < j) qs_disk(fp, left, (int) j);   if(i < right) qs_disk(fp, (int) i, right); } void swap_all_fields(FILE *fp, long i, long j) {   char a[sizeof(ainfo)], b[sizeof(ainfo)];   /* first read in record i and j */   fseek(fp, sizeof(ainfo)*i, SEEK_SET);   fread(a, sizeof(ainfo), 1, fp);   fseek(fp, sizeof(ainfo)*j, SEEK_SET);   fread(b, sizeof(ainfo), 1, fp);   /* then write them back in opposite slots */   fseek(fp, sizeof(ainfo)*j, SEEK_SET);   fwrite(a, sizeof(ainfo), 1, fp);   fseek(fp, sizeof(ainfo)*i, SEEK_SET);   fwrite(b, sizeof(ainfo), 1, fp); } /* Return a pointer to the zip code */ char *get_zip(FILE *fp, long rec) {   struct address *p;   p = &ainfo;   fseek(fp, rec*sizeof(ainfo), SEEK_SET);   fread(p, sizeof(ainfo), 1, fp);   return ainfo.zip; }