Generates a list of random integers, makes a heap, and then performs heapsort.

heapsort.c

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <math.h>
#include <assert.h>

// #define ARRAY_SIZE 100
#define MAX_NUMBER 100

#define bool char
#define TRUE 1
#define FALSE 0


int* generateRandomIntArray(int size)
{
	int *arr = malloc(size * sizeof(int));
	time_t t;
	srand((unsigned) time(&t));

	int i;
	for( i = 0 ; i < size ; i++ ) 
	{
		arr[i] = rand() % MAX_NUMBER;
	}

	return arr;
}

void swap(int* a, int* b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}

int getChild1(int n, int size)
{
	/* returns a left child of node n */
	int index = (2*n+1);
	return index<size?index:-1;
}

int getChild2(int n, int size)
{
	/* returns a right child of node n */
	int index = (2*n+2);
	return index<size?index:-1;
}

int getParent(int n)
{
	return (n-1)/2;
}

void buildHeap(int* arr, int size)
{
	assert(size>0);

	/*heapifies an array of integers*/
	int start = size/2-1;
	int max_depth = (int)(log(size-1)/log(2));

	int node_n; int step_n; int child1_n; int child2_n; int cur_node_n;
	int steps_to_make = 1; int steps_increase_index = pow(2, max_depth-1)-1;
	for(node_n=start;node_n>=0;node_n--)
	{
		cur_node_n = node_n;
		for(step_n=0;step_n<steps_to_make;step_n++)
		{
			child1_n = getChild1(cur_node_n, size);
			child2_n = getChild2(cur_node_n, size);
			if(child1_n == -1)
			{
				break;
			}

			if(arr[child1_n]>arr[cur_node_n])
			{
				if(child2_n != -1)
				{
					if(arr[child1_n]<=arr[child2_n])
					{
						swap(&arr[child2_n],&arr[cur_node_n]);
						cur_node_n = child2_n;
					}
					else
					{
						swap(&arr[child1_n],&arr[cur_node_n]);
						cur_node_n = child1_n;
					}
				}
				else
				{
					swap(&arr[child1_n],&arr[cur_node_n]);
					cur_node_n = child1_n;
				}
			}
			else
			{
				if(child2_n != -1)
				{
					if(arr[child2_n]>arr[cur_node_n])
					{
						swap(&arr[child2_n],&arr[cur_node_n]);
						cur_node_n = child2_n;
					}
					else
					{
						break;
					}
				}
				else
				{
					break;
				}
			}
		}

		if(node_n == steps_increase_index)
		{
			steps_to_make++;
			steps_increase_index /= 2;
		}
	}
}

void heapsort(int* arr, int size)
{
	assert(size>0);
	if(size==1)return;

	int node_n; int cur_node_n; 
	int new_size = size;
	int child1_n = 0; int child2_n = 0;
	for(node_n=size-1;node_n>0;node_n--)
	{
		cur_node_n = 0;

		/* move the root to the end */
		swap(&arr[0], &arr[node_n]);
		new_size--;

		child1_n = getChild1(cur_node_n, new_size); 
		child2_n = getChild2(cur_node_n, new_size); 

		while(child1_n != -1 || child2_n != -1)
		{
			if(arr[child1_n]>arr[cur_node_n])
			{
				if(child2_n != -1)
				{
					if(arr[child2_n]>arr[child1_n])
					{
						swap(&arr[child2_n], &arr[cur_node_n]);
						cur_node_n = child2_n;
					}
					else
					{
						swap(&arr[child1_n], &arr[cur_node_n]);
						cur_node_n = child1_n;
					}
				}
				else
				{
					swap(&arr[child1_n], &arr[cur_node_n]);
					cur_node_n = child1_n;
				}
			}
			else
			{
				if(child2_n != -1)
				{
					if(arr[child2_n]>arr[cur_node_n])
					{
						swap(&arr[child2_n], &arr[cur_node_n]);
						cur_node_n = child2_n;
					}
					else
					{
						break;
					}
				}
				else
				{
					break;
				}
			}
			child1_n = getChild1(cur_node_n, new_size); 
			child2_n = getChild2(cur_node_n, new_size); 
		}
	}
}


int main(int argc, char const *argv[])
{
	assert(argc==2);
	int ARRAY_SIZE = atoi(argv[1]); 

	int *arr = generateRandomIntArray(ARRAY_SIZE);

	int i;
	printf("Initial array:\n");
	for( i = 0 ; i < ARRAY_SIZE ; i++ ) 
	{
		printf("%d, ", arr[i]);
	}
	printf("\n");

	buildHeap(arr, ARRAY_SIZE);

	printf("Heap array:\n");
	for( i = 0 ; i < ARRAY_SIZE ; i++ ) 
	{
		printf("%d, ", arr[i]);
	}
	printf("\n");

	heapsort(arr, ARRAY_SIZE);

	printf("Sorted array:\n");
	for( i = 0 ; i < ARRAY_SIZE ; i++ ) 
	{
		printf("%d, ", arr[i]);
	}
	printf("\n");


	return 0;
}