main.c

/**
 * Heapsort implementation
 * 10 March, 2010, TUCN FA Labs
 * Stas Suscov <[email protected]>
 */
#include <stdio.h>
#include <stdlib.h>

double attrs; // stored attributions
double comps; // stored comparisons

/**
 * Function to generate randomly an array
 * params: target array, lenght of it and salt used for rand()
 */
int r_gen(int ar[], int ar_lenght, int salt)
{
	int i;
	srand(time(NULL));
	for(i = 0; i < ar_lenght; i++)
	{
		ar[i] = rand()%salt;
	}
	return 0;
}

/**
 * Function to clone arrays
 * params: from array, to target array, lenght of both
 */
int ar_cpy(int *from, int *to, int lenght)
{
	int i;
	for(i = 0; i < lenght; i++)
	{
		to[i] = from[i];
	}
	return 0;
}

/**
 * Prints an array
 * params: array to be printed and its lenght
 */
void ar_dump(int *ar, int ar_lenght, char delim)
{
	int i;
	for(i=0; i<ar_lenght; i++)
		printf("%d%c", ar[i], delim);
}

/**
 * Swaps two elements, a with b
 */
void swaps(int *ar, int a, int b) 
{
	int tmp;
	tmp = ar[a];
	ar[a] = ar[b];
	ar[b] = tmp;
	
	attrs++; //increment nr. of attributions
}

/**
 * Compares two elements, a with b
 * @return 0, if equal
 * @return -1, if a smaller than b
 * @return 1, if a greater than b
 */
int cmp(int a, int b)
{
	int r;
	if(a == b)
		r = 0;
	else if(a < b)
		r = -1;
	else
		r = 1;

	comps++; //increment the number of comparisons

	return r;
}

/**
 * Calculates and returns the position for parent node
 * @param int i
 * @return int
 */
int h_parent(int i)
{
	return i/2;
}

/**
 * Calculates and returns the position for left node
 * @param int i
 * @return int
 */
int h_left(int i)
{
	return 2*i;
}

/**
 * Calculates and returns the position for left node
 * @param int i
 * @return int
 */
int h_right(int i)
{
	return 2*i+1;
}

/**
 * Function to manipulate the heap in order to get a max sorted heap
 * @param int array ar, the heap array
 * @param int i, the position to be checked
 * @param int ar_length, the length of the ar
 * @param int h_size, the size of the heap
 */
void max_heapify(int *ar, int i, int ar_length, int *h_size)
{
	int l = h_left(i);
	int r = h_right(i);
	int largest;
	if((cmp(l, h_size) <= 0) && cmp(ar[l], ar[i]) == 1)
		largest = l;
	else
		largest = i;

	if((cmp(r, h_size) <=0) && cmp(ar[r], ar[largest]) == 1)
		largest = r;

	if(cmp(largest, i) != 0)
	{
		swaps(ar, i, largest);
		max_heapify(ar, largest, ar_length, h_size);
	}
}

/**
 * This builds a heap in bottom-up manner
 * @param int array ar
 * @param int ar_length, the length of the ar
 * @param int h_size, the size of the heap
 */
void build_max_heap(int *ar, int ar_length, int *h_size)
{
	h_size = ar_length;
	int i;
	for(i = ar_length/2; i>=1; i--)
		max_heapify(ar, i, ar_length, h_size);
}

/**
 * Heapsort algorith implemenation
 * @param int array ar
 * @param int ar_length, the length of the ar
 * @param h_size, the size of the heap
 */
void heapsort(int *ar, int ar_length, int *h_size)
{
	build_max_heap(ar, ar_length, h_size);
	int i;
	for(i=ar_length; i>= 2; i--)
	{
		swaps(ar, 1, i);
		h_size--;
		max_heapify(ar, 1, ar_length, h_size);
	}
}

/**
 * Main launcher
 */
int main()
{
	int ar_length = 12;
	int h_size;
	int ar_h[ar_length] = {1,2,3,4,5,6,7,8,9,10,14};
	//int ar_h[] = {1,2,3,4,5,6,7,8,9,10,14}; //works 
	ar_dump(ar_h, ar_length, ',');

	//r_gen(ar_h, ar_length, 100);
	ar_dump(ar_h, ar_length, ',');
	heapsort(ar_h, ar_length, h_size);
	printf("\n");
	ar_dump(ar_h, ar_length, ',');

	return 0;
}