You are suggested to use the teaching servers burrow.soic.indiana.edu or hulk.soic.indiana.edu or tank.soic.indiana.edu for practicing C programs.

Lab 4: Quick Sort algorithm


Recursion

Recursion is the magical tool supplied to the developer by all high level programming languages. Whenever we can divide our problem into sub-problem we can use recursion. By using recursion, we can code our program with ease and produce clean and readable codes.
Every recursive function must have a base case and a recursive case.
For example, about Fibonacci number we can say that: F[1] = 1, F[2] = 1, F[n>=3] = F[n-2]+F[n-1]
We can write a recursive function to calculate that: 
int FIBO(int n)
{
	// Base case
	if (n==1 || n==2)
		return 1;
	else
		// Recursive case
		return FIBO(n-1)+FIBO(n-2);
}
Without defining the base case, a recursive function will go forerver.
All recursive code can be replaced by alternative loop version, for example we can write a looped version to calculate the fibonacci rather than the recursive case. But most of the cases, writing a loop version would be much harder to write than the recursive version.
For example, we can write a recursive function that print out all possible permutations of a string say "abcd" as 
abcd
abdc
acbd
acdb
adbc
adcb
bacd
badc
bcad
bcda
bdac
bdca
cabd
cadb
cbad
cbda
cdab
cdba
dabc
dacb
dbac
dbca
dcab
dcba
Here is the code 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char *flag, *output;
char s[] = "abcde";

printperm(int index, int len)
{
	int i;
	if (index == 0 && len == strlen(s))
		printf("%s\n", output);
	
	if (flag[index]) return;
	flag[index] = 1;
	output[len] = s[index];
	
	for(i=0; s[i]; ++i)			
		printperm(i, len+1);
	
	flag[index] = 0;
}

int main()
{
	int i, len;
	len = strlen(s);
	flag = (char *) malloc(len);
	output = (char *) malloc(len+1);

	memset(flag, 0, len);
	output[len] = 0;
	for(i=0; s[i]; ++i)
		printperm(i, 0);
}
If we try to do the same without recursion, there is definitely possible ways to do so, but it won't be as easy as it is with recursion.

Quick Sort

Quick sort runs in O(nlgn) time on average. Although in the worst case when all items are sorted reversely quick sort runs in O(n^2) time, quick sort is one of the most used sorting methods. Also the constant factor is quite small in quick sort, thus improving runtime. Quick sort also has the advantage of sorting in place without creating temporary arrays.

Quick sort uses divide and conquer method. At first a partition is created within the array such that all elements left of the partition value is smaller (or equal) to the partition and all elements right of the partition value is larger (or equal) to the partition. The last element is marked as the partition item. 

PARTITION(A, p, r)
	x = A[r]
	i = p-1
	for j=p to r-1
		if A[j] <= x
			i = i +1
			swap A[i] with A[j]
	swap A[i+1] with A[r]
	return i+1
The QUICKSORT function finds the partition within the range and recursively calls the QUICKSORT for left array and right array. 
QUICKSORT(A, p, r)
	if p < r
		q = PARTITION(A, p, r)
		QUICKSORT(A, p, q-1)
		QUICKSORT(A, q+1, r)