Linked Lists
What is Linked Lists? Singly Linked Lists Doubly Linked Lists Circular Linked Lists Header Linked ListsStacks
What is Stack? Push Operation Pop Operation Peek Operation Linked Stack Multiple StacksQueues
What is Queues? Linear QueueSearching
What is Searching? Linear Search Binary Search Interpolation Search Jump SearchSorting
What is Sorting? Bubble Sort Insertion Sort Selection Sort Merge Sort Quick Sort Radix Sort Heap Sort Shell Sort Tree SortHashing
What is Hashing? What is Collision?The ones who are crazy enough to think they can change the world are the ones who do.- Steve Jobs
Heap Sort
A Heap sort algorithm works by first organsizing the data to be sorted into a special type of binary tree by setting the largest element of an array in the top of the binary tree, so the heap sort algorithm is very capable of reversing its order at any time.
Advantages - Heap Sort
- Like insertion sort algorithm, but unlike merge sort algorithm, the heap sort algorithm sorts in place.
- Heap sort algorithm is simple, fast, and stable sorting algorithm which can be used to sort large sets of data.
Disadvantages - Heap Sort
- Heap sort algorithm uses 0(1) memory space for the sorting operation.
- Heap sort algorithm's worst case comes with the running time of 0(n log (n)) which is more likely to merge sort algorithm.
C program - Heap Sort
Here is the program to demonstrate Heap Sort.
heap-sort.c
#include <stdio.h>
int x[100], n, i;
int main()
{
void buildheap();
void heapsort();
printf("\n Enter the size of the array : ");
scanf("%d",&n);
printf("\nEnter %d elements in the array : \n",n);
for(i = 1; i <= n; ++i)
scanf("%d", &x[i]);
buildheap();
heapsort();
printf("\nSorted Array in ascending order is : \n");
for(i = 1;i <= n; ++i)
printf("%5d", x[i]);
return 0;
}
void buildheap()
{
int j, k, temp;
for(k=2; k < n; ++k)
{
i = k;
temp = x[k];
j = i / 2;
while((i > 1) && (temp > x[j]))
{
x[i] = x[j];
i = j;
j = i / 2;
if(j < 1)
j = 1;
}
x[i] = temp;
}
}
void heapsort()
{
int j, k, temp, value;
for(k=n; k >= 2;--k)
{
temp = x[1];
x[1] = x[k];
x[k] = temp;
i=1;
value = x[1];
j = 2;
if((j+1) < k)
if(x[j+1] > x[j])
j++;
while((j <= (k-1)) && (x[j] > value))
{
x[i] = x[j];
i = j;
j = 2*i;
if((j+1) < k)
if(x[j+1] > x[j])
j++;
else
if(j > n)
j = n;
x[i] = value;
}
}
}
Enter the size of the array : 5 Enter 5 elements in the array : 4 3 1 2 5 Sorted Array in ascending order is : 1 2 3 4 5
Related to Heap Sort
Report Us
We may make mistakes(spelling, program bug, typing mistake and etc.), So we have this container to collect mistakes. We highly respect your findings.
Report
Programming
Electrical
Interview
© Copyright 2019