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