quicksort.c

/*
    quicksort - C
*/

#include <alloca.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define ARRAY_SIZE 1048576

typedef struct
{
	void *begin,*end;
} quicksort_stack_body_t;

unsigned int fls(int i){
	unsigned int counter = 0;
	while(i){
		i = i>>1;
		counter++;
	}
	return counter;
}

#define SWAP(a,b,size) \
	do{ \
		register char *a_ = (char *)(a),*b_ = (char *)(b); \
		register size_t size_ = (size); \
		while(size_--){ \
			char temp = *a_; \
			*a_++ = *b_; \
			*b_++ = temp; \
		} \
	}while(0)

void quicksort(void *base,const size_t num,const size_t size
	,int (*compare)(const void *,const void *))
{
	quicksort_stack_body_t *stack,*stack_top;
	stack_top = stack = alloca(sizeof(quicksort_stack_body_t)*fls(num));
	stack_top->begin = base,stack_top->end = base+size*(num-1);
	while(1){
		void *current_begin = stack_top->begin,*current_end = stack_top->end;
		if(current_begin >= current_end){
			if(stack == stack_top){
				break;
			}
			stack_top--;
		}
		else{
			void *pivot
				= current_begin+size*((current_end-current_begin)/size>>1)
				,*first2last = current_begin,*last2first = current_end;
			while(first2last < last2first){
				while(compare(first2last,pivot)){
					first2last += size;
				}
				while(!compare(last2first,pivot)){
					last2first -= size;
				}
				if(first2last < last2first){
					if(pivot == first2last){
						pivot = last2first;
					}
					SWAP(first2last,last2first,size);
				}
			}
			SWAP(pivot,first2last,size);
			first2last += size;
			if(current_end-last2first < first2last-current_begin){
				stack_top->end = last2first;
				stack_top++;
				stack_top->begin = first2last;
				stack_top->end = current_end;
			}
			else{
				stack_top->begin = first2last;
				stack_top++;
				stack_top->begin = current_begin;
				stack_top->end = last2first;
			}
		}
	}
}

int compare_integer_qsort(const void *a,const void *b)
{
	return *(int *)a-*(int *)b;
}

int compare_integer_quicksort(const void *a,const void *b)
{
	return *(int *)a<*(int *)b;
}

int main(void)
{
	int array[ARRAY_SIZE];
	unsigned long random_seed = time(NULL);
	size_t counter = 0;
	clock_t clock_;
	/*
	while(counter != 32){
		array[counter] = rand()%64;
		printf("%02d ",array[counter]);
		counter++;
	}
	printf("\n");
	quicksort(array,32,sizeof(int),compare_integer_quicksort);
	counter = 0;
	while(counter != 32){
		printf("%02d ",array[counter]);
		counter++;
	}
	printf("\n");
	return 0;
	*/
	srand(random_seed);
	while(counter != ARRAY_SIZE){
		array[counter] = rand()%1048576;
		counter++;
	}
	clock_ = clock();
	qsort(array,ARRAY_SIZE,sizeof(int),compare_integer_qsort);
	printf("C standard library - qsort() : %d/%d s\n",clock()-clock_,CLOCKS_PER_SEC);
	srand(random_seed);
	counter = 0;
	while(counter != ARRAY_SIZE){
		array[counter] = rand()%1048576;
		counter++;
	}
	clock_ = clock();
	quicksort(array,ARRAY_SIZE,sizeof(int),compare_integer_quicksort);
	printf("pi8027\'s quicksort() : %d/%d s\n",clock()-clock_,CLOCKS_PER_SEC);
	return 0;
}