C/Data Structure Algorithm/Quick sort
Содержание
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;
}
A Quicksort for strings
#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);
}
}
A Quicksort for structures of type address
/*
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);
}
How to use sysmtem quick sort
#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;
}
Quick sort on two dimensional string array
#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] );
}
Sort: quicksort: how to use qsort
#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;
}
The Quicksort
#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);
}
Use the system quick sort
#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;
}