DS (II) Assignment 2: Set B- a)

 a) Write a program to sort n randomly generated elements using Heapsort method.

Solution: 

#include<stdio.h>
void swap(int *a, int *b) 
{
int temp = *a;
*a = *b;
*b = temp;
}
void generate(int *arr, int n)
{
int i;
  for (i=0; i < n; i++) 
{
        arr[i] = rand()%100;
}
}
void heapify(int arr[], int n, int i) 
{
    // Find largest among root, left child and right child
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < n && arr[left] > arr[largest])
largest = left;
    if (right < n && arr[right] > arr[largest])
  largest = right;
    // Swap and continue heapifying if root is not largest
    if (largest != i) 
{
    swap(&arr[i], &arr[largest]);
heapify(arr, n, largest);
    }
}
void heapSort(int arr[], int n) 
{
    int i,a;
    // Build max heap
    for (i = n/2 - 1; i >= 0; i--)
    heapify(arr, n, i);
    // Heap sort
    for (i = n - 1; i >= 0; i--) 
{
    swap(&arr[0], &arr[i]);
    printf("\nHeap Sort Iteration %d : ", i);
  for (a = 0; a < n; a++)
{
      printf("\t%d", arr[a]);
  }
      // Heapify root element to get highest element at root again
      heapify(arr, i, 0);
    }
}
void printArray(int arr[], int n) 
{
  int i;
    for (i = 0; i < n; ++i)
      printf("%d ", arr[i]);
    printf("\n");
}
int main() 
{
    int arr[20],n;
    printf("\nEnter The Number of Elements for The Array\n");
    scanf("%d",&n);
generate(arr,n);
printf("\nGiven Array Is:\n");
printArray(arr, n);
printf("\n\t\tHeap Sort\n");
heapSort(arr, n);
    printf("\n\nSorted array is \n");
    printArray(arr, n);
}