For Advertisements on this blog Contact Us at developgram@gmail.com or +91-9923438816

Simple Programming Tutorials For Beginners

Monday, December 12, 2016

Heap Sort

/*
Summary: The heapsort algorithm can be divided into two parts.
-Step 1: a heap is built out of the data.
-Step 2: a sorted array is created by repeatedly removing the largest element from the heap, and inserting it into the array.
The heap is reconstructed after each removal. Once all objects have been removed from the heap, we have a sorted array. The direction of the sorted elements can be varied by choosing a min-heap or max-heap in step one.
Complexity: O(n·log n)
*/

#include <stdio.h>
int main()
{
 int heap[10], no, i, j, c, root, temp;

 printf("\n Enter no of elements :");
 scanf("%d", &no);
 printf("\n Enter the nos : ");

 for (i = 0; i < no; i++)
  scanf("%d", &heap[i]);

 for (i = 1; i < no; i++)
 {
  c = i;
  do
  {
   root = (c - 1) / 2;
                if (heap[root] < heap[c])   /* to create MAX heap array */
   {
    temp = heap[root];
    heap[root] = heap[c];
    heap[c] = temp;
   }
   c = root;
  } while (c != 0);
 }

 printf("Heap array : ");
 for (i = 0; i < no; i++)
  printf("%d\t ", heap[i]);

 for (j = no - 1; j >= 0; j--)
 {
  temp = heap[0];
            heap[0] = heap[j];    /* swap max element with rightmost leaf element */
  heap[j] = temp;
  root = 0;
  do
  {
                c = 2 * root + 1;    /* left node of root element */
   if ((heap[c] < heap[c + 1]) && c < j-1)
    c++;
                if (heap[root]<heap[c] && c<j)    /* again rearrange to max heap array */
   {
    temp = heap[root];
    heap[root] = heap[c];
    heap[c] = temp;
   }
   root = c;
  } while (c < j);
 }

 printf("\n The sorted array is : ");
 for (i = 0; i < no; i++)
  printf("\t %d", heap[i]);

 printf("\n Complexity : \n Best case = Avg case = Worst case = O(n logn) \n");

 return 0;
}

No comments:

Post a Comment

SEARCH THIS BLOG