Heap Sort in C - Iterative Algorithm

"Heapsort is a comparison-based sorting algorithm to create a sorted array (or list), and is part of the selection sort family. Although somewhat slower in practice on most machines than a well-implemented quicksort, it has the advantage of a more favorable worst-case O(n log n) runtime. Heapsort is an in-place algorithm, but is not a stable sort." - Wikipedia

#include<stdio.h>
#define maxheapsize 50
#define LEFT(i) 2*i
#define RIGHT(i) 2*i+1

MAX_HEAPIFY(int *a, int i, int size)
{
  // Largest of a[i], a[LEFT(i)] and a[RIGHT(i)]
  // is determined and the index is stored in "largest".
  int l, r, largest, temp;
  l = LEFT(i);
  r = RIGHT(i);
  if ((l <= size)&&(a[l] > a[i]))
    largest = l; 
  else largest = i;
  if((r <= size)&&(a[r] > a[largest]))
    largest = r;
  
  // If largest != i, swap a[i] and a[largest]
  // and heapify the subtree rooted at largest
  if(largest != i)
  {
    temp = a[i];
    a[i] = a[largest];
    a[largest] = temp;

    MAX_HEAPIFY(a, largest, size);
  }
}

BUILD_MAX_HEAP(int *a, int size)
{
  int i;

  // 2nd half of the array are leaf nodes, so each is a
  // 1-element heap to begin with.
  for(i = size/2; i > 0; i--)
    MAX_HEAPIFY(a, i, size);
}

HEAPSORT(int *a, int size)
{
  int sortedarray[maxheapsize], actualsize, root;
  int i, s = 0, j, temp;
  actualsize = size;
  
  // Build the heap tree
  BUILD_MAX_HEAP(a, size); 
  
  for(i = size; i > 0; i--)
  { 
    // Save the root to another array
    sortedarray[++s] = a[1];
    root = a[1];

    // exchange a[1](root) and a[i]
    temp = a[1];
    a[1] = a[i];
    a[i] = temp;
    
    size--;
    
    // MAX_HEAPIFY lets the value of a[i] "float down" in
    // the max-heap so that the subtree rooted at index i
    // obeys the max-heap property
    MAX_HEAPIFY(a, 1, size);

    printf("\nHeap tree after removing the largest element %d\n", root);
    for(j = 1; j<=size; j++)
      printf("%d ", a[j]);
    if(size == 0)
      printf("NULL\n");
  }

  // Print the sorted array
  printf("\nSorted array\n");
  for(i = actualsize; i > 0; i--)
    printf("%d ", sortedarray[i]);
}

int main()
{ 
  int a[maxheapsize], n, i;
  printf("\nEnter the size of the array (< 50):");
  scanf("%d", &n);
  printf("\nEnter the elements of the array\n");
  for(i = 1; i <= n; i++)
    scanf("%d", &a[i]);

  HEAPSORT(a, n);

  return 0;
}

Written by Munia Balayil

GATE 2010 C Programming Question

GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

What is the value printed by the following C program?

#include <stdio.h>

int f(int *a, int n)
{
  if(n <= 0) return 0;
  else if(*a % 2 == 0) return *a + f(a + 1, n - 1);
  else return *a - f(a + 1, n - 1);
}

int main()
{
  int a[] = {12, 7, 13, 4, 11, 6};
  printf("%d", f(a, 6));
  return 0;
}

(A) -9
(B) 5
(C) 15
(D) 19

Answer
------
(C) 15

Explanation
-----------
f(12,....6, 6) = 12 + f(7,....6, 5)
f(7,....6, 5) = 7 - f(13,....6, 4)
f(13,....6, 4) = 13 - f(4,....6, 3)
f(4,....6, 3) = 4 + f(11,....6, 2)
f(11,....6, 2) = 11 - f(6, 1)
f(6, 1) = 6 + f(NULL, 0)
f(NULL, 0) = 0

Hence, 12 + (7 - (13 - (4 + (11 - (6 + (0)))))) = 15
Written by Munia Balayil