C/Data Structure Algorithm/Quick sort

A Quicksort for files

<source lang="cpp"> /* C: The Complete Reference, 4th Ed. (Paperback) by Herbert Schildt ISBN: 0072121246 Publisher: McGraw-Hill Osborne Media; 4 edition (April 26, 2000)

• /

1. include <stdio.h>
2. include <stdlib.h>
3. include <string.h>
4. 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;

}

      </source>

A Quicksort for strings

<source lang="cpp">

1. include <stdio.h>
2. include <string.h>

void quickSortMain(char items[][10], int count); void quickSort(char items[][10], int left, int right); int main(void) {

 int i;
 char str[][10] = { "this","is","a","test"};
 quickSortMain(str, 4);
 for(i=0; i<4; i++) {
    printf("%s ", str[i]);
 }
 return 0;

} void quickSortMain(char items[][10], int count) {

 quickSort(items, 0, count-1);

} void quickSort(char items[][10], int left, int right) {

 int i, j;
 char *x;
 char temp[10];
 i = left;
 j = right;
 x = items[(left+right)/2];
 do {
   while((strcmp(items[i],x) < 0) && (i < right)) {
      i++;
   }
   while((strcmp(items[j],x) > 0) && (j > left)) {
       j--;
   }
   if(i <= j) {
     strcpy(temp, items[i]);
     strcpy(items[i], items[j]);
     strcpy(items[j], temp);
     i++;
     j--;
  }
 } while(i <= j);
 if(left < j) {
    quickSort(items, left, j);
 }
 if(i < right) {
    quickSort(items, i, right);
 }

}

      </source>

A Quicksort for structures of type address

<source lang="cpp"> /* C: The Complete Reference, 4th Ed. (Paperback) by Herbert Schildt ISBN: 0072121246 Publisher: McGraw-Hill Osborne Media; 4 edition (April 26, 2000)

• /

struct address {

 char name[40];
 char street[40];
 char city[20];
 char state[3];
 char zip[11];

}; /* A Quicksort for structures of type address. */ void quick_struct(struct address items[], int count) {

 qs_struct(items,0,count-1);

} void qs_struct(struct address items[], int left, int right) {

 register int i, j;
 char *x;
 struct address temp;
 i = left; j = right;
 x = items[(left+right)/2].zip;
 do {
   while((strcmp(items[i].zip,x) < 0) && (i < right)) i++;
   while((strcmp(items[j].zip,x) > 0) && (j > left)) j--;
   if(i <= j) {
     temp = items[i];
     items[i] = items[j];
     items[j] = temp;
     i++; j--;
   }
 } while(i <= j);
 if(left < j) qs_struct(items, left, j);
 if(i < right) qs_struct(items, i, right);

}

      </source>

How to use sysmtem quick sort

<source lang="cpp">

1. include <stdlib.h>
2. include <stdio.h>

int num[10] = {

 1, 2, 6, 5, 3, 7, 9, 12, 2, 0

}; /* compare the integers */ int comp(const void *i, const void *j) {

 return *(int *)i - *(int *)j;

} int main(void) {

 int i;
 printf("Original array: ");
 for(i=0; i<10; i++) {
     printf("%d ", num[i]);
 }
 qsort(num, 10, sizeof(int), comp);
 printf("Sorted array: ");
 for(i=0; i<10; i++) {
    printf("%d ", num[i]);
 }
 return 0;

}

      </source>

Quick sort on two dimensional string array

<source lang="cpp">

1. include <stdio.h>
2. include <string.h>
3. include <assert.h>

char names[22][25] = {

 "J", "C", "I", "B", "P", "G", "D", "O", "B", "V", "C", "D", "L",
 "G", "A", "K", "K", "T", "R", "J", "D", "J" };

1. define NUMBER_OF_NAMES sizeof ( names ) / sizeof ( names[0] )

int main() {

   int i;
   /* the unsorted letter */
   printf ( "The Unsorted Names.\n" );
   for ( i = 0; i < NUMBER_OF_NAMES; i++ ) 
       printf ( "%s\n", names[i] );
   printf ( "Press RETURN to continue: " );
   fflush ( stdout );
   getchar();
   qsort (( char * ) names, NUMBER_OF_NAMES, sizeof ( *names ), strcmp );
   assert ( names[0][0] < names[1][0] );  /* Quick check */
   /* the sorted names */
   printf ( "The Sorted letter.\n" );
   for ( i = 0; i < NUMBER_OF_NAMES; i++ ) 
       printf ( "%s\n", names[i] );

}

      </source>

Sort: quicksort: how to use qsort

<source lang="cpp">

1. include <stdio.h>
2. include <stdlib.h>

int values[] = { 4, 1, 10, 9, 2, 5 }; int compare (const void * a, const void * b) {

 return ( *(int*)a - *(int*)b );

} int main () {

 int i;
 
 qsort (values, 6, sizeof(int), compare);
 
 for (i = 0; i < 6; i++)
 {
   printf ("%d ",values[ i ]);
 }
 return 0;

}

      </source>

The Quicksort

<source lang="cpp">

1. include <string.h>
2. include <stdio.h>
3. include <stdlib.h>

void quickSortMain(char *items, int count); void quickSort(char *items, int left, int right); int main(void) {

 char s[255]="asdfasdfasdfasdfasdfasdfasdf";
 quickSortMain(s, strlen(s));
 printf("The sorted string is: %s.\n", s);
 return 0;

} void quickSortMain(char *items, int count) {

 quickSort(items, 0, count-1);

} void quickSort(char *items, int left, int right) {

 int i, j;
 char x, y;
 i = left;
 j = right;
 x = items[(left+right)/2];
 do {
   while((items[i] < x) && (i < right))
      i++;
   while((x < items[j]) && (j > left))
      j--;
   if(i <= j) {
     y = items[i];
     items[i] = items[j];
     items[j] = y;
     i++; j--;
   }
 } while(i <= j);
 if(i < right)
     quickSort(items, i, right);
 if(left < j)
     quickSort(items, left, j);

}

      </source>

Use the system quick sort

<source lang="cpp">

1. include <stdio.h>
2. include <stdlib.h>

int comp(const void *i, const void *j); int main(void) {

 int sort[100], i;
 /* set the array with random numer*/
 for(i = 0; i < 100; i++)
   sort[i] = rand();
 
 /* call the quick sort */
 qsort(sort, 100, sizeof(int), comp);
 for(i = 0; i < 100; i++)
   printf("%d\n", sort[ i ]);
 return 0;

} int comp(const void *i, const void *j) {

 return *(int*)i - *(int*)j;

}

      </source>