#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 10	/* number of int's to sort. */

void quicksort(int *begin, int *end);
void swap(int *p1, int *p2);

int main()
{
	int a[N];
	int i;

	srand(time(NULL));
	for (i = 0; i < N; ++i) {
		a[i] = rand();
	}

	quicksort(a, a + N);

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

	return EXIT_SUCCESS;
}

/*
Sort the int's into increasing order.  begin is the address of the first int;
end is one more than the address of the last int.  The number of int's to sort
is therefore (end - begin).
*/

void quicksort(int *begin, int *end)
{
	int *p;
	int *last;
	const ptrdiff_t length = end - begin;

	if (length <= 1) {
		return;
	}

	/* Pick a random element and move it to the front. */
	swap(begin, begin + rand() % length);

	/* Move all the elements that are smaller than the randomly selected
	element to the range begin + 1 to last inclusive. */

	/* address of the last element that is < the randomly selected element. */
	last = begin;

	for (p = begin + 1; p < end; ++p) {
		if (*p < *begin) {
			swap(++last, p);
		}
	}

	/* Put the randomly selected element where it belongs. */
	swap(begin, last);

	/* Sort all the int's that are < the randomly selected element. */
	quicksort(begin, last);

	/* Sort all the int's that are >= the randomly selected element. */
	quicksort(last + 1, end); 
}

void swap(int *p1, int *p2)
{
	const int temp = *p1;
	*p1 = *p2;
	*p2 = temp;
}