Program for Heap Sort. Kinda tricky program. If you need help, comment below
#include<stdio.h> int tree[20],n,ah[20],c=0; void build(int m,int item) { int ptr,par,f=0; m=m+1; ptr=m; while(ptr>1) { par=ptr/2; if(item<=tree[par]) { tree[ptr]=item; f=1; break; } tree[ptr]=tree[par]; ptr=par; } if(f==0) tree[1]=item; } void delheap(int k,int m) { int left,right,ptr,last,i; ah[k]=tree[1]; last=tree[m]; m=m-1; ptr=1; left=2; right=3; while(right<=m) { if((last>=tree[left])&&(last>=tree[right])) { tree[ptr]=last; return; } if(tree[right]<=tree[left]) { tree[ptr]=tree[left]; ptr=left; } else { tree[ptr]=tree[right]; ptr=right; } left=2*ptr; right=left+1; } if((left==m)&&(last<tree[left])) { tree[ptr]=tree[left]; ptr=left; } tree[ptr]=last; c++; printf("\n\nPass %d: ",c); for(i=1;i<=m;i++) printf("%d ",tree[i]); } main() { int i,j; printf("\nEnter total number of elements:"); scanf("%d",&n); printf("\nEnter elements to be inserted : "); for(i=1;i<=n;i++) scanf("%d",&tree[i]); for(i=1;i<n;i++) build(i,tree[i+1]); printf("\n\nHeap : "); for(i=1;i<=n;i++) printf("%d ",tree[i]); for(i=n,j=1;i>1;i--,j++) delheap(j,i); if(i==1) ah[n]=tree[1]; printf("\n\nHeap sort : "); for(i=1;i<=n;i++) printf("%d ",ah[i]); }
#include<stdio.h> int tree[20],n,ah[20],c=0; void build(int m,int item) { int ptr,par,f=0; m=m+1; ptr=m; while(ptr>1) { par=ptr/2; if(item<=tree[par]) { tree[ptr]=item; f=1; break; } tree[ptr]=tree[par]; ptr=par; } if(f==0) tree[1]=item; } void delheap(int k,int m) { int left,right,ptr,last,i; ah[k]=tree[1]; last=tree[m]; m=m-1; ptr=1; left=2; right=3; while(right<=m) { if((last>=tree[left])&&(last>=tree[right])) { tree[ptr]=last; return; } if(tree[right]<=tree[left]) { tree[ptr]=tree[left]; ptr=left; } else { tree[ptr]=tree[right]; ptr=right; } left=2*ptr; right=left+1; } if((left==m)&&(last<tree[left])) { tree[ptr]=tree[left]; ptr=left; } tree[ptr]=last; c++; printf("\n\nPass %d: ",c); for(i=1;i<=m;i++) printf("%d ",tree[i]); } main() { int i,j; printf("\nEnter total number of elements:"); scanf("%d",&n); printf("\nEnter elements to be inserted : "); for(i=1;i<=n;i++) scanf("%d",&tree[i]); for(i=1;i<n;i++) build(i,tree[i+1]); printf("\n\nHeap : "); for(i=1;i<=n;i++) printf("%d ",tree[i]); for(i=n,j=1;i>1;i--,j++) delheap(j,i); if(i==1) ah[n]=tree[1]; printf("\n\nHeap sort : "); for(i=1;i<=n;i++) printf("%d ",ah[i]); }
No comments:
Post a Comment