C Program For Heap Sort Using Divide And Conquer

Ram Pothuraju
#include<stdio.h>
#include<conio.h>
#define MAX 30
struct heap{
 int S[MAX];

 int heapsize;
}H;
void siftdown(struct heap* H,int i)
{
 int parent,largerchild;
 int siftkey;
 int spotfound;
 siftkey=H->S[i];
 parent=i;
 spotfound=0;

 while(2*parent <= H->heapsize && spotfound==0)
 {
  if(2*parent < H->heapsize && H->S[2*parent] < H->S[2*parent+1])
   largerchild=2*parent+1;
  else
   largerchild=2*parent;

  if(siftkey<h->S[largerchild])
  {
   H->S[parent]=H->S[largerchild];
   parent=largerchild;
  }
  else
   spotfound=1;
 }
 H->S[parent]=siftkey;
}

int root(struct heap* H)
{
 int keyout;
 keyout=H->S[1];
 H->S[1]=H->S[H->heapsize];
 H->heapsize=H->heapsize-1;
 siftdown(H,1);
 return keyout;
}
void removekeys(int n,struct heap* H)
{
 int i;
 for(i=n;i>=1;i--)
 {
  H->S[i]=root(H);
 }
}

void makeheap(int n,struct heap* H)
{
 int i;
 H->heapsize=n;
 for(i=n/2;i>=1;i--)
  siftdown(H,i);
}
void heapsort(int n,struct heap* H)
{
 makeheap(n,H);
 removekeys(n,H);
}
void main()
{
 int n,i,j;
 clrscr();
 printf("\n-------------------------------------------------");
 printf("\n               HEAP SORT USING D & C");
 printf("\n-------------------------------------------------");
 printf("\n Enter number of element you want:");
 scanf("%d",&n);
 for(i=1;i<=n;i++)
 {
  scanf("%d",&H.S[i]);
 }
 heapsort(n,&H);
 printf("\n-------------------------------------------------");
 printf("\n Elements after sorting:");
 for(i=1;i<=n;i++)
 {
        printf("%3d",H.S[i]);
 }
 printf("\n-------------------------------------------------");
getch();
}
</h-></conio.h></stdio.h>


OUTPUT


------------------------------------------------------------------------------------
               HEAP SORT USING D & C
------------------------------------------------------------------------------------
 Enter number of element you want:8
11
95
25
74
36
12
10
45

------------------------------------------------------------------------------------
 Elements after sorting: 10 11 12 25 36 45 74 95
------------------------------------------------------------------------------------


Post a Comment

0Comments

Post a Comment (0)