Here you will get program for heap sort in C.

It is a comparison based sorting technique which uses binary heap data structure.

Below I have shared simple program to implement this sorting technique in C.

## Program for Heap Sort in C

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
#include<stdio.h> void create(int []); void down_adjust(int [],int); void main() { int heap[30],n,i,last,temp; printf("Enter no. of elements:"); scanf("%d",&n); printf("\nEnter elements:"); for(i=1;i<=n;i++) scanf("%d",&heap[i]); //create a heap heap[0]=n; create(heap); //sorting while(heap[0] > 1) { //swap heap[1] and heap[last] last=heap[0]; temp=heap[1]; heap[1]=heap[last]; heap[last]=temp; heap[0]--; down_adjust(heap,1); } //print sorted data printf("\nArray after sorting:\n"); for(i=1;i<=n;i++) printf("%d ",heap[i]); } void create(int heap[]) { int i,n; n=heap[0]; //no. of elements for(i=n/2;i>=1;i--) down_adjust(heap,i); } void down_adjust(int heap[],int i) { int j,temp,n,flag=1; n=heap[0]; while(2*i<=n && flag==1) { j=2*i; //j points to left child if(j+1<=n && heap[j+1] > heap[j]) j=j+1; if(heap[i] > heap[j]) flag=0; else { temp=heap[i]; heap[i]=heap[j]; heap[j]=temp; i=j; } } } |

**Output**

*Enter no. of elements:5*

*Enter elements:12 8 46 23 7*

*Array after sorting:*

*7 8 12 23 46*

why not just a simple bubblesort?

The time complexity of heap sort is O(nlogn) which is better than that of bubble sort which is O(n^2).

I used this program but if I put number of elements in the array greater than 71, some printf lines and elements do not appear in console. Also the more I increase the size of the array the less lines and elements appear in console while the program is running.. What is going on? Does this code have a limit as to how many elements you can use?

You can scroll up to see upper output.

That’s the thing. I scroll way up at the beginning and I notice that a) some printf lines are not printed in console and b) when the sorting ends, not all elements are shown in console, even though if I “fprintf” them into a data.dat I can see all the elements.

I think I know the problem. Because I use 10000 elements or more, the cmd window cant print so many lines it has a 9999 limit and you have to set that too by yourself. the default is like 100 or something. That’s why some of my printf lines magically dissapeared. There was not enough space for them to be printed out in the cmd window.

why do we use down_adjust(heap,1);?

Dwnadjst is actually the sink fuction,the input we gave taken is unsortedbso wif parent<child value parent has to move dwn (Sink) and the child tets promoted that is why we perfem sink,arter one sink we get the highet elem at a[0]