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 3: Sorting algorithm


Dynamic Memory Allocation

Whenever we need to create an array of arbitrary length, we can use malloc() function (defined in stdlib.h).
We cannot create an array of n length like this 

int a[n]; // Generates compilation error

Rather we can code like this 
#include <stdlib.h>
int main()
{
	int *a;
	int n, i;
	scanf(%d", &n);
	a = (int *) malloc(n * sizeof(int));
	for(i = 0; i < n; ++i)
	{
		// work with a[i]
		...................
		...................
	}
	free(a);
}

We need to free the memory using free() function after we are done with it.

Heap Sort

Heap sort runs in O(nlgn) time. Heap sort uses less memory and time compared to the insertion sort and merge sort. In insertion sort, the run time is O(n^2) and although merge sort runs as fast as heap sort, merge sort need new array elements with every merge procedure. Heap sort on the other hand sorts in place.

Heap sort starts with building a max heap. A heap is an array that we can view as a binary tree. In a heap 

PARENT(i)=Floor(i/2)
LEFT(i)=2i
RIGHT(i)=2i+1
A max heap is a heap where the parent is greater or equal to its child(s). We can make a max heap out of an array by calling the BUILD-MAX-HEAP 
BUILD-MAX-HEAP(A)
	A.heap-size = A.length
	for i= Floor(A.length/2) downto 1
		MAX-HEAPIFY(A,i)
The MAX-HEAPIFY(A,i) function make a max heap recursively starting from i through the child trees rooted from i position. It does not care about the elements on top of i position. 
MAX-HEAPIFY(A,i)
	l = LEFT(i)
	r = RIGHT(i)
	if l ≤ A.heap-size and A[l] > A[i]
		largest = l
	else
		largest = i
	if r ≤ A.heap-size and A[r] > A[largest]
		largest = r
	if largest ≠ i
		swap A[i] with A[largest]
		MAX-HEAPIFY(A,largest)
Finally the HEAPSORT function first build a max heap. It guarantees that the maximum value is stored in the first position. Thus we can put it on the correct position at the end of the array and decrease the heap size by 1. It will permanently keep that position intact and in the next iterations the last element will be ignored. 
HEAPSORT(A)
	BUILD-MAX-HEAP(A)
	for i= A.length downto 2
		swap A[1] with A[i]
		A.heap-size = A.heap-size - 1
		MAX-HEAPIFY(A,1)