Exercise

ABy Admin
May 13'24

Answer

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
 */

#ifndef QSORTSIMP_H_
#define QSORTSIMP_H_
#include <stdlib.h>
void qsortsimp( void* a, size_t elem_sz, int len, int(*cmp) (void*,void*) );
void shutdown_qsortsimp();

#endif /* QSORTSIMP_H_ */

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

/*   qsortsimp.c
 *   author : anonymous
 */
#include "qsortsimp.h"
#include<stdlib.h>
#include<string.h>

	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
 ============================================================================
 */

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#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.

00