C Menu
- Basics of C
- Basics of C Programming
- Features of C Programming
- Preprocessors in C Programming
- History of C Programming
- Low Level Programming
- Why C is Middle Level Language
- Introduction to C programming
- Structure of a C program
- Input-Output Functions
- Difference between Compiler and Interpreter
- Assembler v/s Compiler v/s Interpreter v/s Linker v/s Loader
- Basics to Code
- Operators in C
- Operators in C
- Precedence Associativity Operators
- Arithmetic Operators
- Relational Operators
- Logical Operators
- Bitwise Operators
- Assignment Operators
- Ternary Operators in C
- Size of Operators
- Conditional Operators
- Comma Operators
- Format Specifiers in C
- Difference between %d and %i
- Difference between %f, %e, %E and %g
- How to print% using printf
- How to print \ using printf
- How to print “” using printf
- What is the use of %p in C
- Library Functions in C
- pow() in C
- sqrt() in C
- Storage Classes in C
- Conditional statements and Decision Making in C
- DataType & Functions in C
- Arrays, String, Structure, Union and Enum
- Pointer in C
- Library Function in C
- Library function in C
- math.h in c
- Library function math.h acos
- Library function math.h acosh
- Library function math.h asin
- Library function math.h asinh
- Library function math.h atan
- Library function math.h atan2
- Library function math.h atanh
- Library function math.h cbrt
- Library function math.h cell
- Library function math.h cos
- Library function math.h cosh
- Library function math.h exp
- Library function math.h fabs
- Library function math.h floor
- Library function math.h hypot
- Library function math.h log
- Library function math.h log10
- Library function math.h pow
- Library function math.h sin
- Library function math.h sinh
- Library function math.h sqrt
- Library function math.h tan
- Library function math.h tanh
- Library function studio.h clearerr
- Library function string.h strcat
- Library function string.h strcmp
- Library function string.h strcpy
- Library function string.h strlen
- File Handling
- Dynamic Memory Allocation
- Miscellaneous Topics in C
- Miscellaneous Coding Questions
PREPINSTA PRIME
Heap Sort Program in C
Heap Sort in C
A heap is a complete binary tree which is represented using array or sequential representation.
It is a special balanced binary tree data structure where root node is compared with its children and arranged accordingly.Normally in max heap parent node is always has a value greater then child node.
The worst and Average complexity of heap sort is O(n log2 n).
- From the given array, build the initial max heap.
- Interchange the root element with the last element.
- Use repetitive downward operation from root node to rebuild the heap of size one less than the starting.
Algorithm of Heap Sort
MAX-HEAPIFY(A,i)
1- i<-left[i]
2- r<-right[i]
3- if l<heap-size[A]and A[l]>A[i]
4- then largest<-1
5- else largest<-i
6- if r<heap-size[A] and A[r]>A[largest]
7- then largest<-r
8- if largest!=i
9- then exchange A[i]<->A[largest]
10- MAX-HEAPIFY[A,largest]
HEAP-SORT(A)
1- BUILD-MAX-HEAP(A)
2- for i<-length[A] down to 2
3- do exchange A[1]<-> heap-size[A]-1
4- heap-size[A]<-heap-size[A]-1
5- MAX-HEAPIFY(A,1)
BUILD-MAX-HEAP(A)
1- heap-size[A]<-length[A]
2- for i<-(length[A]/2) down to 1 do
3- MAX-HEAPIFY(A,i)
Implementation of Heap Sort
As we know that heap sort is based on the tree structure.
so we will take an example of heap sort with the based on tree.
Originally the given array is :[6,14,3,25,2,10,20,7,6]
First we call Build-max heap
heap size[A]=9
so,i=4 to 1, call MAX HEAPIFY (A,i)
i.e., first we call MAX HEAPIFY (A,4)
A[l]=7, A[i]=A[4] = 25,A[r] = 6
l<- left[4] = 8
r<-right[4] = 9
8<9 and 7>25 (false)
Then,largest <-4
9<9 and 6>25(false)
Then,largest = 4
A[i]<-> A[4]
Now call MAX HEAPIFY (A,2)
the A[length] =9
So, i=A/2 = 9/2 =4
i=4
since the parent node is greater than its child node.
If it is parent node is greater than child node then the parent node replace with the lesser child node.
similarly for i=3,2,1 we get the following heap tree.
Now call MAX HEAPIFY
Now we will replace the root node to last child In this photo is shown by replace 25 to 6.
Now call MAX HEAPIFY
Now we will replace the root node to last child In this photo is shown by replace 20 to 6.
Again call MAX HEAPIFY,
we get exchange A[14] and A[3] which is shown by a image.
Again call MAX HEAPIFY,
we get exchange A[10] and A[3] which is shown by a image.
Similarly,call MAX HEAPIFY
we’ll interchange A[7] and A[2]. which is shown by this image.
Similarly,call MAX HEAPIFY
we’ll interchange A[6] and A[3]. which is shown by this image.
Similarly,call MAX HEAPIFY
we’ll interchange A[6] and A[2]. which is shown by this image.
Final,call MAX HEAPIFY
we’ll interchange A[3] and A[2]. which is shown by this image.
and finally array will be sorted.
C Code of Heap Sort
#include<stdio.h> // including library files int temp; void heapify(int arr[], int size, int i)//declaring functions { int max = i; int left = 2*i + 1; int right = 2*i + 2; if (left < size && arr[left] >arr[max]) max= left; if (right < size && arr[right] > arr[max]) max= right; if (max!= i) { // performing sorting logic by using temporary variable temp = arr[i]; arr[i]= arr[max]; arr[max] = temp; heapify(arr, size, max); } } void heapSort(int arr[], int size)// providing definition to heap sort { int i; for (i = size / 2 - 1; i >= 0; i--) heapify(arr, size, i); for (i=size-1; i>=0; i--) { // swaping logic temp = arr[0]; arr[0]= arr[i]; arr[i] = temp; heapify(arr, i, 0); } } void main() // defining main() { int arr[] = {58, 134, 3, 67, 32, 89, 15, 10,78, 9}; // array initializing with their elements. int i; int size = sizeof(arr)/sizeof(arr[0]); heapSort(arr, size); printf("printing sorted elements\n"); // printing the sorted array for (i=0; i<size; ++i) printf("%d ",arr[i]); }
Output
printing sorted elements 3 9 10 15 32 58 67 78 89 134
Sorting
Sorting algorithms are easy to learn but are really important for college semester exams and companies offering package between 3 – 6 LPA would ask direct searching questions in online test/ interviews.
Login/Signup to comment