Programto implement Selection
sort.
#Createdby :230921 Akshay Rao M
#Date :08-07-2025
Algorithm:
Step 1:Fori-0
to n-1
Repeat throughstep3
min=i
Step 2:Forj=i
to n-1
Repeat
If(a[j]<a[min])
then
Min=j
[Endofif]
[Endoffor]
Step 3:If
min!=Ithen
A[i]>a[min]#swap
[Endofif]
[Endoffor]
Program:
#include<stdio.h>
#include<conio.h>
voidmain)
int a[10],i,n.j,min;
clrscr();
printf("Enter
the array size:");
scanf("%d",&n);
for(i-0;i<n;itt)
scanf("%d",&a[il);
printf("Sorted
elements are:"):
for(i-0;i<n-1;itt)
{
min=i;
for(í-i:j<nj++)
if(a[j]<a[min))
min-j;
if(min=i)
temp-a[i];:
ali]-a[min):
amin]=temp;
UO5SY23S02 11
for(i=0;i<n;itt)
printf("%d".a[i]):
etch():
Output:
Enter the arra size:12
Enter [Link]
elemets:9045 67 9% 76 49 67 12 23 2123 21
Sorted elements are:1221 21 23 23 45 49 67 67 76 90 98
Enter the arra size:10
Enter 10 arra elements 98 97 65 64 76 83 43 21 1112
Sorted elementsare:11 12 21 43 64 65 76 83 97 98
Analysis:
[Link]:O(N)
:
Best case:0(N)
Average case:o(N')
Worst case: O(N
[Link]: OH
UO5SY23S0211
Find minimum and maximum number inan
arrayof n elements using
Divideand Conquer Method.
#Createdby:230921 Akshay Rao M
#Date :16-07-2025
Algorithm:
Stepl:
minmax([Link]):
If(i=5))then
return(a[i],a[i])
(endif)
Step2: elseif(i=j-1)then
If(ai]<a[j)
return(a[i],a[j])
else
return(a[i],a[i])
(endif)
Step3: mid-(itj)/2
minmax(a,i,mid)
return(min,max)
minmax(a,mid+1,)
return(min,max)
if(lmin<min)
then
min=Imin
else
min=rmin
[endif]
If(lmax>rmax)
then
Max=Imax
else
max=rmax
[end ofif]
return(min,max)
UO5SY23S02 11
Program:
#include<stdio.h>
#include<conio.h>
int min,max;
voidminmax(int[],int,int);
voidmain()
int ij.n,a[15];
clrscr();
printf("Enter
the arraysize:");
scanf("%d",&n);
printf("Enter
the %d arrayelements:",n);
for(i0:in;i++)
scanf("%d",&a[i]);
);
minmax(a,0,n-1
printf("MaximumValue inthearray is :%d"max);
Value inthearray is :%d",min);
printf("\nMinimum
getch();
voidminmax(int a[],int
i,int
j)
int mid-0,Imin,
Imax,rmin,rmax;
if(íj)
min-a[i];
max=a[i];
}
else if(i-j-1)
if(a[i]<a[i])
{
min-a[i]:
max-alj);
else
min=aj]:
max-a[i]:
UO5SY23S0211
else
mid-(itj)/2:
minmax(a,[Link]);
Imin-min;
Imax=max;
minmax(a,mid+1,):
rmin=min;
rmax-Fmax;
if(lmin<rmin)
min=Imin;
else
min-rmin:
if(lmax>max)
max=lmax;
else
max=rmax:
Qutput:
Enter the arraysize:12
Enter the 12 arra elements:6576 33 89 66 45 89 45 22 1187 65
aximum Value in the arrayis :89
1inimum Ualue in the arrayis : 11
Enterthe arra s1ze: 10
Enter the 10 arra elements:37 5 21 9 0 6 7 8
MaximLm Ua lue inthe array is :9
1inimum Ualue inthe array is
Analysis:
Time Complexity:Let T(n)be the number ofcomparison made by the function
where
minmax(x,y) the number of elements n=y-x+[Link] T(n)representthe comparisons,then
recursion
relation
can be representedas,
0 for n=1
T(n)=
1for n =2
2r()+2
for n>2)
of power of2 then n=2* where k isa heightof the recursion
tree.
Assume that n is inthe form
So.
=> 2.(2.T( +2)+2
T(n)-2.T(;+2 >..» 2
ofcomparisionis less.
Compared to naïve method inthe divideand conquer,the number
time
However usingasymptotic notation,both of the approaches arerepresentedby the
complexity ofO(n).
UO5SY23S0211
Sort agivenset of element usingthe insertion sortmethod and determine
the time required to sortthe [Link] the experimentfordifferent
valuesof [Link] number of element in the list to be sortedand plota graph
of the time taken vs n.
#Created by:230921 Akshay Rao M
#Date :06-08-2025
Program:
#include<stdio.h>
#include<conio.h>
#include<time.h>
voidinsertion(int[],int);
voidmain()
inta[15],i.n;
double time,start,stop:
clrscr():
the arraysize:");
printf("Enter
scanf("%od",&n);
%d arrayelements:",n);
printf("Enter
for(i-0;i<n;itt)
scanf("%d",&ai]):
start-clock():
insertion(a,n);
delay(1000);
stop-clock);
elements aftersorting:"X
print("Array
for(i-0;i<n;itt)
printf("%d",a[i]);
Taken:
printf("nTime (stop-start)/CLOCKSPER
%1f",(double) SEC);
getch():
n)
a],int
voidinsertion(int
int ij,temp;
for(i=1;i<n;it+)
UO5SY23S0211
temp-ali):
j-i-l;
while(ý>-0&& alil>emp)
+1]-ajl:
alj
jj-l:
a[j+1]-temp:
delay(100):
Output:
Enterte arraysize:10
Enter 16 arrayelements:75 0 9 3 2 178 5 6
:0 1 2 3
Array elements aftersorting 55 679 78
Time Taken: 3.076923_
Graph:
Size Time Taken
5 1.483516
10 2.967033
12 4.285714
15 5.274725
20 10.254874
UO5SY23S02 11
Sort
of insertion
Time Analysis
12
10.254874
10
6
5.274725
4.285714
Time
Time Taken
4 2.967033
1.483516
2
0
10 12 15 20
Size
Time analysis:
Best Case : O(n)
Worst Case : O(n)
Average Case :0(n)
Writea program to implement Strassen's
MatrixMultiplication
of 2*2
matrix.
#Created by :230921 Akshay Rao M
#Date :12-08-2025
Program:
#include<stdio.h>
#include<conio.h>
void x[2][2]);
print_matrix(int
voidmain()
intij,k,n;
inta[2][2],2][2],x[2][2]:
intml,m2,m3,m4,m5,m6,m7;
clrscr();
the elements intomatrixA:"):
printf("Enter
for(i-0;i<2;it+)
for(j-0j<2j++)
scanf("%d",&ali][]);
the elements intomatrix B:");
printf("Enter
for(i-0;i<2;i++)
for(í-0;j<2j++)
scanf("%d",&b[i][i]);
elements of A are:\n");
printf("Array
print_matrix(a);
eements ofB are:n");
printf("Array
matrix(b);
print
ml-(a[0][+al1][1])*(b[][+b[1][1):
[0]:
m2-(al1][+al1][1])"b[0]
m3-a0][*(b[1]-b[ 1][1]):
m4-al 1][1]*(b1][-b [):
UO5SY23S02 11
1]:
mS-(a[0][+a[0][1])*b1][
m6-(a[1][0]-a[0][0])*
(b[0][0]+b[0j[1));
m7-(a[0[ 1][1])*(b{1][+b[
1]-a[ 1][1]):
[0]-ml+m4-mS+m7:
x[[ 1]-m3+mS:
1][0-m2+m4;
1][1]-m1 +m3-m2+m6;
ResultantmatrixAxB usingStrassensMethod is:n");
printf("The
print_matrix(x);
getch();
void x(2][2])
_matrix(int
print
inti,j;
for(i-0;i<2;i++)
for(j-0;j<2:j++)
",i]G]):
printf("d
printf("n");
Output:
Enter the elements into matrixA:12 4 5
Enter the elements into matrixB:6 19 2
Array elements of Matrix are: A
1 2
45
Array elements of MatrixB are
6 1
92
The ResultantmatrixAxB using StrassensMethod is:
24 5
69 14
Analysis:
Time Complexity : O(nlog')
UO5SY23S02 11
and
Sorta given set of n integerelements using merge sortmethod
compute itstime [Link] the program forvariedvaluesof n>500
and recordthe time takento sort.
#Created by : 230921 Akshay Rao M
#Date : 23-07-2025
Algorithm:
Stepl: Merge sort(a,l,h)
If(|<h)then
Set mid=(l+h)/2
Mergesort(a,l,mid)
Merge sort(a,mid+1.h)
Merge(a,l,mid,h)
(End ofif]
|End Function)
Step 2: Merge(a,l,mid,h)
Set i-l,j=mid+1,k=1
and
Repeat while(i<=mid) (j<-h)
If(a[i]<alj))
then:
M[k]=a[i]
the Iand
Increase k valueby 1
Else
M[k]-alj]
the jand
Increase k valueby1
[Endifl
[End loop]
Step 3: Repeat while(i<=mid)
M[k]-a[i]
Increase
the Iand k value byt
[End loop]
M[k]-alj]
Increasethe j and kvalueby I
[End loop]
For i=l
to i<=h
A[il-m[i]
[End loop]
[End function]
UO5SY23S02 11
Program:
#include<stdio.h>
#include<conio.h>
#include<time.h>
void merge_sort(int[],int,
int);
int);
void merge(int[],int,int,
voidmain()
int i,n.a(20]:
doubletime,start,stop;
clrscr():
the arraysize:");
printf("Enter
scanf("%od",&n):
the %d arrayelements:".n);
printf("Enter
for(i=0;i<n;itt)
scanf("%d",&ai]);
start=clock():
);
merge_sort(a,0,n-1
delay(200):
stop=clock():
elements aftersorting:");
printf("Array
for(i-0;i<n;itt)
printf("%d".a[i]):
delay(200);
l/ime-(stop-start)/(CLK_TCK);
printf("nTime
Taken:%If"(double)\(stop-start)/CLOCKS_PER_SEC);
getch();
voidmerge_sort(inta[]j1,int
h)
if(|<h)
int mid-(+h)/2;
merge sort(a,l,mid):
mergesort(a,mid+1,h);
merge(a,l,mid,h);
UO5SY23S02 11
voidmerge(int a[],int
l,intmid,int
h)
int
i-1.j-mid+1.k=l,m(20]:
&& j<=h)
while(i<=mid
iflalil<ajl)
m|k-ai]:
it+;
kt+;
else
m[k]-a[j}:
jt;
ktt;
while(i<-mid)
mlk]-li1
itt;
k++;
while(j<-h)
m[k-ali}:
jtt;
kt+;
for(i-l;i<-h;it)
ail-m[i]:
Output:
Enter the array size:15
Enter the 15 arrayelements
:6 4 2 3 5 8 0 12 3 8 5 4 6 1
Array e lements aftersorting
Time Taken: 1.70329? :01 12 23 34 45566 8 8
UO5SY23S0211
Analysis:
Best case:O(nlogn)
Average case:O(nlogn)
Worst case:O(nlogn)
Space Complexity:
O(n)
Status:Stable
Graph:
Size
Time
1.2087
10
1.4285
12
1.5384
15
1.6483
20
1.9223
Time Analysisof Merge Sort
2.5
2 1.9223
1.6483
1.5384
1.4285
1.5
1.2087
Time
1
Time Taken
0.5
5 10 12 15 20
Array Size
UO5SY23S0211
Sorta setof n integer
element usingquicksortand
required to sort determinethe time
the element of different
in thelist valueof [Link] number of
to be sortedand
plota graphtime element
takenvs n.
#Createdby : 230921
Akshay Rao M
#Date :30-07-2025
Algorithm:
Step 1: Quick
sort(a,low,high)
lf(low<high)
then
J-partition(a,[Link])
Quick_sort(a,lowj-1)
Quick_sort(aj+1,high)
Step 2: Return
Step 3:
Partition(a,low,high)
Step 4: key-a[low]
j-high
Repeat
Step 5: Repeat while
a[i]<keyand i<=high
i=i+]
Step 6: Repeat while
a[i]>key
jj-1
Step 4: ifisj
then
Swap a[i]
and a[j]
Else
Swap a[low]
and a[i]
Return
Program:
#include<stdio.h>
#include<conio.h>
#include<time.h>
voidquick_sort(int[],ip,int);
int partition(int|],int,
int);
void main)
inti.n.a/20:
double time,start,stop;
clrscr():
printf("Enter
the arraysize:");
UO5SY23S02 11
scanf("%od",&n);
printf("Enter
the %d array elements:",n):
for(i-0;i<n;it+)
scanf("%od",&a[i]):
start-clock():
quick_sort(a,0,n-1
):
delay(1000);
stop-clock():
printf("Array
elements aftersorting:");
for(i-0;i<n;it+)
printf("%d".a[i):
printf("nTime
Taken: %1f",(double)(stop-start)/CLOCKS
PERSEC);
etch():
voidquick_sort(int
a],int
low,int
high)
if(low<high)
int j;
j-partition(a,low,high);
quick_sort(a,low.j-1);
quick_sort(a,j+1,high);
delay(100);
intpartition(int
a[],int
low,int
high)
int key-alow]j-high,i=low+1Jemp;
while(1)
&& i<-high)
while(a[i]<key
itt;
while(alj]>key)
jj-l;
UO5SY23502 11
ifi)
temp-a[i]:
ali]-alj}:
alj]-temp;
else
temp-allow];
allow]-aljl:
a[j]-temp:
break;
it+;
j-:
returnj;
Output:
Entert}he arra size:
10
Enterthe 10 arra elements:54 23 1 4 67 8 9
:12344 5 67 89
Array e lements af tersorting
Time Taken: 1.428571
Graph:
Size Time Taken
5 1.153846
10 1.703297
12 1.81318Y
15 2.087912
20 2417582
UO5SY23S0211
Time Analysisof Quicksort
3
2.417582
2.5
2.087912
1.813187
2 1.703297
1.5
1.153846
TIME
1 -Time
0.5
5 10 12 15 20
Size
Analysis:
Time Complexity:O(nlogn)
Best Case : O(nlogn)
Average Case :O(nlogn)
Worst Case :O(nlogn)
Space Complexity:O(n)
Status : Stable
Writea program to check whether the givengraph isconnected ornot
using the DFS method.
#Createdby :230921 Akshay Rao M
#Date :19-08-2025
Algorithm:DFS(V)
I/Implement DepthFirstsearchofa given graph
IlnputG:{V,E}
/Graph G isrepresented usingAdjacency MatrixA[JO
I/Marks1 invectorvisitwhen a node isvisited
Step 1:visit[v]=1
Step 2:For i-1
to n Repeat
Ifvisit[i]-0
and A[v]il-0
Then
DFS()
Step 3:Return
Program:
#include<stdio.h>
#include<conio.h>
voiddfs(int
a[5][5],int
v,int
n,intvisit[1
0]);
voidmain()
int n,a[5][5],flag-0,i,s,j:
intvisit[10];
clrscr();
Vertexno:");
printf("Enter
scanf("%d",&n);
Matrixelements:");
printf("Enter
for(i=1;i<-n;it+)
for(i=lj<=nj++)
scanf("%d",
&a[i]i]);
for(i=1;i<=n;it+)
visit[i]-0;
source vertex:");
printf("Enter
U05SY23S0211
scanf("°%od",&s):
dfs([Link],visi):
for(i-1;init+)
if(visit[i]--0)
flag-1:
if(Mag-)
Connected"):
printf("Not
else
printf"Connected"):
elch):
al5]|5],int
voiddfs(int vintn,int
visit[10])
inti:
visit[v]=1:
for(i=1:i<=n;i++)
&& a[v]i]-=1)
if(visit[i]=-0
dfs([Link]):
Output:
EnterUertex nn:4
EnterMatrixelenents: 2
0 109
1 101
Entersource vertex:2
Nnt. Cannerted_
EnterUertex no:4
EnterMa trixelements :
O0 1 0
O00 1
Entersource vertex:3
Connected_
UO5SY23S0211
Analysis:
Adjacency Matrix :O(v)
Adjacency List:O(V+E)
19|2|as
UO5SY23S0211