Saturday, December 13, 2014

Shell Sort code in C++

 Other Type Of Sorting : Click here :: most important ::


#include<iostream.h>
#include<conio.h>
 void display(int *arr,int n)
{
 cout<<endl;
 for(int i=0;i<=n;i++){
 cout<<arr[i]<<"\t"; }
 cout<<endl;
}

void shellsort(int *arr,int n)
{
 int gap,i,j,temp;
 for(gap=n/2;gap>0;gap/=2)
 {
 for(i=gap;i<=n;i++)
 {
 for(j=i-gap;j>=0 && arr[j]>arr[j+gap];j-=gap)
 {
 display(arr,n);
 temp=arr[j];
 arr[j]=arr[j+gap];
 arr[j+gap]=temp;
 }
 }
 }
}

void main()
{
int x[]={12,7,3,8,1,5,2};
clrscr();
display(x,6);
shellsort(x,6);
display(x,6);
getch();
}

Quick Sort code in C++

 Other Type Of Sorting : Click here :: most important ::


#include <iostream.h>
#include <stdlib.h>
#include <conio.h>
void display(int *x,int s)
{
cout<<endl;
for(int i=0;i<s;i++)
{
cout<<x[i]<<"  ";
}}


int partition(int* A, int p, int r)
{
 int pivot = r;
 int low = p;
 int high = r-1;
 while(low<high)
 {              display(A,9);
while(low<high && A[low]<A[pivot])
{
low++;
}
while(low<high && A[high]>A[pivot])
{
high--;
}
if(A[high]<A[low]){
int n=A[low];
A[low]=A[high];
A[high]=n;        }



 }   if(A[low]>A[pivot]) {
 int temp=A[low];
 A[low]=A[pivot];
 A[pivot]=temp;     }
 return low;
}
void quickSort(int* A, int p, int r)
{
if( p < r )
{
int q = partition(A, p, r);

quickSort(A, p, q-1);
quickSort(A, q+1, r);
}
}
void main()
{
clrscr();
int A[]={3,1,2,8,7,4,5,6,9};
quickSort(A, 0,8);

display(A,9);
getch();
}
---------------------------------
Another : -
----------------------------------
#include <iostream.h>
#include <conio.h>
void swap(int *a,int b,int c)
{
int temp=a[b];
a[b]=a[c];
a[c]=temp;
}
void display(int *a,int s)
{
cout<<endl;
for(int i=0;i<=s;i++){
cout<<a[i]<<"  ";  }
cout<<endl;
}

void quickSort(int *a,int,int);

int partition(int *, int,int);

void main()
{
    int A[] = {6,10,13,5,8,3,2,25,4,11};
    int p=0;
    int q=10;
    clrscr();
    cout<<"======Original======="<<endl;
    display(A,9);
    quickSort(A,p,q);
    cout<<"======Sorted======="<<endl;
    display(A,9);
    getch();
}


void quickSort(int  *A, int p,int q)
{
    int r;
    if(p<q)
    {   display(A,9);   getch();
    r=partition(A, p,q);
    quickSort(A,p,r);
    display(A,9);          getch();
    quickSort(A,r+1,q);
    display(A,9);
    }
}
int partition(int *A, int p,int q)
{
    int x= A[p];
    int i=p;
    int j;
    for(j=p+1; j<q; j++)
    {   display(A,9);  getch();
    if(A[j]<=x)
    {
        i=i+1;
        swap(A,i,j);
    }
    }
    swap(A,i,p);
    return i;
}

Selection Sort code in C++


 Other Type Of Sorting : Click here :: most important ::



#include<iostream.h>
#include<conio.h>
void display(int *arr,int size)
{
 cout<<endl;
 for(int i=0;i<=size;i++){
 cout<<arr[i]<<"\t";     }
}

int find_min_index(int *arr,int start,int n)
{
 int posmin=start;
 int index;
 for(index=start;index<=n;index++){
 display(arr,n);
 if(arr[index]<arr[posmin]){
 posmin=index;
 cout<<"\n Min index = "<<posmin<<"\t Value = "<<arr[posmin]<<"\n";
 }
 }
return posmin;
}

void selection_sort(int *arr,int n)
{
 int posmin,count,temp;
 for(count=0;count<=n;count++)
 {
 posmin=find_min_index(arr,count,n);
 temp=arr[posmin];
 arr[posmin]=arr[count];
 arr[count]=temp;
 }
}

void main()
{
int x[]={12,5,7,1,9,4,8};
clrscr();
selection_sort(x,6);
display(x,6);
getch();
}

Insertion Sort Code in C++


 Other Type Of Sorting : Click here :: most important ::



#include<iostream.h>
#include<conio.h>

void display(int *arr,int n)
{
 cout<<endl;
 for(int i=0;i<=n;i++){
 cout<<arr[i]<<"\t";  }
}

void insertion_sort(int *arr,int n)
{
 int pos,count,val;
 for(count=1;count<=n;count++)
 {
 val=arr[count];
 for(pos=count-1;pos>=0;pos--)
 {
 if(arr[pos]>val)     {
 cout<<"\n Swapped arr["<<pos+1<<"] with arr["<<pos<<"]\n";
 arr[pos+1]=arr[pos]; }
 else { break; };
 }
 arr[pos+1]=val;
 display(arr,6);
 }
}

void main()
{
int x[]={12,4,7,2,9,5,1};
clrscr();
display(x,6);
insertion_sort(x,6);
getch();
}


Bubble Sort Code in C++


 Other Type Of Sorting : Click here :: most important ::



#include<iostream.h>
#include<conio.h>

void display(int *arr,int n)
{
 cout<<endl;
 for(int i=0;i<=n;i++){
 cout<<arr[i]<<"\t";  }
}

void bubblesort(int *arr,int n)
{
 int i,temp,bound=n-1;
 int swapped=1;
 while(swapped>0)
 {
 swapped=0;
 for(i=0;i<=bound;i++){ display(arr,6);
 if(arr[i]>arr[i+1]){
  cout<<endl<<"Swaped arr["<<i<<"] with arr["<<i+1<<"]\n";
 temp=arr[i];
 arr[i]=arr[i+1];
 arr[i+1]=temp;
 swapped=i;          }}
 bound=swapped;
 }
}

void main()
{
int x[]={12,7,5,4,11,9,8};
clrscr();
bubblesort(x,6);
display(x,6);
getch();
}

Tuesday, December 2, 2014

Removing in Bineary Tree


Removing In Bineary Tree All 3 cases: 
1st case having no child (leaf node)
2nd case having one child (non leaf node)
3rd case having two childs :)
==========================================

#include<iostream.h>
#include<conio.h>
class treenode{
public:
int info;
treenode *left,*right;
treenode()
{ this->info=NULL;
  this->left=NULL;
  this->right=NULL;
}
treenode(int info)
{ this->info=info;
  this->left=NULL;
  this->right=NULL;
}
void setinfo(int info)
{ this->info=info; }
int getinfo()
{ return info; }
void setleft(treenode *left)
{  this->left=left; }
void setright(treenode *right)
{   this->right=right; }
treenode *getleft()
{ return left; }
treenode *getright()
{  return right; }

void insert(treenode *root,int info)
{
treenode *node=new treenode(info);
treenode *p,*q;
p=q=root;
while(info!=p->getinfo() && q!=NULL)
{
p=q;
if(info<p->getinfo())
{ q=p->getleft(); }
else
{  q=p->getright(); }
}
if(info==p->getinfo())
{ cout<<" \n Attempt to insert duplicate "<<info<<endl;
delete node;
}
else if(info<p->getinfo())
{ p->setleft(node); }
else
{p->setright(node); }
}

void preorder(treenode *root)
{
if(root!=NULL)
{ cout<<"\t"<<root->getinfo();
preorder(root->getleft());
preorder(root->getright());
}}
void postorder(treenode *root)
{
if(root!=NULL)
{
postorder(root->getleft());
postorder(root->getright());
cout<<"\t"<<root->getinfo();
}}
void inorder(treenode *root)
{
if(root!=NULL)
{
inorder(root->getleft());
cout<<"\t"<<root->getinfo();
inorder(root->getright());
}}

treenode *remove(treenode *tree,int info)
{
treenode *t;
int cmp=info-tree->getinfo();
if(cmp<0){
t=remove(tree->getleft(),info);
tree->setleft(t);
}
else if(cmp>0){
t=remove(tree->getright(),info);
tree->setright(t);
}
else if(tree->getleft()!=NULL && tree->getright()!=NULL)
{
treenode *minnode;
minnode=findmin(tree->getright());
tree->setinfo(minnode->getinfo());
t=remove(tree->getright(),minnode->getinfo());
tree->setright(t);
}
else
{ treenode *nodetodelete=tree;
  if(tree->getleft()==NULL)
  tree=tree->getright();
  else if(tree->getright()==NULL)
  tree=tree->getright();
  else{
  tree=NULL;
  delete nodetodelete;}
}
return tree;
}
treenode *findmin(treenode *tree)
{ if(tree==NULL)
 return NULL;
 if(tree->getleft()==NULL)
 return tree;
 return findmin(tree->getleft());
}

};
void main()
{
clrscr();
int x[]={14,15,4,8,7,3,5,2,1,9,6,-1};
treenode *root=new treenode();
root->setinfo(x[0]);
for(int i=1;x[i]>0;i++)
{ root->insert(root,x[i]);}
cout<<"\n\nDispaly ::Pre Order\n\n";
root->preorder(root);
cout<<"\n\n Display ::In Order\n\n";
root->inorder(root);
cout<<"\n\n Display ::Post Order\n\n";
root->postorder(root);
getch();
clrscr();
root->preorder(root);
cout<<"\n\n Removing leaf node     :: 1st case\n\n ";
root->remove(root,x[10]);
root->preorder(root);
cout<<"\n\n Removing Non leaf node :: 2nd case\n\n";
root->remove(root,x[6]);
root->preorder(root);
cout<<"\n\n Removing parent node [having two child] ::case 3\n\n";
root->remove(root,x[2]);
root->preorder(root);
getch();
}