Program 8) Design, Develop and Implement a Program in CPP for sorting an

element From data given by the user, using

A. Bubble Sort
#include<iostream>
using namespace std;
class Bsort
{
int a[10],N;
public:
void Get();
void sort();
void put();
};
void Bsort::Get()
{
cout<<"\nenter the how many elements in array";
cin>>N;
cout<<"\nenter the elements";
for(int i=0;i<N;i++)
{
cin>>a[i];
}
}
void Bsort::sort()
{
int temp;
for(int i=0;i<N;i++)
{
for(int j=0;j<N-i-1;j++)
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
}
void Bsort::put()
{
cout<<"\n elements after sorting are:\n";
for(int i=0;i<N;i++)
{
cout<<a[i]<<"\n";
}
}
int main()
{
Bsort b;
b.Get();
b.sort();
b.put();
}
Output :
enter the how many elements in array5

enter the elements2 5 6 8 3

elements after sorting are:

B. Insertion sort
#include<iostream>
using namespace std;
class insertion
{
int i,j,n,temp,a[30];
public:
void get();
void sort();
void put();
};
void insertion::get()
{
cout<<"\n enter the number of elements:";
cin>>n;
cout<<"\n enter the elements\n";
for(i=0;i<n;i++)
{
cin>>a[i];
}
}
void insertion:: sort()
{
for(i=1;i<=n-1;i++)
{
temp=a[i];
j=i-1;
while((temp<a[j])&&(j>=0))
{
a[j+1]=a[j];
j=j-1;
}
a[j+1]=temp;
}
}
void insertion ::put()
{
cout<<"\n sorted list is as follows \n";
for(i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
}
int main()
{
insertion i;
i.get();
i.sort();
i.put();
}
Output :
enter the number of elements:4

enter the elements

sorted list is as follows

C. Selection Sort
#include<iostream>
using namespace std;
class selection
{
int i,j,n,loc,temp,min,a[30];
public:
void get();
void sort();
void put();
};
void selection :: get()
{
cout<<"Enter the number of elements:";
cin>>n;
cout<<"\nEnter the elements\n";
for(i=0;i<n;i++)
{
cin>>a[i];
}
}
void selection :: sort()
{
for(i=0;i<n-1;i++)
{
min=a[i];
loc=i;
for(j=i+1;j<n;j++)
{
if(min>a[j])
{
min=a[j];
loc=j;
}
}
temp=a[i];
a[i]=a[loc];
a[loc]=temp;
}
}
void selection :: put()
{
cout<<"\nSorted list is as follows\n";
for(i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
}
int main()
{
selection s;
s.get();
s.sort();
s.put();
}

Output :
Enter the number of elements:5

Enter the elements

Sorted list is as follows

D. Merge Sort
#include<iostream>
using namespace std;
class number
{
int a[50],n;
public:
void get();
void mergesort(int low,int high);
void merge(int low,int mid,int high);
};
void number::get()
{
int i;
cout<<"\n enter the number of elements :";
cin>>n;
cout<<"\n enter your elements:\n";
for(i=1;i<=n;i++)
cin>>a[i];
cout<<"\n your array is:\n";
for(i=1;i<=n;i++)
cout<<a[i]<<"\t";
mergesort(1,n);
cout<<"\n array after sorting :\n";
for(i=1;i<=n;i++)
cout<<a[i]<<"\t";
}
void number::mergesort(int low,int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
mergesort(low,mid);
mergesort(mid+1,high);
merge(low,mid,high);
}
}
void number::merge(int low,int mid,int high)
{
int h,i,j,k,b[5000];
h=low;
i=low;
j=mid+1;
while((h<=mid)&&(j<=high))
{
if(a[h]<=a[j])
{
b[i]=a[h];
h=h+1;
}
else
{
b[i]=a[j];
j=j+1;
}
i=i+1;
}
if(h>mid)
{
for(k=j;k<=high;k++)
{
b[i]=a[k];
i=i+1;
}
}
else
{
for(k=h;k<=mid;k++)
{
b[i]=a[k];
i=i+1;
}
}
for(k=low;k<=high;k++)
a[k]=b[k];
}
int main()
{
number a;
a.get();
return(0);
}

Output :
enter the number of elements :5
enter your elements:
56742
your array is:
56742
array after sorting :
24567

E. Quick Sort
#include<iostream>
using namespace std;
class quick
{
public:
int a[50],n;
void getdata();
void quicksort(int,int);
int partition(int,int);
void swap(int &a,int&b);
void putdata();
};
void quick::getdata()
{
cout<<"\n enter the limit of the array:";
cin>>n;
cout<<"\n enter the elements of the array:";
for(int k=1;k<=n;k++)
{
cin>>a[k];
}
quicksort(1,n);
}
void quick::quicksort(int p,int q)
{
if(p<q)
{
int j=q+1;
j=partition(p,j);
quicksort(p,j-1);
quicksort(j+1,q);
}
}
int quick::partition(int m,int r)
{
int i;
int v=a[m];
i=m;
do
{
do
{
i++;
}
while(a[i]<=v);
do
{
r--;
}
while(a[r]>v);
if(i<r)
{
swap(a[i],a[r]);
}
else
break;
}
while(1);
a[m]=a[r];
a[r]=v;
return(r);
}
void quick::swap(int &a,int&b)
{
int temp=a;
a=b;
b=temp;
}
void quick::putdata()
{
cout<<"after sorting";
for(int k=1;k<=n;k++)
{
cout<<"\t"<<a[k];
}
}
int main()
{
quick q;
q.getdata();
q.putdata();
}
Output :
enter the limit of the array:5
enter the elements of the array:
1
2
8
3
6
after sorting 1 2 3 6 8

Program 9) Design, Develop and Implement a Program in CPP for Searching

A. Linear Search
#include<iostream>
using namespace std;
class linear
{
int a[20],i,x,n;
public:
void get();
void search();
};
void linear :: get()
{
cout<<"How many elements?";
cin>>n;
cout<<"Enter array elements:\n";
for(i=0;i<n;++i)
cin>>a[i];
}
void linear :: search()
{
cout<<"\nEnter element to search:\n";
cin>>x;
for(i=0;i<n;++i)
if(a[i]==x)
break;
if(i<n)
cout<<"Element found at index : " <<i+1;
else
cout<<"Element not found";
}
int main()
{
linear l;
l.get();
l.search();
return 0;
}

Output :
How many elements?6
Enter array elements:
4
1
8
3
5
7
Enter element to search:
8
Element found at index :
3
Process finished

B. Binary Search
#include<iostream>
Using namespace std;
Class binary
{
Int I, low, high, mid, n, key, array[100];
Public:
Void get();
Void search();
};
Void binary :: get()
{
Cout<<”Enter number of elements :”;
Cin>>n;
Cout<<”Enter your elements :\n”;
For(I = 0; I < n; i++)
{
Cin>>array[i];
}
}
Void binary :: search()
{
Cout<<”Enter value to find n”;
Cin>>key;
Low = 0;
High = n – 1;
Mid = (low+high)/2;
While (low <= high)
{
If(array[mid] < key)
Low = mid + 1;
Else if (array[mid] == key)
{
Cout<<”Element found at location :”<<mid+1;
Break;
}
Else
High = mid – 1;
Mid = (low + high)/2;
}
If(low > high)
Cout<<”Not found!”;
}
Int main()
{
Binary b;
b.get();
b.search();
}

Output :
Enter number of elements :4
Enter your elements :
6
4
2
8
Enter value to find n8
Element found at location :4

Program 10) Design, Develop and Implement a Program in CPP for the
following Operations on Graph(G) of Cities
a) Create a Graph of N cities using Adjacency Matrix.
b) Print all the nodes reachable from a given starting node in a digraph using
DFS method
c) Print all the nodes reachable from a given starting node in a digraph using
BFS method

A.DFS
#include<iostream>
Using namespace std;
Int n,a[10][10],visited[10]={0};
Char node[10],start;
Void dfs(char v);
Int main()
{
Int I,j;
Cout<<”Enter no of nodes \n”;
Cin>>n;
Cout<<”Enter name of nodes \n”;
For(i=0;i<n;i++)
{
Cin>>node[i];
}
Cout<<”Enter adjacency matrix \n”;
For(i=0;i<n;i++)
{
For(j=0;j<n;j++)
{
Cin>>a[i][j];
}
}
Cout<<”Enter starting node\n”;
Cin>>start;
Dfs(start);
}
Void dfs(char v)
{
Int I,j;
For(i=0;i<n;i++)
{
If(v == node[i])
Break;
}
Visited[i]=1;
Cout<<node[i];
For(j=0;j<n;j++)
{
If(visited[j]==0&&a[i][j]!=0)
Dfs(node[j]);
}
}

Output :
Enter no of nodes 9
Enter name of nodes
ABCDEFGJK
Enter adjacency matrix
011001000
000000100
010001000
001000000
001100000
000100000
001100001
000100001
000010000
Enter starting node
B
BGCFDKE
Process finished.

B.BFS
#include<iostream>
Using namespace std;
Int main(){
Int a[10][10],visited[10]={0},n,f=0,r=0,I,j;
Char ch,q[50],node[10],start;
Cout << “\n\t Enter the number of nodes \n “;
Cin >> n;
Cout << “\n\t Enter the name of node \n “;
For(i=0;i<n;i++)
{
Cin >> node[i];
}
Cout << “\n\t Enter the adjacency matrix \n “;
For(i=0;i<n;i++)
{
For(j=0;j<n;j++)
{
Cin >> a[i][j];
}
}
Cout << “\n\t Enter the starting node \n “;
Cin >> start;
For(i=0;i<n;i++)
{
If(node[i]==start)
Break;
}
Q[0]=node[i];
R++;
Cout<<q[0];
Visited[i]=1;
F++;
Do
{
For(j=0;j<n;j++)
{
If(visited[j]== 0 && a[i][j]!=0)
{
Q[r]= node[j];
Visited[j]=1;
R++;
}
}
Ch = q[f];
Cout<<ch;
F++;
For(i=0;i<n;i++)
{
If(node[i]==ch)
Break;
}
}
While(f!=r);
}

Output :
Enter the number of nodes
9
Enter the name of node
ABCDEFGJK
Enter the adjacency matrix
011001000
000000100
010001000
001000000
001100000
000100000
001100001
000100001
000010000
Enter the starting node
A
ABCFGDK
Process finished.

Program 11) Design, Develop and Implement a menu driven Program in CPP
for the following operations on Binary Search Tree (BST) of Integers.
a) Create a BST of N Integers: 6, 9, 5, 2, 8, 15, 24, 14, 7, 8, 5, 2
b) Traverse the BST in Inorder, Preorder and Post Order
c) Search the BST for a given element (KEY) and report the appropriate
message
d) Exit
#include<iostream>
using namespace std;
class tree
{
int info;
tree *left,*right;
public:
void insert();
void preorder(tree*);
void inorder(tree*);
void postorder(tree*);
void search();
};
tree *root=NULL,*move,*back,*temp;
int item,top;
void tree :: insert()
{
temp=new tree;
cout<<"\nEnter the item : ";
cin>>item;
temp->info=item;
temp->left=NULL;
temp->right=NULL;

if(root==NULL)
{
root=temp;
}
else
{
move=root;
while(move!=NULL)
{
back=move;
if(temp->info<=move->info)
{
move=move->left;
}
else
{
move=move->right;
}
}
if(temp->info<=back->info)
{
back->left=temp;
}
else
{
back->right=temp;
}
}
}
void tree :: preorder(tree *root)
{
if(root!=NULL)
{
cout<<" "<<root->info;
preorder(root->left);
preorder(root->right);
}
}
void tree :: inorder(tree *root)
{
if(root!=NULL)
{
inorder(root->left);
cout<<" "<<root->info;
inorder(root->right);
}
}
void tree :: postorder(tree *root)
{
if(root!=NULL)
{
postorder(root->left);
postorder(root->right);
cout<<" "<<root->info;
}
}
void tree :: search()
{
if(root==NULL)
{
cout<<"\nEmpty Tree";
}
else
{
cout<<"\nEnter the element need to be searched : ";
cin>>item;
move=root;

while(move!=NULL)
{
if(item==move->info)
{
cout<<"\nElement Present";
break;
}
if(item<move->info)
{
move=move->left;
}
else
{
move=move->right;
}
}
if(move==NULL)
{
cout<<"\nItem is not present";
}
}
}
int main()
{
int ch;
tree t1;
do
{
cout<<"\n-----MENU-----";
cout<<"\n1.for Insert";
cout<<"\n2.for Preorder";
cout<<"\n3.for Inorder";
cout<<"\n4.for Postorder";
cout<<"\n5.for Search";
cout<<"\n6.for Exit";
cout<<"\nEnter your choice : ";
cin>>ch;

switch(ch)
{
case 1:
t1.insert();
break;
case 2:
t1.preorder(root);
break;
case 3:
t1.inorder(root);
break;
case 4:
t1.postorder(root);
break;
case 5:
t1.search();
break;
case 6:
exit(0);
default:
cout<<"\nInvalid Choice";
}
}
while(1);
return(0);
}

Output :
}*---Menu---*
1 for Insert
2 for Preorder
3 for Inorder
4 for Postorder
5 for Search
6 for Exit
Enter your choice1
Enter the item 34
*---Menu---*
1 for Insert
2 for Preorder
3 for Inorder
4 for Postorder
5 for Search
6 for Exit
Enter your choice1
Enter the item 11
*---Menu---*
1 for Insert
2 for Preorder
3 for Inorder
4 for Postorder
5 for Search
6 for Exit
Enter your choice1
Enter the item 38
*---Menu---*
1 for Insert
2 for Preorder
3 for Inorder
4 for Postorder
5 for Search
6 for Exit
Enter your choice1
Enter the item 90
*---Menu---*
1 for Insert
2 for Preorder
3 for Inorder
4 for Postorder
5 for Search
6 for Exit
Enter your choice1
Enter the item 22
*---Menu---*
1 for Insert
2 for Preorder
3 for Inorder
4 for Postorder
5 for Search
6 for Exit
Enter your choice2
34 11 22 38 90
*---Menu---*
1 for Insert
2 for Preorder
3 for Inorder
4 for Postorder
5 for Search
6 for Exit
Enter your choice3
11 22 34 38 90
*---Menu---*
1 for Insert
2 for Preorder
3 for Inorder
4 for Postorder
5 for Search
6 for Exit
Enter your choice4
22 11 90 38 34
*---Menu---*
1 for Insert
2 for Preorder
3for Inorder
4 for Postorder
5 for Search
6 for Exit
Enter your choice