EXP.NO:1 Implementation of Sorting Algorithms
i) Quick Sort
Aim:
To write a C++ program to perform Quick sort using the divide and conquer technique
Algorithm:
Step 1: Start the process.
Step 2: Declare the variables.
Step 3: Enter the list of elements to be sorted using the get()function.
Step 4: Divide the array list into two halves the lower array list and upper array list using the merge sort function.
Step 5: Sort the two array list.
Step 6: Combine the two sorted arrays.
Step 7: Display the sorted elements using the dis() function.
Step 8: Stop the process.
PROGRAM
#include<iostream.h>
#include<conio.h>
int n;
class qs
{
public:
int a[10];
void get();
void qsort(int,int);
void dis();
void swap(int &,int &);
int median(int,int);
};
void qs::get()
{
int i;
cout<<”\n\nQuick sort\n\n”;
cout<<”Enter the number of element :”;
cin>>n;
cout<<\nEnter the elements :\n”;
for(i=0;i<n;i++)
cin>>a[i];
}
int qs::median(int left,int right)
{
int centre=(left+right)/2;
if(a[left]<a[centre]
swap(a[left],a[centre]);
if(a[right]<a[left])
swap(a[right],a[left]);
if(a[right]<a[centre])
swap(a[centre],a[right]);
swap(a[centre],a[right-1]);
return(a[right-1]);
}
void qs::dis()
{
cout<<”\nSorted elements :\n”;
for(i=0;i<n;i++)
cout<<” ”<<a[i];
}
void qs::swap(int &a,int &b)
{
int t;
t=a;
a=b;
b=t;
}
void qs::qsort(int left,int right)
{
if(left<right)
{
int pivot=median(left,right);
int i=left;
int j=right-1;
for(;;)
{
while(a[++i]<pivot);
while(pivot<a[--j]);
if(i<j)
swap(a[i],a[j]);
else
break;
}
if(l<right)
swap(a[i],a[right-1]);
qsort(left,i-1);
qsort(i+1,right);
}
}
void main()
{
qs q;
clrscr();
q.get();
q.qsort(0,n-1);
q.dis();
getch();
}
Output:
Enter the number of elements: 3
Enter the elements:
2
7
1
Sorted elements:
1 2 7
Result:
Thus the C++ program to perform Quick sort using the divide and conquer technique has been completed successfully
EXP.NO:1 ii) MERGE SORT
Aim:
To write a C++ program to perform merge sort using the divide and conquer technique.
Algorithm:
Step 1: Start the process.
Step 2: Declare the variables.
Step 3: Enter the list of elements to be sorted using the get function.
Step 4: Divide the array list into two halves the lower array list and upper array list using the merge sort function.
Step 5: Sort the two array list.
Step 6: Combine the two sorted arrays.
Step 7: Display the sorted elements using the get () function.
Step 8: Stop the process.
PROGRAM:
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
int temp[200], n;
class ms
{
public:
int a[200],l,r,m;
void cre();
void mss(int t[],int,int);
void mg(int t[],int,int,int);
void dis();
};
void ms::cre()
{
int i;
cout<<”\m\nMerge sort\n\n”;
cout<<”\n\nEnter the number of element:”;
cin>>n;
cout<<\nEnter the elements :\n”;
for(i=0;i<n;i++)
cin>>a[i];
}
void ms::dis()
{
int i;
cout<<”\nthe sorted elements are :\n”;
for(i=0;i<n;i++)
cout<<” ”<<a[i];
}
void ms::mss(int t[],int l,int r)
{
if(l<r)
{
m=(l+r)/2;
mss(t,l,m);
mss(t,m+1,r);
mg(t,l,m+1,r);
}
}
void ms::mg(int t[],int lp,int rp,int re)
{
int le,i,ne,tp;
le=rp-1;
tp=lp;
ne=re-lp+1;
while((lp<=le)&&(rp<=re))
{
if(a[lp]<=a[rp])
{
t[tp]<=a[lp];
tp=tp+1;
lp++;
}
else
{
t[tp]<=a[rp];
tp=tp+1;
rp++;
}
}
while(lp<=le)
{
t[tp]<=a[lp];
lp++;
tp++;
}
while(rp<=re)
{
t[tp]<=a[rp];
rp++;
tp++;
}
for(i=1;i<=ne;i++)
{
a[re]=t[re];
re--;
}
}
void main()
{
ms o;
clrscr();
o.cre();
o.mss(temp,0,n-1);
o.dis();
getch();
}
Output:
MERGE SORT
Enter the size of the array: 5
Enter the elements of the array…
3
5
2
8
7
Sorted Elements:
2
3
5
7
8
Result:
Thus the C++ program to perform merge sort using the divide and conquer technique has executed successfully.
EXP NO: 1 iii) HEAP SORT
Aim:
To write a C++ program to perform Heap sort using the divide and conquer technique
Algorithm:
Step 1: Start the process.
Step 2: Declare the variables.
Step 3: Enter the list of elements to be sorted using the get function.
Step 4: Divide the array list into two halves the lower array list and upper array list using the merge sort function.
Step 5: Sort the two array list.
Step 6: Combine the two sorted arrays.
Step 7: Display the sorted elements using the get() function.
Step 8: Stop the process.
PROGRAM
#include<iostream.h>
#include<conio.h>
#define M 100
class hs
{
int n,i;
int a[M];
public:
void get();
void bh();
void pd(int h,int n);
void dis();
void sort();
};
void hs::get()
{
cout<<”\n\nHeap sort\n\”;
cout<<”\nEnter the number of element:”;
cin>>n;
cout<<\n\nEnter the elements :”;
for(i=0;i<n;i++)
cin>>a[i];
bh();
}
void hs::bh()
{
for(i=(n/2);i>0;i--);
pd(i,n);
}
void hs::sort()
{
int t;
for(i=n;i>=2;i--)
{
t=a[1];
a[1]=a[i];
a[i]=t;
pd(i,i-1);
}
}
void hs::pd(int h,int n)
{
int c;
int temp=a[h];
for(;h*2<=n;h=c)
{
c=h*2;
if(c!=n&&a[c+1]>a[c])
c++;
if a[c]>temp)
a[h]=a[c];
else
break;
}
a[h]=temp;
}
void hs::dis()
{
cout<<”\n\nSorted elements :\n”;
for(i=0;i<n;i++)
cout<<a[i]<<” ”;
}
void main()
{
hs h;
clrscr();
h.get();
h.sort();
h.dis();
getch();
}
Output:
Heap sort
Enter the number of elements: 5
66 56 78 90 21
Sorted Elements:
21 56 66 78 90
Result:
Thus the C++ program to perform Heap sort using the divide and conquer technique has been completed successfully.
EXP NO: 2 IMPLEMENTATION OF BINARY SEARCH TREE ALGORITHM
Aim:
To write a C++ program to perform binary search using the divide and conquer technique.
Algorithm:
Step 1: Start the process.
Step 2: Declare the variables.
Step 3: Enter the list of elements to be searched using the get function.
Step 4: Divide the array list into two halves the lower array list and upper array
List.
Step 5: It works by comparing a search key k with the arrays middle element a[m].
Step 6: If they match the algorithm stops; otherwise the same operation is repeated recursively
for the first half of the array if k < a[m] and the second half if k > a[m].
Step 7: Display the searching results
Step 8: Stop the process.
PROGRAM
#include<iostream.h>
#include<conio.h>
class bsearch
{
public:
int a[200],n,x,i;
void get();
int bs();
void dis(int);
};
Void bsearch::get()
{
cout<<”\n\n Binary sort\n\n”;
cout<<”\n\n Enter the number of element :”;
cin>>n;
cout<<\nEnter the elements :\n”;
for(i=0;i<n;i++)
cin>>a[i];
cout<<\nEnter the elements to be searched :”;
cin>>x;
}
void bsearch::dis(int s)
{
int i;
if(s!=0)
cout<<”\nThe element is found at position :”<<s+1;
else
cout<<”\n\nThe element is not found”;
}
int bsearch::bs()
int l=1;
int h=n;
while(1<h)
{
int m(l+h)/2;
if(x<a[m])
h=m-1;
else if(x>a[m])
l=m+1;
else
return m;
}
return 0;
}
void main()
{
bsearch b;
clrscr();
b.get();
int s=b.bbs();
b.dis(s);
getch();
}
Output:
Binary Search
Enter the number of elements: 4
Enter the elements:
1
3
7
8
Enter the element to be searched: 8
The element is found at position: 4
Result:
Thus the C++ program to perform binary search using the divide and conquer technique has executed successfully
EXP NO: 3 IMPLEMENTATION OF MINIMUM SPANNING TREE
Aim:
To write a C++ program to find the minimum spanning tree using prim’s algorithm
Algorithm:
Step1: Start the program.
Step2: Declare the variables.
Step3: Using the get function get the number of vertices and enter their weights.
Step4: Using the cal function calculate the minimum spanning tree.
Step5: Display the minimum spanning tree for the given weighted graph.
Step6: End the program
PROGRAM:
#include<iostream.h>
#include<conio.h>
class prim
{
int a,b,u,v,i,j,n,noe;
int vi[10],min,mc,c[10][10];
public:
prim()
{
noe=1;
mc=0;
void read();
void prims(c[][10],int n);
};
void prim::read()
{
cout<<”\n\nEnter the number of vertices :”;
cin>>n;
cout<<\nEnter the adjacency matrix :\n”;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
cin>>c[i][j];
if(c[i][j]==0)
c[i][j]=999;
}
}
prims(c,n);
}
void prim::prims(int c[][10],int n)
{
for(i=2;i<=n;i++)
vi[i]=0;
cout<<”\nEdges in the spanning tree are :\n;
vi[1]=1;
while(noe<1)
{
for(i=1,min=999;i<=1;i++)
for(j=1;j<=n;j++)
if(c[i][j]<min)
if(vi[i]==0)
continue;
else
{
min=c[i][j];
a=u=i;
b=v=j;
}
if((vi[u]==0)||(vi[v]==0))
noe++;
cout<<”\nEdge(”<<a<<”-->”<<b<<”) :”<<min;
mc+=min;vi[b]=1;
}
c[a][b]=c[b][a]=999;
}
cout<<”\n\nMinimum cost spanning tree is :”<<mc;
}
void main()
{
clrscr();
cout<<”\nPrims algorithm\n”;
prim p;
p.read();
getch();
}
Output:
PRIM'S ALGORITHM
Enter the number of vertices: 3
Enter the adjacency matrix:
0 5 2
5 0 1
0 1 0
Enter the spanning tree are:
Edge <1---->3>: 2
Edge<3---->2>: 1
Minimum cost spanning tree is: 3
Result:
Thus the C++ program to find the minimum spanning tree using prim’s algorithm has been completed successfully.
EXP NO: 4 IMPLEMENTATION OF KNAPSACK PROBLEM
Aim:
To write a C++ program to solve the knapsack problem using greedy method.
Algorithm:
Step1: Start the program.
Step2: Declare the variable.
Step3: Using the get function read the number of items, capacity of the bag,
Weight of the item and value of the items.
Step4: Find the small weight with high value using the find function.
Step5: Find the optimal solution using the function findop ().
Step6: Display the optimal solution for the items.
Step7: Stop the process.
Program:
#include<iostream.h>
#include<conio.h>
int we=0;
class knapsack
{
int max,obj;
float s[100],w[100],p[100],p1[100];
public:
void get();
void calc();
void disc();
};
void knapsack::get()
{
float temp;
cout<<”\nEnter the maximum value of knapsack :”;
cin>>max;
cout<<”\nEnter the number of objects :”;
cin>>obj;
for(i=1;i<=obj;i++)
{
cout<<”\nEnter the value :”;
cin>>w[i];
we+=w[i];
cout<<”\nEnter the profit :”;
cin>>p[i];
p1[i]=p[i]/w[i];
cout<<”\np1=”<<p1[i];
}
for(i=1;i<obj;i++)
for(int j=1;j<=obj;j++)
if(p1[j]<p1[j-1])
{
temp=p1[j];
p1[j]=p1[j+1];
p1[j+1]=temp;
temp=w[j];
w[j]=w[j+1];
w[j+1]=temp;
temp=p[j];
p[j]=p[j+1];
p[j+1]=temp;
}
for(i=1;i<=obj;i++)
cout<<”\n\t\t”<<w[i]<<”\t\t”<<p[i]<<”\t\t ”<<p1[i]<<”\n”;
}
void knapsack::calc()
{
int k=1;as=0;
for(int i=1;i<=obj;i++)
{
for(k=k;k<=w[i]+as;k++)
s[k]=p1[i];
as=k;
we+=w[i];
}
}
void knapsack::disc()
{
float op_w1;
int i;
if(we>=max)
for(i=1;i<=max;i++)
op_w1+=s[i];
out<<”\n Maximum profit= ”<<op_w1;
}
void main()
{
knapsack k;
clrscr();
k.get();
k.calc();
k.disc();
getch();
}
Output:
Enter the maximum value of knapsack: 10
Enter the number of objects: 3
Enter the value 7
Enter the profit 70
P1=10
Enter the value 3
Enter the profit 30
Enter the value 11
Enter the profit 110
P1= 10
7 70 10
3 30 10
11 110 10
Maximum Profit 100
Result:
Thus the C++ program for solving Knapsack problem has been executed successfully.
EXP NO: 5 IMPLEMENTATION OF 8 QUEEN’S PROBLEM
Aim:
To write a C++ program to find the solution to the 8 queen’s problem using the backtracking method.
Algorithm:
Step1: Start the process.
Step2: Enter the no. of queens.
Step3: Using the queen function place all the queens.
Step4: Check the position to place the queen is free or not.
Step5: Check finally if all the queens are placed.
Step6: Check for all the constraints, check the rows and columns
Step7: If no clash then all the queens are placed in correct position.
Step8: stop.
PROGRAM
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
class queen
{
int x[20],count;
public:
void ques(int);
int place(int,int);
void printq();
void disp();
queen():count(0)
{ }
};
void queen::ques(int k)
{
for(int=i;i<=8;i++)
if(place(k,i))
x[k]=i;
if(k==8)
printq();
else
ques(k+1);
}
}
int queen::place(int k,int i)
{
for(j=1;j<k;j++)
if(x[j]==i||abs(x[j]-i)==abs(j-k))
return 0;
return 1;
}
void queen::printq()
{
count++;
for(int i=1;i<=8;i++)
{
cout<<” \t\t\t”;
for(int j=1;j<=8;j++)
{
if(x[i]==j)
cout<<”q”;
else
cout<<”x”;
}
cout<<end1;
}
cout<<”\n\n\n\n\n\n\n”;
}
void queen::disp()
{
if(count==0)
cout<<”\n\t\tNo solution possible”;
else
cout<<”\n\t\tNo of solution possible”<<count;
}
void main()
{
queen q;
clrscr();
q.ques(1);
q.disp();
getch();
}
Output:
********
********
********
********
********
********
********
********
********
********
********
********
********
********
********
********
Number of possible solutions are: 92
Result:
Thus the C++ program to find the solution to the 8 queen’s problem using the backtracking method has been completed successfully.
EXP NO: 6 IMPLEMENTATION OF ALL PAIR SHORTEST PATH ALGORITHM
Aim:
To write a C++ program to find the shortest path using Floyd’s algorithm.
Algorithm:
Step1: Start the program.
Step2: Declare the variables.
Step3: Using the get function get the number of vertices and enter their weights.
Step4: Using the cal function calculate the shortest path
Step5: Display the shortest path distance graph.
Step6: End the program.
PROGRAM:
#include<iostream.h>
#include<conio.h>
int a[10][10];
int cost[10][10];
int mini(int,int);
int main()
{
clrscr();
int i,j,k,n,m;
cout<<”\n\nEnter the number of vertices :”;
cin>>n;
cout<<\nEnter the no.of edge :\n”;
cin>>m;
cout<<\nEnter the matrix :\n”;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
cin>>a[i][j];
}
}
for(k=0;k<n;k++)
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
a[i][j]=mini(a[i][j],a[i][k]+a[k][j]);
}
}
}
cout<<”\n\nThe all pair shortest path is :\n”;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
cout<<”\n”<<i<<”-->”<<j<<” : ”<<a[i][j];
}
}
cout<<”\n\nThe cost matrix is :\n\n”;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
cout<a[i][j]<<” ”;
}
cout<<”\n”;
}
getch();
return 0;
}
int mini(int a,int b)
{
if(a<b)
return a;
else
return b;
}
OUTPUT
ENTER THE NUMBER OF VERTICES: 3
ENTER THE NUMBER OF EDGES: 5
ENTER THE DISTANCE MATRIX:
0 4 15
28 0 2
3 999 0
THE ALL PAIR SHORTEST PATH OF THE GRAPH
0->0: 0
0->1: 4
0->2: 6
1->0: 5
1->1: 0
1->2: 2
2->0: 3
2->1: 7
2->2: 0
THE COST MATRIX IS:
0 4 6
5 0 2
3 9 8
Result:
Thus the C++ program to find the shortest path using Floyd’s algorithm has been completed successfully.
EXP NO: 7 IMPLEMENTATION OF TRAVELLING SALESMAN
PROBLEM
Aim:
To write a C++ program to solve the travelling sales man problem using the dynamic programming approach.
Algorithm:
Step1: Start the process
Step2: Enter the number of cities
Step3: Enter the cost matrix of all the cities
Step4: Find all possible feasible solutions by taking the permutation of the cities which is to be
covered.
Step5: Find the cost of each path using the cost matrix.
Step6: Find out the path with minimum cost.
Step7: If more than one path having the same cost considers the first occurring path.
Step8: That is selected as the optimum solution.
Step9: stop the process.
PROGRAM:
#include<iostream.h>
#include<conio.h>
int a[10][10],visit[10],n,cost;
class travel
{
public:
int least(int c);
{
int i,nc=999;
int min=999,kmin;
for(i=0;i<n;i++)
if((a[c][i]!=0)&&(visit[i]==0))
if(a[c][i]<min)
{
min=a[i][0]+a[c][i];
kmin=a[c][i];
nc=i;
}
if(min!=999)
cost+=kmin;
return(nc);
}
void mincost(int city)
{
int i,ncity;
visit[city]=1;
cout<<city+1<<”-->”;
ncity=least(city);
if(ncity==999)
{
ncity=0;
cout<<city+1;
cost+=a[city][ncity];
return;
}
mincost(ncity);
}
};
void main()
{
travel t;
int i,j;
cirscr();
cout<<”TRAVELING SALESMAN PROBLEM\n”;
cout<<”ENTER THE NO OF CITIES:”;
cin>>n;
for(i=0;i<n;i++)
{
cout<<”ENTER THE CONNECTIVITY:”<<i+1;
for(j=0;j<n;j++)
{
cin>>a[i][j];
}
}
cout<<end1;
visit[i]=0;
cout<<”THE PATH IDS:\n\t\t”;
t.mincost(0);
cout<<”\n THE MINIMUM COST:”<<cost;
getch();
}
Output:
TRAVELLING SALESMAN PROBLEM
ENTER THE NUMBER OF CITIES: 3
ENTER THE CONECTIVITY: 1
0
2
2
ENTER THE CONECTIVITY:2
2
0
2
ENTER THE CONECTIVITY:3
1
2
3
THE PATH IDS:
1->3->2->1
THE MINIMUM COST: 6
Result:
Thus the C++ program to solve the travelling salesman problem using the dynamic programming approach.
EXP NO: 8 IMPLEMENTATION OF GRAPH COLOURING
Aim:
To write a C++ program to solve graph colouring problem.
Algorithm:
Step1: Start the process
Step2: read the number of vertices.
Step3: For each vertex of a graph, determine each degree, and then classify vertexes in the
degree descending order.
Step5: colour the vertices.
Step6: print the coloured vertices order.
Step7: stop the process.
PROGRAM
#include<iostream.h>
#include<conio.h>
#include<math.h>
#define N 5
#define M 3
//clrscr();
int g[N][N];
int x[N];
void nextvalue(int k)
{
do
{
x[k]=(x[k]+1%(m+1));
if(x[k]==0)
return;
for(int j=0;j<N;j++)
{
if((g[k][i]!=0)&&(x[k]==x[j]))
{
break;
}
}
if(j==N)
return;
}while(!0);
}
void display()
{
for(int i=0;i<N;i++)
cout<<x[i]<<” ”;
cout<<”\n”;
}
void M_colouring(int k)
{
do
{
nextvalue(k);
if(x[k]==0)
return;
if(k==N-1)
display();
else
M_colouring(k+1);
}while(!0);
}
void main()
{
cout<<”\n ENTER THE GRAPH(IF EDGE EXIST YES=1,NO=0”;
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
{
if((i!=j)&&(i<j))
{
cout<<i+1<<”and ”<<j+1<<”!”;
cin>>g[i][j];
g[j][i]=g[i][j];
}
if(i=j)
g[i][j]=0;
}
M_colouring(0);
}
}
Output:
Enter the graph <if edge exist yes=1, no=0>1 and 2:1
1 and 3:1
1and 4:1
1 and 5:0
2 and 3:0
2 and 4:1
2 and 5:1
3 and 4:1
3 and 5:0
4 and 5:1
1 2 2 3 1
1 3 3 2 1
2 1 1 3 2
2 3 3 1 2
3 1 1 2 3
3 2 2 1 3
Result:
Thus the C++ program to solve graph colouring problem has been completed successfully.
EXP NO: 9 IMPLEMENTATION OF MULTISTAGE GRAPHS
Aim:
To write a C++ program to find the shortest path of the multistage graph using dynamic programming.
Algorithm:
Step1: Start the program.
Step2: Declare the variables.
Step3: read the number of vertices and enter their weights.
Step4: Using the graphs function calculate the shortest path
Step5: Display the shortest path. .
Step6: End the program.
PROGRAM:
#include<iostream.h>
#include<conio.h>
void fgraph();
static findr(int);
static int g[100][100];
static int n;
static int k;
int i,j,r,w;
void main()
{
clrscr();
cout<<”Multistage graph”;
cout<<”\n\n\nEnter the no. of vertices:”;
cin>>n;
cout<<”\n\n\nEnter the total no. of states:”;
cin>>k;
cout<<”\n\nIf there is a edge between following vertices Enter its weight else 0”;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
g[i][j]=0;
if((i!=j)&&(i<j))
{
cout<<i;
cout<<”and”<<j;
cout<<”:”;
cin>>w;
g[i][j]=w;
}
}
fgraph();
getch();
}
void fgraph()
{
int cost[100];
int d[100];
int p[100];
for(i=1;i<=n;i++)
cost[i]=0;
for(j=n-1;j>=1;j--)
{
r=findr(j+1);
cost[j]=g[j][r]+cost[r];
d[j]=r;
}
p[1]=1;p[k]=n;
for(j=2;j<k;j++)
p[j]=d[p[j-1]];
cout<<d[1];
cout<<”****”;
for(j=2;j<n;j++)
{
if((d[j]==d[j-1]||d[j]==0))
continue;
cout<<d[j];
}
cout<<n;
}
static int findr(int cu)
{
int k;
int r1=n+1;
for(int h=1;h<=n;h++)
{
if((g[h][cu]!=0)&&(r1==n+1))
{
r1=h;
continue;
}
if(g[h][cu]!=0
{
if(g[h][cu]<g[r1][cu])
r1=h;
}
}
return r1;
}
OUTPUT
Enter the number of the vertices:
4
Enter the total number of stages in your graph:
4
If there is a edge between the following vertices enter its weight else 0:
1 and 2: 2
1 and 3: 4
1 and 4: 8
2 and 3: 3
2 and 4: 1
3 and 4: 3
1***>2***>4
Result:
Thus the shortest path of the multistage graph using dynamic programming has been completed successfully.
(ADDITIONAL PROGRAM)
Ex. No: 10 SELECTION SORT USING BRUTE FORCE METHOD
Aim:
To write a C++ program to perform selection sort using the brute force technique.
Algorithm:
Step 1: Start the process.
Step 2: Declare the variables.
Step 3: Enter the list of elements to be sorted using the get function.
Step 4: find the smallest element and exchange it with the first element, putting the first
element in the final position in the sorted list
Step 5: Then the scan starts from the second element to find the smallest among n-1 elements
and exchange it with the second element.
Step 6: Display the sorted elements using the put function.
Step 7: Stop the process.
Source Code:
#include <iostream.h>
#include <conio.h>
int a[10],n;
int i;
void get();
void put();
void selection(int[],int);
void main()
{
clrscr();
cout<<"\n<< SELECTION SORT ";
put();
getch();
}
void get()
{
Cout<<” ENTER THE SIZE OF THE ARRAY ";
Cin>>n;
Cout<<”ENTER THE ARRAY ELEMENTS ONE BY ONE”;
for(i=0;i<n;i++)
cout<<a[i];
selection(a,n);
}
void put()
{
Cout<<” THE SORTED ELEMENTS ARE ";
for(i=0;i<n;i++)
cout<<a[i];
}
void selection(int a[],int n)
{
int i,j,min,t;
for(i=0; i<=n-2; i++)
{
min=i;
for(j=i+1; j<=n-1; j++)
{
if(a[j]<a[min])
min=j;
}
t=a[i];
a[i]=a[min];
a[min]=t;
}
}
Output:
SELECTION SORT
Enter the size of the array: 4
Enter the elements of the array…
3
5
2
8
Sorted Elements are:
2
3
5
8
Result:
Thus the selection sort using brute force method has been completed successfully.
No comments:
Post a Comment