A simple example of quick sort of disk files in C language

A simple example of quick sort of disk files in the C language

Quicksort (quick sort), invented and named by C.A.R.Hoare, is considered to be one of the best sorting algorithms available. Quicksort is based on exchange sort, which is very effective compared with bubble sort based on exchange sort.

Its basic idea is: through 1 visit to sort to sort data split into separate two parts, one part of all the data than the other one part of all data, and then of the two parts data respectively according to the method of quick sort, the entire sorting process can be recursive, to achieve the whole data into an orderly sequence.

In this example, quicksort is achieved by repeatedly calling the sorting function qs_disk(FILE* fp,int left,int right) in the function quick_disk(FILE* fp,int count). In qs_disk(), the function get_name(fp,(long))(i+j)/2 returns the middle value as the comparison number for quicksort.

The following is the specific source code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define NUM 4
 
struct data
{
  char name[20];
  char school[20];
  char city[20];
  char province[20];
}info;
 
struct data addrs[NUM]=
{
  "OKBase","BIT","JiLin","JiLin",
  "TongWei","BIT","ZhengJiang","JiangSu",
  "SunYou","BIT","WeiFang","ShangDong",
  "XiaoMing","PKU","TaiYuan","ShanXi"
 
};
/* Declare the function to be used later */
void quick_disk(FILE *fp,int count);
void qs_disk(FILE *fp,int left,int right);
void exchangedata(FILE *fp,long i, long j);
char *get_name(FILE *fp, long rec);
void print_data(struct data *p);
struct data *get_data(FILE *fp,long rec);
 
int main(void)
{
  int i;
  FILE *fp;          /* The file pointer */
  /* Generates text files as reads and writes fp*/
  if((fp = fopen("datalist.txt","w+")) == NULL)
  {
    printf(" File opening failed \n");
    exit(1);
  }
  printf(" Writes unsorted data to a file \n");
  /* The array Sdata[NUM] To a file */
  fwrite(addrs,sizeof(addrs),1,fp);
  /* Put the array in the file Sdata[NUM] Take them out and print them */
  for(i=0;i<NUM;i++)
  {
    struct data *p;
    p = get_data(fp,i);   /* get Sdata[i] A pointer to the */
    print_data(p);     /* The structure Sdata[i] Each member variable is printed out */
    printf("\n");
  }
 
  fclose(fp);         /* Close file pointer */
  /* In order to 2 Open the file again in base mode datalist.txt*/
  if((fp=fopen("datalist.txt","rb+"))==NULL)
  {
    printf(" Unable to open file in read-write mode \n");
    exit(1);
  }
 
  printf(" Sort the file data \n");
  /* The string sort function is called to sort the string structure in the text */
  quick_disk(fp,NUM);     
 
  printf(" End of the sort \n");
  /* Print out the array data after sorting */
  for(i=0;i<4;i++)
  {
    struct data *p;
    p = get_data(fp,i);
    print_data(p);
    printf("\n");
  }
  fclose(fp);
 
  return 0;
}
/* Sort strings using quicksort */
void quick_disk(FILE *fp,int count)
{
  qs_disk(fp,0,count-1);
}
/* Sorting function */
void qs_disk(FILE *fp,int left,int right)
{
  long int i,j;
  char x[30];
  i = left;
  j = right;
  /* Comparison string x for Sdata An array of middle 1 Of structural variables name Member variables */
  strcpy(x,get_name(fp,(long)(i+j)/2));
  do
  {  /* Compare the current structure variables name Member variable to the comparison string x The size of the */
    while((strcmp(get_name(fp,i),x)<0)&&(i<right))
      i++;
    while((strcmp(get_name(fp,j),x)>0)&&(j>left))
      j--;
    if(i<=j)
    {
      exchangedata(fp,i,j);    /* exchange i and j Corresponding data */
      i++;
      j--;
    }
  }while(i<j);
 
  if(left<j)          /* Call this sort function again and again until j Reach the leftmost end of the data */
    qs_disk(fp,left,(int)j);
  if(i<right)         /* Call this sort function again and again until i Reach the far right end of the data */
    qs_disk(fp,(int)i,right);
}
/* exchange i and j The corresponding data in the file */
void exchangedata(FILE *fp,long i,long j)
{
  char a[sizeof(info)],b[sizeof(info)];
  fseek(fp,sizeof(info)*i,SEEK_SET);   /* find i The corresponding data location in the file */
  fread(a,sizeof(info),1,fp);       /* Reads the location data into an array of strings a In the */
 
  fseek(fp,sizeof(info)*j,SEEK_SET);   /* find j The corresponding data location in the file */
  fread(b,sizeof(info),1,fp);       /* Reads the location data into an array of strings b In the */
 
  fseek(fp,sizeof(info)*j,SEEK_SET);   /* find j The corresponding data location in the file */
  fwrite(a,sizeof(info),1,fp);      /* Read that in a Is written to this location */
  fseek(fp,sizeof(info)*i,SEEK_SET);   /* find i The corresponding data location in the file */
  fwrite(b,sizeof(info),1,fp);      /* Read that in b Is written to this location */
  /* In the completion file i and j Where the corresponding data is exchanged */
}
/* Get the file fp In the variable rec Of the corresponding structural variables name Member variables */
char *get_name(FILE *fp,long rec)
{
  struct data *p;
  p = &info;
  rewind(fp);
  /* Find the location of the structure variable */
  fseek(fp,rec*sizeof(struct data),SEEK_SET);
  /* Read it to the pointer p*/
  fread(p,sizeof(struct data),1L,fp);
  return p->name;     /* Returns the value of the struct variable name Member variables */
}
/* Get the file fp In the variable rec Pointer to the corresponding struct variable */
struct data *get_data(FILE *fp,long rec)
{
  struct data *p;
  p = &info;
  rewind(fp);
  /* Find the location of the structure variable */
  fseek(fp,rec*sizeof(info),SEEK_SET);
  /* Read it to the pointer p*/
  fread(p,sizeof(info),1,fp);
  return p;        /* Returns a pointer to the structure */
}
/* The pointer p Each member variable of the corresponding structure is printed */
void print_data(struct data *p)
{
  printf(" Name: %s\n",p->name);
  printf(" School: %s\n",p->school);
  printf(" City: %s\n",p->city);
  printf(" province   : %s\n",p->province);
}

Thank you for reading, I hope to help you, thank you for your support of this site!