Heap Sort in C
Here you will know about Heap Sort and learn Heap Sort in C program.
What is Heap Sort in C
Heap Sort is a comparison-based sorting algorithm that works by creating a binary heap data structure. It repeatedly extracts the maximum (for ascending order) or minimum (for descending order) element from the heap and places it at the end of the sorted array. This method is repeated until the full array has been sorted.
Heap Sort in C program
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 66 67 68 69 70 71 72 73 74 75 | #include <stdio.h> #define MAX 10 void adjust( int list[],int i, int n) { int j,k,flag; k = list[i]; flag = 1; j = 2 * i; while(j <= n && flag) { if(j < n && list[j] < list[j+1]) j++; if( k >= list[j]) flag =0; else { list[j/2] = list[j]; j = j *2; } } list [j/2] = k; } void initial_heap( int list[], int n) { int i; for(i=(n/2);i>=0;i--) adjust(list,i,n-1); } void heapsort(int list[],int n) { int i; initial_heap(list,n); for(i=(n-2); i>=0;i--) { int temp=list[0]; list[0]=list[i+1]; list[i+1]=temp; adjust(list,0,i); } } void readarray(int list[],int n) { int i; printf("\nEnter the elements : "); for(i=0;i<n;i++) scanf("%d",&list[i]); } void printarray(int list[],int n) { int i; printf("\nThe elements of the list are: "); for(i=0;i<n;i++) printf("\t%d",list[i]); } int main() { int list[MAX], n; //clrscr(); printf("\n***** Heap Sort in C *****\n\n"); printf("\nEnter the number of elements : "); scanf("%d",&n); readarray(list,n); printf("\n\nlist before sorting is: "); printarray(list,n); heapsort(list,n); printf("\n\nlist after sorting is: "); printarray(list,n); //getch(); } |
Output
Read Also
Check out our DAA Lab Manual and Programs