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)
- /
- 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;
}
</source>
A Quicksort for strings
<source lang="cpp">
- include <stdio.h>
- 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">
- include <stdlib.h>
- 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">
- include <stdio.h>
- include <string.h>
- 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" };
- 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">
- include <stdio.h>
- 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">
- include <string.h>
- include <stdio.h>
- 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">
- include <stdio.h>
- 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>