qsort.c

/*
 * Quicksort sorts by employing a divide and conquer strategy to divide a 
 * list into two sub-lists.Full example of quicksort on a random set of 
 * numbers. The boxed element is the pivot. It is always chosen as the 
 * last element of the partition.
 * 
 * The steps are:
 * 1. Pick an element, called a pivot, from the list.
 * 2. Reorder the list so that all elements which are less than the pivot 
 *    come before the pivot and so that all elements greater than the pivot 
 *    come after it (equal values can go either way). After this partitioning,
 *    the pivot is in its final position. This is called the partition operation.
 * 3. Recursively sort the sub-list of lesser elements and the sub-list of greater elements.
 *
 * The base case of the recursion are lists of size zero or one, which are always sorted.
 */
#include <stdio.h>
#include <stdlib.h>

static int swap_times = 0;

void swap(int v[], int i, int j)
{
	swap_times++;
	int temp = v[i];
	v[i] = v[j];
	v[j] = temp;
}

int partition(int v[], int left, int right, int pivot_index)
{
	int pivot_value = v[pivot_index];
	int store_index = left;
	int i;
	swap(v, pivot_index, right);
	for (i = left; i < right; i++)
	{
		if (v[i] <= pivot_value)
		{
			swap(v, i, store_index);
			store_index++;
		}
	}
	swap(v, store_index, right);
	return store_index;
}

void quick_sort(int v[], int left, int right)
{
	if (left < right)
	{
		int pivot_index = partition(v, left, right, left);
		quick_sort(v, left, pivot_index - 1);
		quick_sort(v, pivot_index + 1, right);
	}
}



void print_array(int v[], int len)
{
	int i;
	printf("[");
	for (i = 0; i < len; i++)
		printf((i == len - 1) ? "%d": "%d ", v[i]);
	printf("]\n");
}

int main(void)
{
	int v[] = {9, 8, 7, 6, 5, 4, 3, 2, 1};
	size_t size = sizeof(v)/sizeof(v[0]);
	printf("---------- before -----------\n");
	print_array(v, size);
	printf("----------  after -----------\n");
	quick_sort(v, 0, size - 1);
	print_array(v, size);
	printf("swap times -- %d\n", swap_times);
	return 0;
}