Skip to main content

Heap sort using Divide & Conquer

#include
#include
#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(siftkeyS[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();
}

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
------------------------------------------------------------------------------------

Comments

  1. hey, can you explain me, what is "spotfound", "siftdown", "siftkey", and "keyout" ???
    thanks

    ReplyDelete
  2. Harrah's Casino and Hotel - Jordan 10 Retro Outlet
    Harrah's Casino where can you buy air jordan 18 retro varsity red and Hotel, air jordan 18 retro red shipping owned by Vici Properties, Inc., is an indian casino and hotel located find air jordan 18 retro racer blue in West Virginia. It how can i buy air jordan 18 retro toro mens sneakers is located in West Virginia and 토토 커뮤니티 is

    ReplyDelete

Post a Comment