heapSort.c

#include <stdio.h>

void print(int *A);
void heapsort(int arr[], unsigned int N);

int main(int argc, char *argv[])
{
	int A[] = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
	print(A);
	heapSort(A);
	//heapsort(A, length(A));
	print(A);
	return 0;
}

void print(int *A)
{
        int i;
        for(i=0;i<length(A);i++)
                printf("%d ",A[i]);
        printf("\n");
}

void heapsort(int arr[], unsigned int N) 
{
    int t; /* the temporary value */
    unsigned int n = N, parent = N/2, index, child; /* heap indexes */
    /* loop until array is sorted */
    for (;;) { 
        if (parent > 0) { 
            /* first stage - Sorting the heap */
            t = arr[--parent];  /* save old value to t */
        } else {
            /* second stage - Extracting elements in-place */
            n--;                /* make the heap smaller */
            if (n == 0) return; /* When the heap is empty, we are done */
            t = arr[n];         /* save lost heap entry to temporary */
            arr[n] = arr[0];    /* save root entry beyond heap */
        }
        /* insert operation - pushing t down the heap to replace the parent */
        index = parent; /* start at the parent index */
        child = index * 2 + 1; /* get its left child index */
        while (child < n) {
            /* choose the largest child */
            if (child + 1 < n  &&  arr[child + 1] > arr[child]) {
                child++; /* right child exists and is bigger */
            }
            /* is the largest child larger than the entry? */
            if (arr[child] > t) {
                arr[index] = arr[child]; /* overwrite entry with child */
                index = child; /* move index to the child */
                child = index * 2 + 1; /* get the left child and go around again */
            } else {
                break; /* t's place is found */
            }
        }
        /* store the temporary value at its new location */
        arr[index] = t; 
    }
}