MERGE SORT:

#include<iostream>

using namespace std;

void mergeSort(int,int);

void mergeTwoSortedArrays(int half1[],int size1,int half2[],int size2,int output[])

int i=0,j=0,k=0;

while(i<size1 && j<size2)

if(half1[i]<half2[j])

{ output[k]=half1[i];

i++;

k++; }

else

{ output[k]=half2[j];

j++;

k++; }

while(i<size1)

{ output[k]=half1[i];

k++;

i++; }

while(j<size2)

{ output[k]=half2[j];

k++; j++; } }

void mergeSort(int input[],int size)

int a;

if(size<=1)

return;

a=size/2;

int half1[1000],half2[1000],i=0,j=0;

for(;i<a;i++)

half1[i]=input[i];

int size1=i;

for(i=a;i<size;i++,j++)

half2[j]=input[i];

int size2=j;

mergeSort(half1,size1);

mergeSort(half2,size2);

mergeTwoSortedArrays(half1,size1,half2,size2,input);

int main()

int arr[1000],n;

cout<<"Enter n: ";

cin>>n;

for(int i=0;i<n;i++)

cin>>arr[i];
 mergeSort(arr,n);

for(int i=0;i<n;i++)

cout<<arr[i]<<" ";

return 0;

Output:

QUICK SORT:
#include<iostream>
using namespace std;

int partitionarray(int input[],int start,int ed)

int pivot=input[start];

int cnt=0;

for(int i=start+1;i<=ed;i++)

if(pivot>=input[i])

cnt++;

input[start]=input[cnt+start];

input[cnt+start]=pivot;

int j=ed;

int k;

for(int i=start;i<=start+cnt-1;i++)

if(input[i]>pivot)

int temp=input[i];

for(j;j>=cnt+start+1;j--)

if(input[j]<=pivot)

k=j;

input[i]=input[j];

input[j]=temp;

j=cnt;
 }

j=k-1;

return start+cnt;

void quicksort(int input[],int start,int ed)

if(start>=ed)

return;

int pivotindex=partitionarray(input,start,ed);

quicksort(input,start,pivotindex-1);

quicksort(input,pivotindex+1,ed);

int main()

int input[100],n;

cout<<"Enter n:";

cin>>n;

for(int i=0;i<n;i++)

cin>>input[i];

int start=0,ed=n-1;

quicksort(input,start,ed);
 cout<<endl<<"After Sorting: "<<endl;

for(int i=0;i<n;i++)

cout<<input[i]<<" ";

return 0;

Output:

PARENTHESIS BALANCING IN AN EXPRESSION:

#include<iostream>

#include<conio.h>

using namespace std;

char stk[100];

public:

int top;

stack()

top=-1;

void push(char x)

if(top>99)

cout <<"stack over flow";

return;

stk[++top]=x;

char pop()

if(top<0)

cout <<"stack under flow";

return '$';

return stk[top--];

void display()
 {

if(top<0)

cout <<" stack empty";

return;

for(int i=top;i>=0;i--)

cout <<stk[i] <<" ";

};

int ParanthesisCounter(stack *st);

int main()

int res;

stack st;

char ch;

cout<<"Enter Expression: ";

do{

cin.get(ch);

st.push(ch);

}while(ch!='\n');

res=ParanthesisCounter(&st);

if(res>0)

cout<<"Left Parenthesis is more";

else
 if(res==0)

cout<<"Parenthesis Balanced";

else

if(res<0)

cout<<"\nRight Parenthesis is more";

return 0;

int ParanthesisCounter(stack *st)

char ch;

int count=0;

while(st->top!=-1)

ch=st->pop();

if(ch=='(')

count++;

if(ch==')')

count--;

}
 return count;

Output:

INFIX TO POSTFIX CONVERSION:

#include<iostream>

#include<cstring>

#include<stack>

using namespace std;

int Precedence(char ch)

switch (ch)
 {

case '^': return 3;

case '/': return 2;

case '*': return 2;

case '+': return 1;

case '-': return 1;

default : return 0;

void infix2postfix(char infix[],char postfix[],int size)

stack<char> s;

int weight;

int i=0;

int k=0;

char ch;

/** iterate over the infix expression **/

while(i<size)

ch = infix[i];

if (ch == '(')

s.push(ch);

i++;

continue;
}

if (ch == ')')

while(!s.empty()&&s.top()!='(')

postfix[k++] = s.top();

s.pop();

if (!s.empty())

s.pop();

i++;

continue;

weight = Precedence(ch);

if (weight==0)

postfix[k++] = ch;

else /**Operator arrives :-| */

if (s.empty())

s.push(ch);

else

{
 while(!s.empty()&&s.top()!='('&&weight <=Precedence(s.top()))

postfix[k++] = s.top();

s.pop();

s.push(ch);

i++;

while(!s.empty())

postfix[k++]=s.top();

s.pop();

postfix[k]='\0';

int main()

char infix[] = "A*(B+C)/D";

int size = strlen(infix);

char postfix[size];

infix2postfix(infix,postfix,size);

cout<<"\nInfix Expression :: "<<infix;

cout<<"\nPostfix Expression :: "<<postfix;

cout<<endl;

return 0;
}

Output:

TOWER OF HANOI:

using namespace std;

#include<iostream>

#include<stdio.h>

void move(int num,char a,char b,char c)

if(num==1)

cout<<a<<"->"<<c<<"\n";

else

move(num-1,a,c,b);
 cout<<a<<"->"<<c<<"\n";

move(num-1,b,a,c);

int main()

int number;

char source='a',temp='b',destination='c';

cout<<"enter the number of disks: ";

cin>>number;

move(number,source,temp,destination);

return 0; }

Output:
CIRCULAR QUEUE USING ARRAYS:
#include<iostream>

#include<stdio.h>

#include<stdlib.h>

using namespace std;

#define maxqueue 10

int queue[maxqueue];

int front=-1;

int rear=-1;

int isempty()

if(front==-1)

return 1;

else

return 0;

}
int isfull()

if((front==0 && rear==maxqueue-1)||(front==rear+1))

return 1;

else

return 0;

void insert(int item)

if(isfull())

cout<<"QUEUE OVERFLOW";

return;

if(front==-1)

front=0;

if(rear==maxqueue-1)

rear=0;

else

rear=rear+1;

queue[rear]=item;

int del()

int item;

if(isempty())

cout<<"QUEUE UNDERFLOW";
 exit(1);

item=queue[front];

if(front==rear)

front=-1;

rear=-1;

else if(front==maxqueue-1)

front=0;

else

front=front+1;

return item;

void display()

int i;

if(isempty())

cout<<"queue is empty";

return;

cout<<"Queue elements: \n";

i=front;

if(front<=rear)

while(i<=rear)

cout<<queue[i++]<<" ";
 }

else

while(i<=maxqueue-1)

cout<<queue[i++]<<" ";

i=0;

while(i<=rear)

cout<<queue[i++]<<" ";

cout<<"\n";

int main()

int item;

cout<<"Enter the Element: ";

cin>>item;

insert(item);

cout<<"Enter the Element: ";

cin>>item;

insert(item);

cout<<"Enter the Element: ";

cin>>item;

insert(item);

cout<<"Enter the Element: ";

cin>>item;

insert(item);

display();

return 0;
}

Output:
SPARSE MATRIX USING TRANSPOSE:

#include<iostream>

using namespace std;

class Matrix

int A[10][10],B[10][3],C[10][3],row,col;

public:

void InputMatrix();

void DisplayMatrix();

void Matrix2Sparse();

void DisplaySparse(int X[][3]);

void DisplayS2M();

void Transpose();

void ftrans();

};

int main()

Matrix A;

A.InputMatrix();

A.DisplayMatrix(); /**Displaying the matrix*/

A.ftrans();

return 0;

void Matrix::InputMatrix()

cout<<"Enter the no of row and columns : "<<endl;

cin>>row>>col;

for(int i=0;i<row;i++) /** Assigning the value of matrix*/

for(int j=0;j<col;j++)

cout<<"A["<<i<<"]["<<j<<"]= ";

cin>>A[i][j];

cout<<endl;

void Matrix::DisplayMatrix()

cout<<"The matrix is :"<<endl<<endl;

for(int i=0;i<row;i++)

for(int j=0;j<col;j++)

cout<<A[i][j]<<" ";
 }

cout<<endl;

void Matrix::Matrix2Sparse()

int t=0; /**t Keeps track of no of non zero element*/

for(int i=0;i<row;i++)

for(int j=0;j<col;j++)

if(A[i][j]!=0) /** Accepting only non zero value(creating Sparse matrix)*/

t++;

B[t][0] = i+1;

B[t][1] = j+1;

B[t][2] = A[i][j];

B[0][0]=row;

B[0][1]=col;

B[0][2]=t;

cout<<"\nThe non zero value matrix are :"<<endl;

DisplaySparse(B);

}
void Matrix::DisplaySparse(int X[][3])

for(int i=0;i<=X[0][2];i++)

cout<<endl<<X[i][0]<<" "<<X[i][1]<<" "<<X[i][2];

cout<<endl<<endl;

void Matrix::DisplayS2M()

cout<<"Transposed matrix: "<<endl<<endl;

int k=1;

for(int i=1;i<=C[0][0];i++)

for(int j=1;j<=C[0][1];j++)

if(C[k][0]==i&&C[k][1]==j)

cout<<C[k][2]<<" ";

k++;

else

cout<<"0"<<" ";

}
 cout<<endl;

void Matrix::Transpose()

int NoOfColoumn = B[0][1];

int NoOfRow = B[0][0];

int NonZeroEle = B[0][2];

if(B[0][2]==0)

return;

int q=1;

for(int i=1;i<=NoOfColoumn;i++)

for(int j=1;j<=NonZeroEle;j++)

if(B[j][1]==i) /**Column index*/

C[q][0]=B[j][1]; /**Putting column index in row place*/

C[q][1]=B[j][0]; /**Putting row index in column place*/

C[q][2]=B[j][2]; /**Copying element value*/

q++;

C[0][0]=NoOfColoumn;
 C[0][1]=NoOfRow;

C[0][2]=NonZeroEle;

cout<<"Transposed sparse matrix"<<endl;

DisplaySparse(C);

DisplayS2M();

void Matrix::ftrans() /**Fast transpose*/

int S[B[0][1]],T[B[0][1]],j;

int m=B[0][0];

int n=B[0][1];

int t=B[0][2];

C[0][0]=n;

C[0][1]=m;

C[0][2]=t;

if(t==0) /**t*/

return;

for(int i=0;i<n;i++) /**n*/

S[i]=0;

for(int i=1;i<=t;i++) /**t*/

S[B[i][1]-1]++;

}
 T[0]=1;

for(int i=1;i<n;i++) /**n*/

T[i]=T[i-1]+S[i-1];

for(int i=1;i<=t;i++)

j=B[i][1];

C[T[j-1]][0]=B[i][1];

C[T[j-1]][1]=B[i][0];

C[T[j-1]][2]=B[i][2];

T[j-1]=T[j-1]+1;

cout<<"Fast Transposed sparse matrix"<<endl;

DisplaySparse(C);

DisplayS2M();

Output:
RADIX SORT:
#include<iostream>

using namespace std;

int largenum(int arr[], int n)

int max = arr[0];

for (int i = 1; i < n; i++)

if (arr[i] > max)

max = arr[i];

return max;

void countSort(int arr[], int n, int exp)

int output[n];

int i, count[10] = {0};

for (i = 0; i < n; i++)

count[ (arr[i]/exp)%10 ]++;

for (i = 1; i < 10; i++)

count[i] += count[i - 1];

for (i = n - 1; i >= 0; i--)

output[count[ (arr[i]/exp)%10 ] - 1] = arr[i];

count[ (arr[i]/exp)%10 ]--;

for (i = 0; i < n; i++)

arr[i] = output[i];

void radixsort(int arr[], int n)

int m = largenum(arr, n);

for (int exp = 1; m/exp > 0; exp *= 10)

countSort(arr, n, exp);

void display(int arr[], int n)

for (int i = 0; i < n; i++)

cout << arr[i] << " ";

int main()

int arr[50],n;

cout<<"Enter n: ";

cin>>n;

for(int i=0;i<n;i++)

cin>>arr[i];

cout<<endl<<"After sorting: ";

radixsort(arr, n);

display(arr, n);

return 0; }

Output:
POLYNOMIAL ADDITION:
#include<iostream>

using namespace std;

class Polynomial

int size;

public:

int *ptr;

Polynomial();

void Display();

Polynomial(int x);

void PolyAttach(int coef,int exp);

void PolyRemove(int coef,int exp);

Polynomial operator+(Polynomial &B);

};

int main()

cout<<"Enter Polynomial A"<<endl;

Polynomial A;

cout<<"\nEnter Polynomial B"<<endl;

Polynomial B;

cout<<"\nPolynomial A: ";

A.Display();

cout<<"\nPolynomial B: ";

B.Display();

Polynomial C(0);

C=A+B;

cout<<"\nAfter sum: ";

return 0;

Polynomial::Polynomial()

cout<<"Enter no of Terms: ";

cin>>size;

ptr = new int[2*size+1];

ptr[0]=size;

cout<<"INPUT FORMAT: coefficient exponent"<<endl;

int index=1;

for(int i=1;i<2*ptr[0];i+=2)

cout<<"Enter Term "<<index++<<": ";

cin>>ptr[i]>>ptr[i+1];

Polynomial::Polynomial(const int x=0)

ptr = new int[1];

ptr[0] = 0;

void Polynomial::Display()

for(int i=1;i<=2*ptr[0]-1;i=i+2)
 {

cout<<ptr[i]<<"x^"<<ptr[i+1]<<" + ";

cout<<endl;

void Polynomial::PolyAttach(int coef,int exp)

int *temp= new int [2*size+3];

temp[0]=ptr[0]+1;

for(int i=1;i<=2*size-1;i+=2)

temp[i]=ptr[i];

temp[i+1]=ptr[i+1];

temp[2*size+1]=coef;

temp[2*size+2]=exp;

size++;

delete [] ptr;

ptr=temp;

void Polynomial::PolyRemove(int coef,int exp)

int pos;

int *temp=new int [2*size-1];

temp[0]=ptr[0]-1;

for(int i=2;i<2*size;i+=2)

{
 if(ptr[i]==exp)

pos=i-1;

int j=1;

for(int i=1;i<=2*size-3;i+=2)

if(i!=pos)

temp[j++]=ptr[i];

temp[j++]=ptr[i+1];

else

continue;

size--;

delete [] ptr;

ptr=temp;

Polynomial Polynomial::operator+(Polynomial &B)

Polynomial C(0);

int p=1,q=1,r=1;

C.ptr = new int[2*(this->ptr[0]+B.ptr[0])+1];

if(this->ptr[p+1]==B.ptr[q+1])

C.ptr[r]=this->ptr[p]+B.ptr[q];

if(C.ptr[r]!=0)

C.ptr[r+1]=this->ptr[p+1];

p=p+2;

r=r+2;

q=q+2;

else if(this->ptr[p+1]<B.ptr[q+1])

C.ptr[r]=this->ptr[p];

C.ptr[r+1]=this->ptr[p+1];

p=p+2;

r=r+2;

else

C.ptr[r] = B.ptr[q];

C.ptr[r+1] = B.ptr[q+1];

q=q+2;

r=r+2;

}
 /**Copying remaining terms*/

while(p<=2*this->ptr[0]-1) /**Copying rest of this-> polynomial*/

C.ptr[r]=this->ptr[p];

C.ptr[r+1]=this->ptr[p+1];

r=r+2;

p=p+2;

while(q<=2*B.ptr[0]-1) /**Copying rest of B*/

C.ptr[r]=B.ptr[q];

C.ptr[r+1]=B.ptr[q+1];

r=r+2;

q=q+2;

r=r-2;

C.ptr[0]=(r+1)/2;

int *temp=new int[2*C.ptr[0]+1];

for(int i=0;i<2*C.ptr[0]+1;i++)

temp[i]=C.ptr[i];

delete []C.ptr;

C.ptr=temp;

return C;

Output:
INSERTION SORTING:
#include<iostream>

using namespace std;

void ins_sort(int a[],int n)

int value,pos;

for(int i=1;i<n;i++)

{
 value=a[i];

pos=i;

while(pos>0 && a[pos-1]>value)

a[pos]=a[pos-1];

pos=pos-1;

a[pos]=value;

int main()

int arr[50],n;

cout<<"Enter n: ";

cin>>n;

cout<<endl;

for(int i=0;i<n;i++)

cin>>arr[i];

ins_sort(arr,n);

cout<<endl<<"Sorted Array is: "<<endl;

for(int j=0;j<n;j++)

cout<<arr[j]<<" ";

}
 cout<<endl;

return 0;

Output:

BINARY SEARCH USING ARRAY:

using namespace std;

int BinarySearch(int arr[], int n, int val)

int mid,start=0,end;

end=n-1;

while(start<=end)

mid=(start+end)/2;
 if(val==arr[mid])

return mid;

else if(val>arr[mid])

start=mid+1;

else if(val<arr[mid])

end=mid-1;

} }

return -1;

int main()

int arr[50],n,val,ans;

cin>>n;

for(int i=0;i<n;i++)

cin>>arr[i];

cin>>val;

ans=BinarySearch(arr,n,val);

cout<<ans;

return 0;

Output:
BINARY SEARCH TREE ->Insertion,Deletion,Inorder
Traversal :
#include<iostream>

#include<stdio.h>

using namespace std;

struct node

struct node *lchild;

int info;

struct node *rchild;

};

void inorder(struct node *ptr)

{
 if(ptr==NULL)

return;

inorder(ptr->lchild);

cout<<ptr->info<<"\t";

inorder(ptr->rchild);

struct node *insert_rec(struct node *ptr,int ikey)

if(ptr==NULL)

ptr=new node;

ptr->info=ikey;

ptr->lchild=NULL;

ptr->rchild=NULL;

return ptr;

else if(ptr->info > ikey)

ptr->lchild=insert_rec(ptr->lchild,ikey);

else if(ptr->info < ikey)

ptr->rchild=insert_rec(ptr->rchild,ikey);

else

cout<<"duplicate key";

return ptr;

};

struct node *del(struct node *root,int dkey)

struct node *parent,*ptr,*child,*succ,*parsucc;

ptr=root;
parent=NULL;

while(ptr!=NULL)

if(dkey==ptr->info)

break;

parent=ptr;

if(dkey < ptr->info)

ptr=ptr->lchild;

else

ptr=ptr->rchild;

if(ptr==NULL)

cout<<"dkey is not present";

return root;

if(ptr->lchild!=NULL && ptr->rchild!=NULL)

parsucc=ptr;

succ=ptr->rchild;

while(succ->lchild!=NULL)

parsucc=succ;

succ=succ->lchild;

ptr->info=succ->info;

ptr=succ;

parent=parsucc;

if(ptr->lchild!=NULL)
 child=ptr->lchild;

else

child=ptr->rchild;

if(parent==NULL)

root=child;

else if(ptr==parent->lchild)

parent->lchild=child;

else

parent->rchild=child;

delete ptr;

return root; } } }

int main()

struct node *root=NULL;

root=insert_rec(root,50);

root=insert_rec(root,30);

root=insert_rec(root,60);

root=insert_rec(root,38);

root=insert_rec(root,35);

root=insert_rec(root,55);

root=insert_rec(root,22);

root=insert_rec(root,59);

inorder(root);

return 0;

Output:
LEVEL ORDER TRAVERSAL:
#include <stdio.h>

#include <stdlib.h>

struct node

int data;

struct node* left, *right;

};

void printGivenLevel(struct node* root, int level);

int height(struct node* node);

struct node* newNode(int data);

void printLevelOrder(struct node* root)

int h = height(root);

int i;

for (i=1; i<=h; i++)

void printGivenLevel(struct node* root, int level)

if (root == NULL)

return;

if (level == 1)

printf("%d ", root->data);

else if (level > 1)

printGivenLevel(root->left, level-1);

printGivenLevel(root->right, level-1);

int height(struct node* node)

if (node==NULL)

return 0;

else

int lheight = height(node->left);

int rheight = height(node->right);

if (lheight > rheight)

return(lheight+1);

else return(rheight+1);

struct node* newNode(int data)

struct node* node = (struct node*)

malloc(sizeof(struct node));

node->data = data;

node->left = NULL;

node->right = NULL;

return(node);

int main()

struct node *root = newNode(1);

root->left = newNode(2);

root->right = newNode(3);

root->left->left = newNode(4);

root->left->right = newNode(5);

printf("Level Order traversal of binary tree is \n");

printLevelOrder(root);

return 0;

Output:
NUMBER OF LEAF NODES:
#include <stdio.h>

#include <stdlib.h>

struct node

int data;

struct node* left;

struct node* right;

};

unsigned int getLeafCount(struct node* node)

if(node == NULL)
 return 0;

if(node->left == NULL && node->right==NULL)

return 1;

else

return getLeafCount(node->left)+getLeafCount(node->right);

struct node* newNode(int data)

struct node* node = (struct node*)malloc(sizeof(struct node));

node->data = data;

node->left = NULL;

node->right = NULL;

return(node);

int main()

struct node *root = newNode(1);

root->left = newNode(2);

root->right = newNode(3);

root->left->left = newNode(4);

root->left->right = newNode(5);

printf("Leaf count of the tree is %d", getLeafCount(root));

getchar();

return 0;

Output:
ZIG ZAG TRAVERSAL:
#include<iostream>

#include<stdio.h>

#include<stack>

using namespace std;

struct node

struct node *lchild;

int info;

struct node *rchild;

};

struct node *insert(int data)

struct node *temp;

temp=new node;

temp->info=data;

temp->lchild=NULL;

temp->rchild=NULL;

return temp;

void zigzag(struct node *root)

if(root==NULL)

{ return; }

stack<struct node *>stack1;

stack<struct node *>stack2;

stack1.push(root);

while(!stack1.empty() || !stack2.empty())

while(!stack1.empty())

struct node *temp;

temp=stack1.top();

stack1.pop();

cout<<temp->info<<"\t";

if(temp->lchild!=NULL)

stack2.push(temp->lchild);

if(temp->rchild!=NULL)

stack2.push(temp->rchild);

}
 while(!stack2.empty())

struct node *temp;

temp=stack2.top();

stack2.pop();

cout<<temp->info<<"\t";

if(temp->rchild!=NULL)

stack1.push(temp->rchild);

if(temp->lchild!=NULL)

stack1.push(temp->lchild);

} } }

int main()

struct node *root=NULL;

struct node *ptr,*q;

root=insert(1);

root->lchild=ptr=insert(2);

root->rchild=q=insert(3);

ptr->lchild=insert(4);

ptr->rchild=insert(5);

q->lchild=insert(6);

ptr->lchild->lchild=insert(7);

ptr->lchild->rchild=insert(8);

q->lchild->lchild=insert(9);

q->lchild->rchild=insert(10);

zigzag(root);

return 0;

}
Output: