Write a C program to recursively sort using the Quick sort partition exchange algorithm.

• you can use the "driver", or the random number test data from exercise on mergesort. This is "re-use", which is encouraged in general.

- an advantage of reuse is less writing time, debugging time, testing time.

• the concept of partition exchange is that a partition element is (randomly) selected, and every thing that needs sorted is put into 3 equivalence classes : those elements less than the partition value, the partition element, and everything above (and equal to ) the partition element.
• this can be done without allocating more space than one temporary element space for swapping two elements. e.g a temporary integer for integer data.
• However, where the partition element should be using the original array space is not known.
• This is usually implemented with putting the partition on the end of the array to be sorted, and then putting two pointers , one at the start of the array, and one at the element next to the partition element , and repeatedly scanning the left pointer right, and the right pointer left.
• the left scan stops when an element equal to or greater than the partition is found, and the right scan stops for a smaller element than the partition value, and these are swapped, which uses the temporary extra space.
• the left scan will always stop if it reaches the partition element , which is the last element; this means the entire array is less than partition value.
• the right scan could reach the first element, if the entire array is greater than the partition , and this needs to be tested for, else the scan doesn't stop.
• the outer loop exits when then left and right pointers cross. Testing for pointer crossing and outer loop exit should occur before swapping, otherwise the right pointer may be swapping a less-than-partition element previously scanned by the left pointer.
• finally, the partition element needs to be put between the left and right partitions, once the pointers cross.
• At pointer crossing, the left pointer may be stopped at the partition element's last position in the array, and the right pointer not progressed past the

element just before the last element. This happens when all the elements are less than the partition.

- if the right pointer is chosen to swap with the partition, then an incorrect state results where the last element of the left array becomes less than the partition element value.

- if the left pointer is chosen to swap with the partition, then the left array will be less than the partition, and partition will have swapped with an element with value greater than the partition or the partition itself.

• The corner case of quicksorting a 2 element out-of-order array has to be examined.

- The left pointer stops on the first out of order element. The right pointer begins on the first out-of-order element, but the outer loop exits because this is the leftmost element. The partition element is then swapped with the left pointer's first element, and the two elements are now in order.

- In the case of a 2 element in order array, the leftmost pointer skips the first element which is less than the partition, and stops on the partition. The right pointer begins on the first element and exits because it is the first position. The pointers have crossed so the outer loop exits. The partition swaps with itself, so the in-ordering is preserved.

• After doing a swap, the left pointer should be incremented and right pointer decremented, so the same positions aren't scanned again, because an endless loop can result ( possibly when the left pointer exits when the element is equal to or greater than the partition, and the right element is equal to the partition value). One implementation, Sedgewick, starts the pointers with the left pointer minus one and right pointer the plus one the intended initial scan positions, and use the pre-increment and pre-decrement operators e.g. ( ++i, --i) .

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.