Heapsort

#include<stdio.h>
#include<conio.h>
#define max 50

struct elem
{
 int info;
}ar[max],tr[max],item;

int noe,i,ptr,par,ind,left,right;

void inp_dat()
{
 do
 {
 printf("\n\n Enter the no. of elements : ");
 scanf("%d",&noe);
 }while(noe<=0 || noe>=max);
 printf("\n\n Enter the '%d' elements of array in unsorted order : ",noe);
 for(i=1;i<=noe;i++)
  scanf("%d",&ar[i].info);
 printf("\n\n The '%d' elements of array in unsorted order :",noe);
 for(i=1;i<=noe;i++)
  printf(" %d",ar[i].info);
}

void ins_heap(int n)
{
 tr[n] = ar[n];
 if(n != 1)
 {
 ptr = n;
 par = ptr/2;
 while(ptr>1 && tr[par].info < tr[ptr].info)
 {
  item = tr[par];
  tr[par] = tr[ptr];
  tr[ptr] = item;
  ptr = par;
  par = ptr/2;
 }
 }
}

void del_heap(int n)
{
 item = tr[1];
 tr[1] = tr[n];
 tr[n] = item;
 par = 1; left = 2; right = 3;
 ind = 0;
 while(par < n && ind == 0)
 {
  if(tr[left].info > tr[par].info && tr[left].info > tr[right].info && left<n)
  {
  item = tr[left];
  tr[left] = tr[par];
  tr[par] = item;
  par = left;
  }
  else if(tr[right].info > tr[par].info && tr[left].info < tr[right].info  && right<n)
  {
  item = tr[right];
  tr[right] = tr[par];
  tr[par] = item;
  par = right;
  }
  else
   ind = 1;
  left = 2*par;
  right = 2*par+1;
 }
 ar[n] = tr[n];
}

void hp_srt()
{
 for(i=1;i<=noe;i++)
  ins_heap(i);
 i = noe;
 while(i>=1)
 {
 del_heap(i);
 i--;
 }
 printf("\n\n The '%d' elements of array in sorted order :",noe);
 for(i=1;i<=noe;i++)
  printf(" %d",ar[i].info);
}

void main()
{
clrscr();
inp_dat();
hp_srt();
getch();
}

Radix Srt

#include<stdio.h>
#include<conio.h>
#include<math.h>
#define max 10

struct ele
{
 int info;
}ar[max],qu[10][max],temp;

int noe,i,j,k,size,end,small,posn,flag;
int front[max],rear[max];

void inp_dat()
{
 do
 {
 printf("\n\n Enter the no. of elements : ");
 scanf("%d",&noe);
 }while(noe<=0 || noe>=max);
 printf("\n\n Enter the '%d' elements of array in unsorted order : ",noe);
 for(i=0;i<noe;i++)
 {
 scanf("%d",&ar[i].info);
 front[i] = rear[i] = 0;
 }
 printf("\n\n The '%d' elements of array in unsorted order :",noe);
 for(i=0;i<noe;i++)
  printf(" %d",ar[i].info);
}

void rdx_srt()
{
  int dig = 1,rem,exp,cnt=0,l,m;
 do
 {
  flag =0; m = 0;
  for(i=0;i<10;i++)
   rear[i] = 0;
  for(i=0;i<noe;i++)
  {
   exp = pow(10,dig-1);
   rem = (ar[i].info/exp) % 10;
   qu[rem][rear[rem]] = ar[i];
   rear[rem]++;
  }
  for(j=0;j<10;j++)
  {
   for(k=0;k<rear[j];k++)
    ar[m++] = qu[j][k];
  }
  printf("\n After Pass %d the array is :",++cnt);
  for(l=0;l<noe-1;l++)
  {
  printf(" %d",ar[l].info);
   if(ar[l].info > ar[l+1].info)
    flag=1;
  }
  printf(" %d",ar[l].info);
  dig+=1;
 }while(flag==1);

 printf("\n\n\n The '%d' elements of array in sorted order :",noe);
 for(i=0;i<noe;i++)
  printf(" %d",ar[i].info);
}

void main()
{
 clrscr();
 inp_dat();
 rdx_srt();
 getch();
}

Merge Sort (Better Code)

#include<stdio.h>
#include<conio.h>
#define max 10

struct ele
{
 int info;
}ar[max],A[max],B[max],C[max];

int noe,i,j,k,size,mgsize,end,small,posn,flag,na,nb,nc;

void inp_dat()
{
 do
 {
 printf("\n\n Enter the no. of elements : ");
 scanf("%d",&noe);
 }while(noe<=0 || noe>=max);
 printf("\n\n Enter the '%d' elements of array in unsorted order : ",noe);
 for(i=0;i<noe;i++)
  scanf("%d",&ar[i].info);
 printf("\n\n The '%d' elements of array in unsorted order :",noe);
 for(i=0;i<noe;i++)
  printf(" %d",ar[i].info);
}

void merge()
{
 int a,b;
 for(a=0,b=0;a<na && b<nb;)
 {
  if(A[a].info <= B[b].info)
   C[nc++] = A[a++];
  else
   C[nc++] = B[b++];
 }
 while(a<na)
  C[nc++] = A[a++];
 while(b<nb)
  C[nc++] = B[b++];
}

void mrg_srt()
{
 int cnt = 0;
 size = 1;
 do
 {
 mgsize = size*2;
 for(i=0;i<noe;i+=mgsize)
  {
  end = i+mgsize >= noe ? noe:i+mgsize;
  na = nb = nc = 0;
  for(j=i;j<i+size;j++)
   A[na++] = ar[j];
  for(;j<end;j++)
   B[nb++] = ar[j];
  merge();
  for(j=0,k=i;j<nc;j++)
   ar[k++] = C[j];
  }
  printf("\n After Pass %d the array is :",++cnt);
  for(i=0;i<noe;i++)
   printf(" %d",ar[i].info);
  size = mgsize;
 }while(size<noe);
 printf("\n\n\n The '%d' elements of array in sorted order :",noe);
 for(i=0;i<noe;i++)
  printf(" %d",ar[i].info);

}

void main()
{
 clrscr();
 inp_dat();
 mrg_srt();
 getch();
}

Merge Sort

#include<stdio.h>
#include<conio.h>
#define max 10
struct ele
{
 int info;
}ar[max],temp;

int noe,i,j,k,size,end,small,posn,flag;

void inp_dat()
{
 do
 {
 printf("\n\n Enter the no. of elements : ");
 scanf("%d",&noe);
 }while(noe<=0 || noe>=max);
 printf("\n\n Enter the '%d' elements of array in unsorted order : ",noe);
 for(i=0;i<noe;i++)
  scanf("%d",&ar[i].info);
 printf("\n\n The '%d' elements of array in unsorted order :",noe);
 for(i=0;i<noe;i++)
  printf(" %d",ar[i].info);
}

void mrg_srt()
{

 int cnt = 0;
 size = 1;
 do
 {
 size *=2;
 printf("\n");
 for(i=0;i<noe;i+=size)
  {
  end = i+size >= noe ? noe:i+size;
  for(j=i;j<end;j++)
  {
   flag = 0;
   small = ar[j].info;
   for(k=j+1;k<end;k++)
    {
    if(small > ar[k].info)
    {
     small = ar[k].info; posn =k ;  flag = 1;
    }
    }
    if(flag==1)
     {
     temp = ar[j];
     ar[j] = ar[posn];
     ar[posn] = temp;
     }
   }
  }
  printf("\n After Pass %d the array is :",++cnt);
  for(i=0;i<noe;i++)
   printf(" %d",ar[i].info);
 }while(size<noe);
 printf("\n\n\n The '%d' elements of array in sorted order :",noe);
 for(i=0;i<noe;i++)
  printf(" %d",ar[i].info);
}
void main()
{
 clrscr();
 inp_dat();
 mrg_srt();
 getch();
}

Huffman Tree Algorithm (Complex)

#include<iostream.h>
#include<conio.h>
#include<stdio.h>
#include<process.h>
#include<iomanip.h>
const MAX=55;
class m_heap      //a min heap
{ private:
int T[MAX],N,loc[MAX];//coz we take here,d sequential representation of trees here;
public:
m_heap()
{ N=0;
}
void insert(int item,int l)
{    N++;
    int ptr=N,par;
    while(ptr>1)
    {         par=ptr/2;
      if(item>=T[par])
      {        T[ptr]=item;
loc[ptr]=l;
return;
      }
      T[ptr]=T[par];
      loc[ptr]=loc[par];
      ptr=par;
    };
    T[1]=item;
    loc[1]=l;
}
void Sdis()
{ for(int i=1;i<=N;i++)
cout<<endl<<setw(9)<<T[i]<<setw(9)<<loc[i];
}
int del(int &lo)
{      int item=T[1],l=loc[1],last=T[N],ll=loc[N],ptr=1,left=2,right=3;
      N--;
      while(right<=N)
      {       if(last<=T[left] && last<=T[right])
{T[ptr]=last;
loc[ptr]=ll;
break;
}
if(T[right]>=T[left])
      { T[ptr]=T[left];
loc[ptr]=loc[left];
ptr=left;
      }
else
{T[ptr]=T[right];
loc[ptr]=loc[right];
ptr=right;
}

left=2*ptr;
right=left+1;
      };
      if(left==N && last>T[left])
      {ptr=left;
      T[1]=T[left];
      loc[1]=loc[left];
      }
      T[ptr]=last;
      loc[ptr]=ll;
      lo=l;
      return item;
}
int retN()
{ return N;
}



};
class hoffman
{ private:
int wt[MAX],left[MAX],right[MAX],n;
char info[MAX];
public:
void insert()
{       cout<<"Enter the no. of external nodes u want:";
cin>>n;
cout<<"\nEnter information and weight in order(info wt):";
for(int i=1;i<=n;i++)
{ cin>>info[i]>>wt[i];
left[i]=0;
right[i]=0;
}
}
void dis()
{
cout<<"s.no"<<setw(9)<<"INFO"<<setw(9)<<"WEIGHT"<<setw(9)<<"LEFT"<<setw(9)<<"RIGHT";
for(int i=1;i<=n;i++)
cout<<endl<<i<<"         "<<info[i]<<setw(9)<<wt[i]<<setw(9)<<left[i]<<setw(9)<<right[i];
}
void hoff()
{ m_heap H;
int w1,w2,l1,l2;
for(int i=1;i<=n;i++)
H.insert(wt[i],i);
while(1)
{     if(H.retN()==0)
    { n--;
     break;
    }

     w1=H.del(l1);
     w2=H.del(l2);
     n++;
     wt[n]=w1+w2;
     left[n]=l1;
     right[n]=l2;
     info[n]=' ';
     H.insert(wt[n],n);
}
}


};

void main()
{               clrscr();
hoffman H;
H.insert();
g:
clrscr();
cout<<"HOFFMAN menu:";
cout<<"\n1.> display";
cout<<"\n2.> Create Hoffman's tree";
cout<<"\n3.> Exit";
cout<<"\nEnter your choice:";
char ch;
cin>>ch;
switch(ch)
{ case '1':clrscr();
H.dis();
getch();
goto g;
case '2':clrscr();
H.hoff();
getch();
goto g;
default: exit(0);
};
getch();
}

Shell Sort (Better Code)

#include<stdio.h>
#include<conio.h>
#define max 10
struct ele
{
 int info;
}ar[max],temp;

int noe,i,j,k,size,small,posn,flag;

void inp_dat()
{
 do
 {
 printf("\n\n Enter the no. of elements : ");
 scanf("%d",&noe);
 }while(noe<=0 || noe>=max);
 printf("\n\n Enter the '%d' elements of array in unsorted order : ",noe);
 for(i=0;i<noe;i++)
  scanf("%d",&ar[i].info);
 printf("\n\n The '%d' elements of array in unsorted order :",noe);
 for(i=0;i<noe;i++)
  printf(" %d",ar[i].info);
}

void shl_srt()
{

 int cnt = 0;
 size = noe/2;
 do
 {
 printf("\n (Size = %d)",size);
 for(i=size;i<noe;i++)
 {
  temp = ar[i];
  j = i;
  while(ar[j-size].info>temp.info && j>=0)
  {
   ar[j] = ar[j-size];
   j -= size;
  }
  ar[j] = temp;
 }
  printf("\n After Pass %d the array is :",++cnt);
  for(i=0;i<noe;i++)
   printf(" %d",ar[i].info);
  size /= 2;
 }while(size>=1);
 printf("\n\n\n The '%d' elements of array in sorted order :",noe);
 for(i=0;i<noe;i++)
  printf(" %d",ar[i].info);
}

void main()
{
 clrscr();
 inp_dat();
 shl_srt();
 getch();
}

Shell Sort

#include<stdio.h>
#include<conio.h>
#define max 10
struct ele
{
 int info;
}ar[max],temp;

int noe,i,j,k,size,small,posn,flag;

void inp_dat()
{
 do
 {
 printf("\n\n Enter the no. of elements : ");
 scanf("%d",&noe);
 }while(noe<=0 || noe>=max);
 printf("\n\n Enter the '%d' elements of array in unsorted order : ",noe);
 for(i=0;i<noe;i++)
  scanf("%d",&ar[i].info);
 printf("\n\n The '%d' elements of array in unsorted order :",noe);
 for(i=0;i<noe;i++)
  printf(" %d",ar[i].info);
}

void shl_srt()
{

 int cnt = 0;
 size = noe%2 == 0 ? noe-1: noe;
 do
 {
 printf("\n (Size = %d)",size);
 for(i=0;i<size;i++)
 {
  for(j=i;j<noe;j+=size)
  {
   flag = 0;
   small = ar[j].info;
   for(k=j+size;k<noe;k+=size)
    {
    if(small > ar[k].info)
    {
     small = ar[k].info; posn =k ;  flag = 1;
    }
    }
    if(flag==1)
     {
     temp = ar[j];
     ar[j] = ar[posn];
     ar[posn] = temp;
     }
   }
  }
  printf("\n After Pass %d the array is :",++cnt);
  for(i=0;i<noe;i++)
   printf(" %d",ar[i].info);
  size -= 2;
 }while(size>=1);
 printf("\n\n\n The '%d' elements of array in sorted order :",noe);
 for(i=0;i<noe;i++)
  printf(" %d",ar[i].info);
}
void main()
{
 clrscr();
 inp_dat();
 shl_srt();
 getch();
}

Quicksort

#include<stdio.h>
#include<conio.h>
#define max 50
struct ele
{
 int info;
}ar[max],stup[max],stlw[max],tmp;


int noe,i,beg,end,top,loc,left,right;


void inp_dat()
{
 do
 {
 printf("\n\n Enter the no. of elements : ");
 scanf("%d",&noe);
 }while(noe<=0 || noe>=max);
 printf("\n\n Enter the '%d' elements of array in unsorted order : ",noe);
 for(i=0;i<noe;i++)
  scanf("%d",&ar[i].info);
 printf("\n\n The '%d' elements of array in unsorted order :",noe);
 for(i=0;i<noe;i++)
  printf(" %d",ar[i].info);
}


void quick(int &beg,int &end,int &loc)
{
 left = beg;
 right = end;
 loc = beg;
 while(loc != right || loc !=left)
 {
  while(ar[loc].info <= ar[right].info && right != loc)
    right -= 1;
  if(ar[loc].info > ar[right].info)
  {
   tmp = ar[loc];
   ar[loc] = ar[right];
   ar[right] = tmp;
   loc = right;
  }
  while(ar[loc].info >= ar[left].info && left != loc)
    left += 1;
  if(ar[loc].info < ar[left].info)
  {
   tmp = ar[loc];
   ar[loc] = ar[left];
   ar[left] = tmp;
   loc = left;
  }
 }
}


void qk_srt()
{
top = 0;
stlw[top].info = 0;   stup[top].info = noe-1;
while(top != -1)
{
 beg = stlw[top].info;
 end = stup[top].info;
 top = top-1;
 quick(beg,end,loc);
 if(beg < loc-1)
 {
 top = top+1;
 stlw[top].info = beg;   stup[top].info = loc-1;
 }
 if(loc+1 < end)
 {
 top = top+1;
 stlw[top].info = loc+1;   stup[top].info = end;
 }
}
 printf("\n\n The '%d' elements of array in sorted order :",noe);
 for(i=0;i<noe;i++)
  printf(" %d",ar[i].info);
}


void main()
{
clrscr();
inp_dat();
qk_srt();
getch();
}