Heap Sort Program in C, Heap Sort Program Algorithm, heap sort algorithm, computer programming, programming sorting, how to implement a heap, tree heap, code for sorting
 |
| Heap Sort Program |
/*
Nilkanth Shet Shirodkar
HEAP SORT AND FINDING PAIRS FROM THE SORTED ARRAY WHICH PRODUCES SUM TAKEN AS INPUT
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int A[20],X,i=0,n,k=0,root,j,c,temp;
int left,right;
//-------Creating Max Heap
void createMaxHeap()
{
for(i=1;i<n;i++)
{
c=i;
do
{
root=(c-1)/2;
if(A[root]<A[c])
{
temp=A[root];
A[root]=A[c];
A[c]=temp;
}//End of if
c=root;
}while(c!=0);
}
}//End of createMaxHeap*/
//------Heap sort from the heap created
void heapSort()
{
for (j = n - 1; j >= 0; j--)
{
temp = A[0];
A[0] = A[j];
A[j] = temp;
root = 0;
do
{
c = 2 * root + 1;
if ((A[c] < A[c + 1]) && c < j-1)
c++;
if (A[root]<A[c] && c<j)
{
temp = A[root];
A[root] = A[c];
A[c] = temp;
}
root = c;
} while (c < j);
}//End of for
}
//----End of heap sort
//-----Main
void main()
{
int left=0,right=n-1;
printf("========================================\n");
printf("\tHEAP SORT -- FINDING PAIRS\n");
printf("========================================\n");
printf("How many numbers you want to insert?\n");
printf("========================================\n");
scanf("%d",&n);
printf("Enter elements\n");
for(i=0;i<n;i++)
scanf("%d",&A[i]);
printf("========================================\n");
printf("Input Elements are\n");
for(i=0;i<n;i++)
{
printf("%d ",A[i]);
}
printf("\n========================================\n");
createMaxHeap();
printf("Heap Order is\n");
for(k=0;k<n;k++)
printf("%d ",A[k]);
printf("\n========================================\n");
heapSort();
printf("Sorted Array\n");
for(i=0;i<n;i++)
{
printf("%d ",A[i]);
}
printf("\n========================================\n");
printf("Enter a value of X(SUM)\n");
scanf("%d",&X);
printf("========================================\n");
//------Finding Unique Pairs
left=0;
right=n-1;
int count=0;
while(left<right)
{
int sum=0;
sum=A[left]+A[right];
if(sum==X)
{
printf("(%d,%d)",A[left],A[right]);
printf("\n========================================\n");
left++;
right--;
count=count+1;
continue;
}
else if(sum<X)
left++;
else if(sum>X)
right--;
}//End of while
if(count==0)
{
printf("No pairs found"); printf("\n========================================\n");
}
//----End of Finding unique pairs
}//End of main
Heap Sort Program
#include<stdio.h>
#include<string.h>
struct student{
char roll_no[5];
char name[50];
int marks;
}student[20],temp;
int i,j,s,root,c,swap;
void main(){
FILE *f,*output;
s=0;swap=0;
f=fopen("input.txt","r");
output=fopen("output.txt","w");
while(fscanf(f,"%s %s %d",&student[s].roll_no,&student[s].name,&student[s].marks)!=EOF)
{
printf("%s %s %d\n",student[s].roll_no,student[s].name,student[s].marks);
s++;
}
createMaxHip();
printf("\nHeap data:\n");
for(i=0;i<s;i++)
printf("%s %s %d\n",student[i].roll_no,student[i].name,student[i].marks);
heapSort();
printf("\nNumber of swapping required is %d.\nSorted data:\n",swap);
for(i=0;i<s;i++){
printf("%s %s %d\n",student[i].roll_no,student[i].name,student[i].marks);
fprintf(output,"%s %s %d\n",student[i].roll_no,student[i].name,student[i].marks);
}
}//end of main()
void createMaxHip(){
for(i=0;i<s;i++)
{
c=i;
do{
root=(c-1)/2;
if(strcmp(student[root].roll_no,student[c].roll_no)<0){
strcpy(temp.roll_no,student[root].roll_no);
strcpy(temp.name,student[root].name);
temp.marks=student[root].marks;
strcpy(student[root].roll_no,student[c].roll_no);
strcpy(student[root].name,student[c].name);
student[root].marks=student[c].marks;
strcpy(student[c].roll_no,temp.roll_no);
strcpy(student[c].name,temp.name);
student[c].marks=temp.marks;
}
c=root;
}while(c!=0);
}
}//end of createmaxhip()
void heapSort(){
for(j=s-1;j>=0;j--,swap++)
{
/*temp.roll_no=student[0];
student[0]=student[j];
student[j]=temp;*/
//swap++;
strcpy(temp.roll_no,student[0].roll_no);
strcpy(temp.name,student[0].name);
temp.marks=student[0].marks;
strcpy(student[0].roll_no,student[j].roll_no);
strcpy(student[0].name,student[j].name);
student[0].marks=student[j].marks;
strcpy(student[j].roll_no,temp.roll_no);
strcpy(student[j].name,temp.name);
student[j].marks=temp.marks;
root=0;
do
{
c=2*root+1;
if((strcmp(student[c].roll_no,student[c+1].roll_no)<0) && (c<j-1))
c++;
if((strcmp(student[root].roll_no,student[c].roll_no)<0) && (c<j))
{
/*temp=student[root];
student[root]=student[c];
student[c]=temp;
*/
strcpy(temp.roll_no,student[root].roll_no);
strcpy(temp.name,student[root].name);
temp.marks=student[root].marks;
strcpy(student[root].roll_no,student[c].roll_no);
strcpy(student[root].name,student[c].name);
student[root].marks=student[c].marks;
strcpy(student[c].roll_no,temp.roll_no);
strcpy(student[c].name,temp.name);
student[c].marks=temp.marks;
}
root=c;
}while(c<j);
}
}//end of heapSort()
