excans:Be232fc3b8

One possible solution , can be to adapt this word sorting use of quicksort to sort integers. Otherwise , an exercise would be to re-write non-generic qsort functions of qsortsimp, partition, and swap for integers.

/*

* qsortsimp.h
*
*  Created on: 17/03/2013
*      Author: anonymous
*/

1. ifndef QSORTSIMP_H_
2. define QSORTSIMP_H_
3. include

void qsortsimp( void* a, size_t elem_sz, int len, int(*cmp) (void*,void*) ); void shutdown_qsortsimp();

1. endif /* QSORTSIMP_H_ */

//----------------------------------------------------------------------------

/* qsortsimp.c

*   author : anonymous
*/

1. include "qsortsimp.h"
2. include
3. include

static void * swap_buf =0; static int bufsz = 0;

void swap( void* a, int i, int j, size_t elem_sz) { if (i==j)return; if (bufsz == 0 || bufsz < elem_sz) { swap_buf = realloc(swap_buf, elem_sz); bufsz=elem_sz; }

memcpy( swap_buf, a+i*elem_sz, elem_sz); memcpy( a+i*elem_sz, a+j*elem_sz, elem_sz); memcpy( a+j*elem_sz, swap_buf, elem_sz); }

void shutdown_qsortsimp() { if (swap_buf) { free(swap_buf); } }

int partition( void* a, size_t elem_sz, int len, int (*cmp)(void*,void*) ) {

int i = -1; int j = len-1; void* v = a + j * elem_sz;

for(;;) { while( (*cmp)(a + ++i * elem_sz , v ) < 0); while ( (*cmp)(v, a + --j * elem_sz) < 0 ) if (j==0) break ; if( i>=j)break; swap(a, i, j, elem_sz); } swap( a, i, len-1, elem_sz); return i;

}

void qsortsimp( void* a, size_t elem_sz, int len, int(*cmp) (void*,void*) ) { if ( len > 2) { int p = partition(a, elem_sz, len, cmp); qsortsimp( a, elem_sz, p, cmp); qsortsimp( a+(p+1)*elem_sz, elem_sz, len - p -1, cmp ); }

}

//------------------------------------------------------------------------------

/* Name  : words_quicksort.c

Author      : anonymous
Version     :
Copyright   :  
Description : quick sort the words in moby dick in C, Ansi-style
============================================================================
*/

1. include
2. include
3. include
4. include
5. include "qsortsimp.h"

void printArray(const char* a[], int n) { int i; for(i=0; i < n; ++i) { if(i!=0 && i% 5 == 0) { printf("\n"); } if (i%1000000 ==0) { fprintf(stderr,"printed %d words\n", i); } printf("%s ", a[i]);

} printf("\n");

}

const int MAXCHARS=250; char ** wordlist=0; int nwords=0; int remaining_block; const size_t NWORDS_PER_BLOCK = 1000;

//const char* spaces=" \t\n\r"; //inline isspace(const char ch) { // int i=0; // while(spaces[i]!='\0') { // if(spaces[i++] == ch) // return 1; // } // return 0; //}

void freeMem() { int i = nwords; while(i > 0 ) { free(wordlist[--i]);

} free(wordlist);

}

static char * fname="~/Downloads/books/pg2701-moby-dick.txt";

void getWords() {

char buffer[MAXCHARS]; FILE* f = fopen(fname,"r"); int state=0; int ch; int i; while ((ch=fgetc(f))!=EOF) { if (isalnum(ch) && state==0) { state=1; i=0; buffer[i++]=ch; } else if (isalnum(ch) && i < MAXCHARS-1) { buffer[i++]=ch; } else if (state == 1) { state =0; buffer[i++]= '\0'; char* dynbuf = malloc(i); int j; for(j=0; j < i; ++j) { dynbuf[j] = buffer[j]; } i=0; if (wordlist == 0 ) {

wordlist = calloc(NWORDS_PER_BLOCK, sizeof(char*)); remaining_block = NWORDS_PER_BLOCK; } else if ( remaining_block == 0) { wordlist = realloc(wordlist, (NWORDS_PER_BLOCK + nwords)* sizeof(char*)); remaining_block = NWORDS_PER_BLOCK; fprintf(stderr,"allocated block %d , nwords = %d\n", remaining_block, nwords);

} wordlist[nwords++]= dynbuf; --remaining_block; }

} fclose(f);

} void testPrintArray() {

int i;

for(i=0; i < nwords;++i) { printf("%s | ", wordlist[i]);

} putchar('\n'); printf("stored %d words. \n",nwords); }

int cmp_str_1( void* a, void *b) { int r = strcasecmp( *((char**)a),*((char**)b)); return r; }

int main(int argc, char* argv[]) { if (argc > 1) { fname = argv[1]; } getWords(); testPrintArray();

qsortsimp(wordlist, sizeof(char*), nwords, &cmp_str_1);

testPrintArray();

shutdown_qsortsimp(); freeMem(); puts("!!!Hello World!!!"); /* prints !!!Hello World!!! */ return EXIT_SUCCESS; }

References

Wikibooks contributors. "C Programming/Exercise solutions". Wikibooks. Wikibooks. Retrieved 13 May 2024.