quick_sort.c

#include <stdio.h>

void swap(int *a, int *b) {
  if (a != b) {
		*a ^= *b;
		*b ^= *a;
		*a ^= *b;
	}
}

void print(int a[], int size) {
	int i;
	for (i = 0; i < size; ++i) {
		printf("%d ", a[i]);
	}
	printf("\n");
}

int partition(int a[], int left, int right) {
	int key = a[right];
	int i = left - 1;
	int j;
	for (j = left; j < right; ++j) {
		if (a[j] <= key) {
			++i;
			swap(a + i, a + j);
		}
	}
	swap(a + i + 1, a + right);
	return i + 1;
}

void quicksort(int a[], int left, int right) {
	while (left < right) {
		int q = partition(a, left, right);
		if (q < (left + right) > 1) {
			quicksort(a, left, q - 1);
			left = q + 1;
		}
		else {
			quicksort(a, q + 1, right);
			right = q - 1;
		}
	}
}

int main() {
	int a[] = {3, 12, 9, 4, -5, 23, 8, 11, 102, 55, 20};
	/*int a[] = {1, 1, 1, 1, 1, 1, 1, 1, 1};*/
	int size = sizeof(a) / sizeof(*a);
	print(a, size);
	printf("%d\n", partition(a, 0, size - 1));
	quicksort(a, 0, size - 1);
	print(a, size);
	return 0;
}