You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
105 lines
2.7 KiB
C
105 lines
2.7 KiB
C
/*
|
|
* C Program to sort an array based on heap sort algorithm(MAX heap)
|
|
*/
|
|
#include <stdio.h>
|
|
|
|
void main()
|
|
{
|
|
int heap[10], no, i, j, c, root, temp;
|
|
printf("\n Enter no of elements :");
|
|
scanf("%d", &no);
|
|
printf("\n Enter the nos : ");
|
|
for (i = 0; i < no; i++)
|
|
scanf("%d", &heap[i]);
|
|
for (i = 1; i < no; i++)
|
|
{
|
|
c = i;
|
|
do
|
|
{
|
|
root = (c - 1) / 2;
|
|
if (heap[root] < heap[c]) /* to create MAX heap array */
|
|
{
|
|
temp = heap[root];
|
|
heap[root] = heap[c];
|
|
heap[c] = temp;
|
|
}
|
|
c = root;
|
|
}
|
|
while (c != 0);
|
|
}
|
|
printf("Heap array : ");
|
|
for (i = 0; i < no; i++)
|
|
printf("%d\t ", heap[i]);
|
|
for (j = no - 1; j >= 0; j--)
|
|
{
|
|
temp = heap[0];
|
|
heap[0] = heap[j /* swap max element with rightmost leaf element */
|
|
heap[j] = temp;
|
|
root = 0;
|
|
do
|
|
{
|
|
c = 2 * root + 1; /* left node of root element */
|
|
if ((heap[c] < heap[c + 1]) && c < j-1)
|
|
c++;
|
|
if (heap[root]<heap[c] && c<j) /* again rearrange to max heap array */
|
|
{
|
|
temp = heap[root];
|
|
heap[root] = heap[c];
|
|
heap[c] = temp;
|
|
}
|
|
root = c;
|
|
}
|
|
while (c < j);
|
|
}
|
|
printf("\n The sorted array is : ");
|
|
for (i = 0; i < no; i++)
|
|
printf("\t %d", heap[i]);
|
|
printf("\n Complexity : \n Best case = Avg case = Worst case = O(n logn) \n");
|
|
}
|
|
/*
|
|
*OUTPUT:
|
|
Average case
|
|
Enter no of elements :7
|
|
|
|
Enter the nos : 6
|
|
5
|
|
3
|
|
1
|
|
8
|
|
7
|
|
2
|
|
Heap array : 8 6 7 1 5 3 2
|
|
The sorted array is : 1 2 3 5 6 7 8
|
|
Complexity :
|
|
Best case = Avg case = Worst case = O(n logn)
|
|
|
|
/* Best case
|
|
Enter no of elements :7
|
|
|
|
Enter the nos : 12
|
|
10
|
|
8
|
|
9
|
|
7
|
|
4
|
|
2
|
|
Heap array : 12 10 8 9 7 4 2
|
|
The sorted array is : 2 4 7 8 9 10 12
|
|
Complexity :
|
|
Best case = Avg case = Worst case = O(n logn)
|
|
|
|
/* Worst case
|
|
Enter no of elements :7
|
|
|
|
Enter the nos : 5
|
|
7
|
|
12
|
|
6
|
|
9
|
|
10
|
|
14
|
|
Heap array : 14 9 12 5 6 7 10
|
|
The sorted array is : 5 6 7 9 10 12 14
|
|
Complexity :
|
|
Best case = Avg case = Worst case = O(n logn)
|
|
*/ |