Quicksort

scvalex (Alexandru Scvortov) — Mon, 01 Oct 2007 10:43:04 GMT

Qucksort written in C. Uses the Hoare partition algorithm.



typedef struct {

	int len;

	int elem[50240];

} vector;



void printv(char *str, vector v) {

	printf("%s", str);

	int i = 0;

	for (; i < v.len; ++i)

		printf("%d ", v.elem[i]);

	printf("\n");

}



#define MAX(a, b) ((a > b) ? (a) : (b))

#define MIN(a, b) ((a < b) ? (a) : (b))



int partition(vector *v, int p, int r) {

	int x;

	if (p + 3 < r)

		x = MIN(v->elem[p], MAX(v->elem[p+1], v->elem[p+2]));

	else

		x = v->elem[p];

	

	int i = p - 1;

	int j = r + 1;

	while (1) {

		do {

			--j;

		} while (v->elem[j] > x);

		do {

			++i;

		} while (v->elem[i] < x);



		if (i < j) {

			int aux = v->elem[j];

			v->elem[j] = v->elem[i];

			v->elem[i] = aux;

		} else

			return j;			

	}

}



void quicksort_real(vector *v, int p, int r) {

	if (p < r) {

		int q = partition(v, p, r);

		quicksort_real(v, p, q);

		quicksort_real(v, q + 1, r);

	}

}



void quicksort(vector *v) {

	printf("Quicksort...\n");

	quicksort_real(v, 0, v->len - 1);

}

DZone Snippets: quicksort code

Quicksort