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

Popular posts from this blog

MVT (Multiprogramming Variable Task) in C Programming

#include< stdio.h> #include< conio.h> void main() { int i,os_m,nPage,total,pg[25]; clrscr(); printf("\nEnter total memory size:"); scanf("%d",&total); printf("\nEnter memory for OS:"); scanf("%d",&os_m); printf("\nEnter no. of pages:"); scanf("%d",&nPage); for(i=0;i< nPage;i++) { printf("Enter size of page[%d]:",i+1); scanf("%d",&pg[i]); } total=total-os_m; for(i=0;i< nPage;i++) { if(total>=pg[i]) { printf("\n Allocate page %d",i+1); total=total-pg[i]; } else printf("\n page %d is not allocated due to insufficient memory.",i+1); } printf("\n External Fragmentation is:%d",total); getch(); } OUTPUT Enter total memory size:1024 Enter memory for OS:256 Enter no. of pages:4 Enter size of page[1]:128 Enter size of page[2]:512 Enter size of page[3]:64 Enter size of page[4]:512 Allocate page 1 Al

implement Rail fence cipher in Java

// File Name: RailFence.java import java.util.*; class RailFenceBasic{ int depth; String Encryption(String plainText,int depth)throws Exception { int r=depth,len=plainText.length(); int c=len/depth; char mat[][]=new char[r][c]; int k=0; String cipherText=""; for(int i=0;i< c;i++) { for(int j=0;j< r;j++) { if(k!=len) mat[j][i]=plainText.charAt(k++); else mat[j][i]='X'; } } for(int i=0;i< r;i++) { for(int j=0;j< c;j++) { cipherText+=mat[i][j]; } } return cipherText; } String Decryption(String cipherText,int depth)throws Exception { int r=depth,len=cipherText.length(); int c=len/depth; char mat[][]=new char[r][c]; int k=0; String plainText=""; for(int i=0;i< r;i++) { for(int j=0;j< c;j++) { mat[i][j]=cipherText.charAt(k++); } } for(int i=0;i< c;i++) { for(int j=0;j< r;j++) { plainText+=mat[j][i]; } }

Deadlock Prevention using Banker’s Algorithm in C Programming

#include< stdio.h> #include< conio.h> void main() { int allocated[15][15],max[15][15],need[15][15],avail[15],tres[15],work[15],flag[15]; int pno,rno,i,j,prc,count,t,total; count=0; clrscr(); printf("\n Enter number of process:"); scanf("%d",&pno); printf("\n Enter number of resources:"); scanf("%d",&rno); for(i=1;i< =pno;i++) { flag[i]=0; } printf("\n Enter total numbers of each resources:"); for(i=1;i<= rno;i++) scanf("%d",&tres[i]); printf("\n Enter Max resources for each process:"); for(i=1;i<= pno;i++) { printf("\n for process %d:",i); for(j=1;j<= rno;j++) scanf("%d",&max[i][j]); } printf("\n Enter allocated resources for each process:"); for(i=1;i<= pno;i++) { printf("\n for process %d:",i); for(j=1;j<= rno;j++) scanf("%d",&allocated[i][j]); } printf("\n avai