ADVANCED ALGORITHM LAB. PROGRAMS


// Program for Bubble, Insertion and Selection Sort

#include<iostream.h>
#include<conio.h>
class Sorting{
public:
void Bubble(int a[],int);
void Insertion(int a[],int);
void Selection(int a[],int);
void Print(int a[],int);
};
//////////////////////BUBBLE SORT//////////////
void Sorting::Bubble(int a[],int n){
int swap=0;
for(int i=0;i<n;i++){
for(int j=n;j>i;j--){
if(a[j]<a[j-1]){
swap=1;
int t;
t=a[j];
a[j]=a[j-1];
a[j-1]=t;
}
}
if(swap==0)
break;
}
}
///////////////////INSERTION SORT//////////////
void Sorting::Insertion(int a[],int n){
for (int i=0;i<n;i++){
int j=i;
while((j>0) && (a[j]<a[j-1])){
int t;
t=a[j];
a[j]=a[j-1];
a[j-1]=t;
j--;
}
}
}
/////////////////////SELECTION SORT//////////////
void Sorting::Selection(int a[],int n){
int min,temp;
for(int i=0;i<n-1;i++){
min = i;
for(int j=i+1;j<n;j++)
if(a[j]<a[min])
min=j;
temp=a[i];
a[i]=a[min];
a[min]=temp;
}
}
////////////////PRINT ARRAY//////////////
void Sorting::Print(int a[],int n){
cout<<"\nSorted Array: ";
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
cout<<endl;
}
void main(){
int a[7],ch;
clrscr();
Sorting s;
for(int i=0;i<7;i++){
cout<<"Enter Values: ";
cin>>a[i];
}
cout<<"\n1-Bubble Sort";
cout<<"\n2-Insertion Sort";
cout<<"\n3-Selection Sort";
cout<<"\n\nEnter ur choice: ";
cin>>ch;
if(ch==1){
s.Bubble(a,i);
s.Print(a,i);
}
else if(ch==2){
s.Insertion(a,i);
s.Print(a,i);
}
else if(ch==3){
s.Selection(a,i);
s.Print(a,i);
}
getch();
}

OUTPUT

Enter Values: 21
Enter Values: 0                                                                 
Enter Values: 45                                                               
Enter Values: 61                                                               
Enter Values: 25                                                                
Enter Values: 7                                                                
Enter Values: 6                                                                
                                                                               
1-Bubble Sort                                                                  
2-Insertion Sort                                                               
3-Selection Sort                                                               
                                                                                
Enter ur choice: 2                                                             
                                                                               
Sorted Array: 0 6 7 21 25 45 61   


_____________________http://sundcs.blogspot.com/_________________



// Program for Quick, Mearge and Heap Sort

#include<iostream.h>
#include<conio.h>
class Sorting{
public:
void mergeSort(int,int);
int QSort(int a[],int,int);
void Print(int a[],int);
void restoreHup(int*,int);
void restoreHdown(int*,int,int);
};

//////////////////////MERGE SORT//////////////
int a[50];
void merge(int,int,int);
void Sorting::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 merge(int low,int mid,int high){
int h,i,j,b[50],k;
h=low;
i=low;
j=mid+1;
while((h<=mid)&&(j<=high)){
if(a[h]<=a[j]){
b[i]=a[h];
h++;
}
else{
b[i]=a[j];
j++;
}
i++;
}
if(h>mid){
for(k=j;k<=high;k++){
b[i]=a[k];
i++;
}
}
else{
for(k=h;k<=mid;k++){
b[i]=a[k];
i++;
}
}
for(k=low;k<=high;k++)
a[k]=b[k];
}

//////////////////////QUICK SORT//////////////
int Sorting::QSort(int a[],int start,int end){
int i=start;
int j=end;
int pivot=i;
if(start>=end)
return 0;
do{
while(i<j&&a[j]>a[pivot])
j--;
while(i<j&&a[i]<=a[pivot])
i++;
int t;
t=a[i];
a[i]=a[pivot];
a[pivot]=t;
if(a[i]<a[pivot]){
int temp;
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}while(i!=j);
QSort(a,start,i-1);
QSort(a,i+1,end);
}

////////////////HEAP SORT////////////////
int aa[20],nn,ii,jj,kk;
cout<<" Enter the number of elements to sort : ";
cin>>nn;
cout<<"Enter the elements :";
for(ii=1;ii<=nn;ii++){
cin>>aa[ii];
restoreHup(aa,ii);
}
jj=nn;
for(ii=1;ii<=jj;ii++)
{
int temp1;
temp1=aa[1];
aa[1]=aa[nn];
aa[nn]=temp1;
nn--;
restoreHdown(aa,1,nn);
}
nn=jj;
cout<<"Here is it... ";
for(ii=1;ii<=nn;ii++)
cout<<aa[ii];
}
void restoreHup(int *aa,int ii)
{int v=aa[ii];
while((ii>1)&&(aa[ii/2]<v))
{
aa[ii]=aa[ii/2];
ii=ii/2;
}
aa[ii]=v;
}
void restoreHdown(int *aa,int ii,int nn)
{
int v=aa[ii];
int jj=ii*2;
while(jj<=nn)
{
if((jj<nn)&&(aa[jj]<aa[jj+1]))
jj++;
if(aa[jj]<aa[jj/2]) break;
aa[jj/2]=aa[jj];
jj=jj*2;
}
aa[jj/2]=v;
}

////////////////PRINT ARRAY//////////////
void Sorting::Print(int a[],int n){
cout<<"\nSorted Array: ";
for(int i=1;i<=n;i++)
cout<<a[i]<<" ";
cout<<endl;
}
void main(){
int a[7],ch;
clrscr();
Sorting s;
for(int i=0;i<7;i++){
cout<<"Enter Values: ";
cin>>a[i];
}
cout<<"\n1-Merge Sort";
cout<<"\n2-Quick Sort";
cout<<"\n3-Heap Sort";
cout<<"\n\nEnter ur choice: ";
cin>>ch;
if(ch==1){
s.mergeSort(0,7);
s.Print(a,i);
}
else if(ch==2){
s.QSort(a,0,7);
s.Print(a,i);
}
else if(ch==3){
s.restoreHup(aa,ii);
//s.Print(a,i);
}
getch();
}


OUTPUT

Enter Values: 9
Enter Values: 8                                                                 
Enter Values: 7                                                                
Enter Values: 6                                                                
Enter Values: 5                                                                 
Enter Values: 4                                                                
Enter Values: 3                                                                
1-Merge Sort                                                                   
2-Quick Sort                                                                   
Enter ur choice: 2                                                             
Sorted Array: 3 4 5 6 7 8 9                                             



_____________________http://sundcs.blogspot.com/_________________


// Implementation of Counting Sort and Radix Sort

#include <iostream>
#include<stdlib.h>
#include<conio.h>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
#include <cstdlib>
#include <ctime>
#include "queue.h"
#define MAX 11
using namespace std;
class CountRadix
{  public:
void CountingSort(vector<int>& Array);
int RadixSort();
void CopyToLast(Queue<int> g[]);
};
void CountRadix::CountingSort(vector<int>& Array)
{  int Min, Max;
Min = Max  = Array[0];
for(int i = 1; i < Array.size(); i ++)//detrmin the max and min in the array
{
if(Array[i] < Min)
Min = Array[i];
if(Array[i] > Max)
Max = Array[i];
}
int Range = Max - Min + 1;
vector<int> Count; //Count Array Hold The Number Of Each Number
Count.resize(Range);
for(int i = 0; i < Range; i ++)
Count[i] = 0;
for(int i = 0; i < Array.size(); i ++)
Count[Array[i] - Min] ++;
int Index = 0;
for(int i = Min; i <= Max; i ++)//Fill Array in sorted Order
for(int j = 0; j < Count[i - Min]; j ++)
Array[Index ++] = i;
}
int CountRadix::RadixSort()
{
Queue<int> q[MAX];
srand(time(0));
int res,i,j,digit = 4,passHelper=10,temp,pos;
cout << "Before Sorting : \n";
for(i=0;i<100;i++) {
res = rand() % 10000;
cout << res << "|";
q[MAX-1].append(res);
}
for(i=0;i<digit;i++) {
while(!q[MAX-1].empty()) {
q[MAX-1].retrieve(temp);
q[MAX-1].serve();
pos=temp;
for(j=0;j<i;j++)
pos/=10;
pos %= 10;
q[pos].append(temp);
}
passHelper *= 10;
CopyToLast(q);
}
cout << "\nAfter sorting :\n";
while(!q[MAX-1].empty()) {
q[MAX-1].retrieve(temp);
cout << temp << "|";
q[MAX-1].serve();
}
return 0;
}
void CountRadix::CopyToLast(Queue<int> g[])
{
int i,temp;
for(i=0;i<MAX-1;i++)
{
while(!g[i].empty())
{
g[i].retrieve(temp);
g[MAX-1].append(temp);
g[i].serve(); }
}
}  int main()
{
CountRadix CR;
int chk;
clrscr();
cout<<"Check for sorting enter \n Counting Sort for 1\n Radix Sort for 2";
switch(chk)
{
case 1:
          CR.CountingSort();
          break;
case 2:
          CR.RadixSort();
          break;
case 3:
          exit(0);
          break;
default:
          cout<<"invalid entry";
          break;
}



_____________________http://sundcs.blogspot.com/_________________


// Implementation of Linear and Binary search

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

class SeqBin
{
public:
int arr[5],a,i;
SeqBin()
{
cout<<"Enter values of array : \n";
for(i=0;i<5;i++)
cin>>arr[i];
}
void seq(int x);
void bin(int x);
};
//      Linear Search
void SeqBin::seq(int x)
{
int i,loc=-1;
for(i=0;i<5;i++)
{
if(x==arr[i])
loc=i;
}
if(loc==-1)
cout<<"number not found"<<endl;
else
cout<<"number"<<x<<"is found at location: "<<loc+1;
}

// Binary Serach
void SeqBin::bin(int x)
{
int e, mid,start=0,end=9,loc=-1;
for(int i=0;i<5;i++)
{
for(int j=i+1;j<5;j++)
{
if(arr[i]>arr[j])
{
e=arr[i];
arr[i]=arr[j];
arr[j]=e;
}
}
}
for(i=0;i<5;i++)
cout<<arr[i]<<"\t";
while(start<=end)
{
mid=(start+end)/2;
if(arr[mid]==x)
{
loc=mid;
break;
}
else
if(x<arr[mid])
end=mid-1;
else
if(x>arr[mid])
start=mid+1;
}
if(loc==-1)
cout<<"number not found";
else
cout<<"number found at loc: "<<loc+1;
}
void main()
{
SeqBin SB;
int a,c,i;
char q;
clrscr();
cout<<"Enter value to find :";
cin>>c;
cout<<"Which type of search u want? "<<endl;
cout<<"Press L for Linear search and B for binary search"<<endl;
cin>>q;
if (q=='l')
SB.seq(c);
if (q=='b')
SB.bin(c);
getch();
}




OUTPUT

Enter values of array :
3
5
6
7
9
      
Enter value to find: 7 
                                                                            
Which type of search u want?                                                   
Press L for Linear search and B for binary search                              
b                                                                              
3       5       6       7       9       number found at loc: 4                 



_____________________http://sundcs.blogspot.com/_________________


// Binary Search Tree with Insertion, Deletion, Searching and Display methods

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
typedef struct bst
{
int data;
struct bst *left, *right;
}node;
void insert(node *,node*);
void inorder(node*);
node *search(node *,int,node **);
void del(node *,int);
void main()
{
int ch;
char ans='N';
int key;
node *New,*root,*tmp,*parent;
node *get_node();
root=NULL;
clrscr();
printf("\n \t Program for Binary Search Tree");
do
{
printf("\n 1.Create \n 2. Search \n 3. Delete \n 4.Display");
printf("\n\n Enter your choice");
scanf("%d",&ch);
switch(ch)
{
case 1 : do
{
New=get_node();
printf("\n Enter the Element");
scanf("%d",&New->data);
if(root==NULL)
root=New;
else
insert(root,New);
printf("\n Do u want to continue enter more elements(y/n)");
ans=getch();
}while(ans=='N');
break;
case 2: printf("/n Enter the element which u want to search");
scanf("%d",&key);
tmp=search(root,key,&parent);
printf("\n Parent of node %d is %d",tmp->data,parent->data);
break;
case 3: printf("\n Enter the Element u wish to delete");
scanf("%d",&key);
del(root,key);
break;
case 4: if(root==NULL)
printf("Tree is not created");
else
{
printf("\n The tree is:");
inorder(root);
}
break;
}
} while(ch!=5);
}
node *get_node()
{
node *temp;
temp=(node*)malloc(sizeof(node));
temp->left=NULL;
temp->right=NULL;
return temp;
}
void insert(node *root,node *New)
{
if(New->data<root->data)
{
if(root->left==NULL)
root->left=New;
else
insert(root->left,New);
}
if(New->data>root->data)
{
if(root->right==NULL)
root->right=New;
else
insert(root->right,New);
}
}
node *search(node *root,int key,node **parent)
{
node *temp;
temp=root;
while(temp!=NULL)
{
if(temp->data==key)
{
printf("\n The %d Element is present",temp->data);
return temp;
}
*parent=temp;
if(temp->data>key)
temp=temp->left;
else
temp=temp->right;
}
return NULL;
}
void del(node *root,int key)
{
node *temp,*parent,*temp_succ;
temp=search(root,key,&parent);
if(temp->left!=NULL && temp->right!=NULL)
{
parent=temp;
temp_succ=temp->right;
while(temp_succ->left!=NULL)
{
parent = temp_succ;
temp_succ=temp_succ->left;
}
temp->data=temp_succ->data;
parent->right=NULL;
printf("\n Now deleted it!");
return;
}
if(temp->left!=NULL && temp->right==NULL)
{
if(parent->left==temp)
parent->left=temp->left;
else
parent->right=temp->left;
temp=NULL;
free(temp);
printf("\n Now deleted if!");
return;
}
if(temp->left==NULL && temp->right!=NULL)
{
if(parent->left==temp)
parent->left=temp->right;
else
parent->right=temp->right;
temp=NULL;
free(temp);
printf("\n Now Deleted it!");
return;
}
if(temp->left==NULL &&temp->right==NULL)
{
if(parent->left==temp)
parent->left=NULL;
else
parent->right=NULL;
printf("\n Now Deleted it!");
return;
}
}
void inorder(node *temp)
{
if(temp!=NULL)
{
inorder(temp->left);
printf(" %d",temp->data);
inorder(temp->right);
}
}

OUTPUT

Program for Binary Search Tree
1.Create
2. Search
3. Delete
4.Display
Enter your choice1
Enter the Element10
Enter your choice1
Enter the Element8
Enter your choice1
Enter the Element9
Enter your choice 1
Enter the Element 7
Enter your choice1
Enter the Element15
Enter your choice1
Enter the Element13
Enter your choice 1
Enter the Element14
Enter your choice 1
Enter the Element12
Enter your choice1
Enter the Element16
Do u want to continue enter more elements(y/n)y
1.Create
2. Search
3. Delete
4.Display
Enter your choice4
The tree is:7 8 9 10 12 13 14 15 16
1.Create
2. Search
3. Delete
4.Display
Enter your choice2
Enter the element which u want to search 16
The 16 Element is present
Parent of node 16 is 15
1.Create
2. Search
3. Delete
4.Display
Enter your choice 3
Enter the Element u wish to delete 13
The 13 Element is present
Now deleted it!
1.Create
2. Search
3. Delete
4.Display
Enter your choice 4
The tree is: 7 8 9 10 12 14 15 16



_____________________http://sundcs.blogspot.com/_________________


// Implementation of insertion operation in AVL tree

#include<stdio.h>
#include<malloc.h>
typedef enum { FALSE ,TRUE } bool;
struct node
{
int info;
int balance;
struct node *lchild;
struct node *rchild;
};
struct node *insert (int , struct node *, int *);
struct node* search(struct node *,int);
main()
{
bool ht_inc;
int info ;
int choice;
struct node *root = (struct node *)malloc(sizeof(struct node));
root = NULL;
while(1)
{
printf("1.Insert\n");
printf("2.Display\n");
printf("3.Quit\n");
printf("Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("Enter the value to be inserted : ");
scanf("%d", &info);
if( search(root,info) == NULL )
root = insert(info, root, &ht_inc);
else
printf("Duplicate value ignored\n");
break;
case 2:
if(root==NULL)
{
printf("Tree is empty\n");
continue;
}
printf("Tree is :\n");
display(root, 1);
printf("\n\n");
printf("Inorder Traversal is: ");
inorder(root);
printf("\n");
break;
case 3:
exit(1);
default:
printf("Wrong choice\n");
}
}
}
struct node* search(struct node *ptr,int info)
{
if(ptr!=NULL)
if(info < ptr->info)
ptr=search(ptr->lchild,info);
else if( info > ptr->info)
ptr=search(ptr->rchild,info);
return(ptr);
}
struct node *insert (int info, struct node *pptr, int *ht_inc)
{
struct node *aptr;
struct node *bptr;
if(pptr==NULL)
{
pptr = (struct node *) malloc(sizeof(struct node));
pptr->info = info;
pptr->lchild = NULL;
pptr->rchild = NULL;
pptr->balance = 0;
*ht_inc = TRUE;
return (pptr);
}
if(info < pptr->info)
{
pptr->lchild = insert(info, pptr->lchild, ht_inc);
if(*ht_inc==TRUE)
{
switch(pptr->balance)
{
case -1:
pptr->balance = 0;
*ht_inc = FALSE;
break;
case 0:
pptr->balance = 1;
break;
case 1:
aptr = pptr->lchild;
if(aptr->balance == 1)
{
printf("Left to Left Rotation\n");
pptr->lchild= aptr->rchild;
aptr->rchild = pptr;
pptr->balance = 0;
aptr->balance=0;
pptr = aptr;
}
else
{
printf("Left to right rotation\n");
bptr = aptr->rchild;
aptr->rchild = bptr->lchild;
bptr->lchild = aptr;
pptr->lchild = bptr->rchild;
bptr->rchild = pptr;
if(bptr->balance == 1 )
pptr->balance = -1;
else
pptr->balance = 0;
if(bptr->balance == -1)
aptr->balance = 1;
else
aptr->balance = 0;
bptr->balance=0;
pptr=bptr;
}
*ht_inc = FALSE;
}
}
}
if(info > pptr->info)
{
pptr->rchild = insert(info, pptr->rchild, ht_inc);
if(*ht_inc==TRUE)
{
switch(pptr->balance)
{
case 1:
pptr->balance = 0;
*ht_inc = FALSE;
break;
case 0:
pptr->balance = -1;
break;
case -1:
aptr = pptr->rchild;
if(aptr->balance == -1)
{
printf("Right to Right Rotation\n");
pptr->rchild= aptr->lchild;
aptr->lchild = pptr;
pptr->balance = 0;
aptr->balance=0;
pptr = aptr;
}
else
{
printf("Right to Left Rotation\n");
bptr = aptr->lchild;
aptr->lchild = bptr->rchild;
bptr->rchild = aptr;
pptr->rchild = bptr->lchild;
bptr->lchild = pptr;
if(bptr->balance == -1)
pptr->balance = 1;
else
pptr->balance = 0;
if(bptr->balance == 1)
aptr->balance = -1;
else
aptr->balance = 0;
bptr->balance=0;
pptr = bptr;
}
*ht_inc = FALSE;
}
}
}
return(pptr);
}
display(struct node *ptr,int level)
{
int i;
if ( ptr!=NULL )
{
display(ptr->rchild, level+1);
printf("\n");
for (i = 0; i < level; i++)
printf(" ");
printf("%d", ptr->info);
display(ptr->lchild, level+1);
}
}
inorder(struct node *ptr)
{
if(ptr!=NULL)
{
inorder(ptr->lchild);
printf("%d ",ptr->info);
inorder(ptr->rchild);
}
}

OUTPUT

1.Insert
2.Display
3.Quit
Enter your choice : 1
Enter the value to be inserted : 23
1.Insert
2.Display
3.Quit
Enter your choice : 1
Enter the value to be inserted : 15
1.Insert
2.Display
3.Quit
Enter your choice : 1
Enter the value to be inserted : 13
Left to Left Rotation
1.Insert
2.Display
3.Quit
Enter your choice : 2
Tree is :
23
15
13
Inorder Traversal is: 13 15 23
1.Insert
2.Display
3.Quit
Enter your choice : 3


_____________________http://sundcs.blogspot.com/_________________
Subscribe to: Posts (Atom)