Unit-V 1
ALGORITHMS
An Algorithm can be defined as step by step procedure that provides
solution to a given problem
Problem Algorithm Program
Characteristics of an Algorithm
[Link] algorithm must comprise of a finite number of steps.
[Link] should have zero or more valid and clearly defined input values.
[Link] should be definite i.e each instruction in the algorithm should be
defined clearly.
[Link] should be correct i.e u should be able to perform the desired task of
generating correct outpuit from the given input.
[Link] should be no ambiguity regarding the order of execution of
alsorithm steps.
[Link] should be able to terminate on its own .
Unit-V 2
Representation of an Algorithm
An algorithm can be represented by english like language ,flowcharts which
are mainly useful when algorihtm is simple and small.
Another way of representing algorithm is Pseudocode.
Pseudocode is an informal representation of the algorithm that provides
complete outline of a program so that programmers can easily understand it
and transform it into a program using programming language of their choice.
The structure and syntax of pseudocode is quite similar to typical
programming language constructs.
However there are certain conventions that are followed while writing
pseudocode.
Unit-V 3
Rules for writing pseudocode
[Link] a valid name for the algorithm .
[Link] each line of instruction ,specify a line number.
[Link] begin an identifier name with alphabet.
[Link] is not necessary to explicitly specify the data type of variables.
[Link] indent the statements present inside a block structure appropriately.
[Link] read and write statements to specify input and output operations
respectively.
[Link] if or if else for conditional statements. Further, you must end an if
construct by using end if statement.
[Link] looping statements ,you can use for/while statements ending with
corresponding end for or end while.
[Link] logical or relational operators whenever required.
[Link] an array or list of elements by specifying the name of the array
followed by square brackets. Ex list[i]
Unit-V 4
Write an algorithm to calculate the average of 10 numbers.
Average(avg,sum)
1. begin
2. set sum to 0,average to 0
3. for I = 1 to 10 do
4. read number
5. Sum = sum + number
6. End for
7. avg = sum/10
8 .write (sum)
9. write(avg)
10. stop
Unit-V 5
Searching:
Searching is the process to find the location of an element in a given list
of [Link] the element is found it is considered to be successful
search otherwise unsuccessful search. The search operation returns
the location of the element found.
There are two basic searches:
Linear Search (Sequential Search)
Binary Search
Unit-V 6
Linear Search:
Linear search is also called Sequential search.
In linear search, we start searching for the (key) element from the
beginning of the list and continue until we find the (key) element or until
we are sure that it is not in the list.
If the target (key) is found in the list, we say that the search is successful
otherwise the search is unsuccessful.
The time complexity of linear search to search n elements is O(n).
Unit-V 7
Linear Search:
18 23 49 57 32
0 1 2 3 4
Key=23 Search is successful and the key is found at index 1
Key=42 Search is unsuccessful
Unit-V 8
linearsearch(list[],size,k)
[Link]
2.i=0;
[Link] steps 4-6 until i < size
[Link] k == list[i] goto step 5 else goto step 6
5. return i and goto steo 9
6. i = i+1
[Link] i=size goto step 8 else goto step 9
8. return null and goto step 9
[Link]
Unit-V 9
Linear Search: Program
#include<stdio.h>
void linear(int a[ ], int n,int key);
void linear(int a[ ], int n,int key)
void main( )
{
{
int i,flag=0;
int a[20],n,i,key;
for(i=0;i<n;i++)
printf("\nEnter the no. of elements:");
{
scanf("%d",&n);
if(a[i]==key)
printf("\nEnter the elements:");
{
for(i=0;i<n;i++)
flag=1;
scanf("%d",&a[i]);
break;
printf("\nEnter the key to search:");
}
scanf("%d",&key);
}
linear(a,n,key);
if(flag==1)
}
printf("\nKey found at %d position",i+1);
else
printf("\nKey not found in the list");
}
Unit-V 10
Binary Search:
Binary search is used when the list is sorted.
The binary search starts by searching for the target (key) at the middle of
the list (array).
If the target (key) is at the middle, the search completes
Otherwise, if the target (key) is less than the value at middle, the search is
applied only to first half
Otherwise, the search is applied only to second half.
Unit-V 11
Binary Search:
First Last
0 1 2 3 4 5 6 7 8
12 18 25 32 35 39 45 48 51
Key = 39
Unit-V 12
Binary Search:
First First Last
0 1 2 3 4 5 6 7 8
12 18 25 32 35 39 45 48 51
Key = 39 Mid= ( First + Last) / 2
If ( First > Last ) Display Key not found and Exit
Mid = ( 0 + 8 ) / 2
Mid = 4
If ( Key == a[Mid] ) Display Key found at Mid position
If ( Key < a[Mid] ) Last=Mid-1
If ( Key > a[Mid] ) First=Mid+1
Unit-V 13
Binary Search: Last
First Last
0 1 2 3 4 5 6 7 8
12 18 25 32 35 39 45 48 51
Key = 39 Mid= ( First + Last) / 2
If ( First > Last ) Display Key not found and Exit
Mid = ( 5 + 8 ) / 2
Mid = 6
If ( Key == a[Mid] ) Display Key found at Mid position
If ( Key < a[Mid] ) Last=Mid-1
If ( Key > a[Mid] ) First=Mid+1
Unit-V 14
Binary Search: Last
First
0 1 2 3 4 5 6 7 8
12 18 25 32 35 39 45 48 51
Key = 39 Mid= ( First + Last) / 2
If ( First > Last ) Display Key not found and Exit
Mid = ( 5 + 5 ) / 2
Mid = 5
If ( Key == a[Mid] ) Display Key found at Mid position
If ( Key < a[Mid] ) Last=Mid-1
If ( Key > a[Mid] ) First=Mid+1
Unit-V 15
Binary Search: Example-2
120 158 196 254 287 312 354 435 468 481
If ( First > Last ) Display Key not found and Exit
If ( Key == a[Mid] ) Display Key found at Mid position
If ( Key < a[Mid] ) Last=Mid-1
If ( Key > a[Mid] ) First=Mid+1
Unit-V 16
Binarysearch(a[], size,key)
Step1 : start
Step2 : i=0,j=size,k=0
Step 3 : repeat steps 4 to 9 while i<=j
Step 4 : set k = (i+j)/2
Step 5: if (a[k] = key) goto step 6 else goto step 7
Step 6: return k and goto step 11
Step 7: if (a[k] < num) goto step 8 else goto step 9
Step 8: I = k+1
Step 9: j = k-1
Step 10 : return null and goto step 11
Step 11. stop
Step-1: If(First>Last) Display Key not found Exit Else
Goto Step-2
Step-2: Calculate Mid= (First+Last)/2
Step-3: If ( Key == a[Mid] )
Display Key found at Mid position
Exit
Else Goto Step-4
Unit-V 17
Step-4: If(Key<a[Mid]) Last=Mid-1 Goto Step-1
Else First=Mid+1 Goto Step-1
Binary Search: Non-Recursive void nrbinary(int a[ ],int key,int first,int last)
{
int mid,flag=0;
int main ( )
while(first<=last)
{
{
int a[20],n,i,key,flag=0,first,last,mid;
mid=(first+last)/2;
printf("\nEnter the no. of elements:");
if(key==a[mid])
scanf("%d",&n);
{
printf("\nEnter elements in sorted order:");
printf("\nElement found at position
for(i=0;i<n;i++)
%d",mid+1);
scanf("%d",&a[i]);
flag=1;
printf("\nEnter the element to search:");
break;
scanf("%d",&key);
}
first=0;
else if(key>a[mid])
last=n-1;
first=mid+1;
nrbinary(a,key,first,last);
else
}
last=mid-1;
}
if(flag==0)
{
printf("\nElement not found in the list");
}
Unit-V} 18
Binary Search: Recursive void rbinary(int a[],int key,int first,int last)
{
int mid;
void main() if(first>last)
{ printf("\nElement not found");
int a[20],n,i,key,flag=0,first,last,mid; else
printf("\nEnter the no. of elements:"); {
scanf("%d",&n); mid = (first + last)/2;
printf("Enter elements in sorted order:"); if(key == a[mid])
for(i=0;i<n;i++) printf("The element is at
scanf("%d",&a[i]); position
printf("\nEnter the element to search:"); %d\n",mid+1);
scanf("%d",&key); else if(key < a[mid])
first=0; {
last=n-1; last = mid - 1;
rbinary(a,key,first,last); rbinary(a,key,first,last);
} }
else
{
first = mid + 1;
rbinary(a,key,first,last);
}
Unit-V 19
}
Basis of Linear search Binary search
comparison
Definition The linear search starts It finds the position of
searching from the first the searched element by
element and compares finding the middle
each element with a element of the array.
searched element till the
element is not found.
Sorted data In a linear search, the The pre-condition for the
elements don't need to be binary search is that the
arranged in sorted order. elements must be
arranged in a sorted
order.
Approach It is based on the It is based on the divide
sequential approach. and conquer approach.
Efficiency It is less efficient in the It is more efficient in the
case of large-size data case of large-size data
sets. sets.
Worst-case In a linear search,
Unit-V the In a binary search, the 20
scenario worst- case scenario for worst-case scenario for
Sorting:
Sorting is the process through which data are arranged according to their
values in increasing or decreasing order.
Some sorting techniques:
Selection sort
Bubble sort
Insertion sort
Unit-V 21
Selection sort:
Selection sort works on the principle of identifying the smallest element in
the list and moving it to the beginning of the [Link] process is repeated
until the list is sorted.
In selection sort, the first smallest element is selected from the unsorted
array and placed at the first position. After that second smallest element
is selected and placed in the second position. The process continues
until the array is entirely sorted.
The average and worst-case complexity of selection sort is O(n2),
where n is the number of items. Due to this, it is not suitable for large
data sets.
Selection sort is generally used when -
A small array is to be sorted
Swapping cost doesn't matter
It is compulsory to check all elements
Unit-V 22
Selection sort: Example 1
23 78 45 8 32 56 Original list
8 78 45 23 32 56 After pass 1
8 23 45 78 32 56 After pass 2
8 23 32 78 45 56 After pass 3
8 23 32 45 78 56 After pass 4
8 23 32 45 56 78 After pass 5
Unit-V 23
Selection sort: Example 2
36 68 91 86 25 43 72 57 Original list
Unit-V 24
#include <stdio.h>
void main()
{
int a[20],i,,j,index,small,temp,n; temp= a[i];
printf(“\n enter the size of array”);; a[i] = a[index;
scanf(“%d”,&n); a[index] = temp;
printf(“\n enter %d elements”,n); }
for(i=0;i<n;i++) }
scanf(“%d”,&a[i]); printf(“\n sorted list is “);
printf(“\n before sorting list is”); for(i=0;i<n;i++)
for(i=0;i<n;i++) printf(“%d “,a[i]);
printf(“ %d”,a[i]); }
for(i=0;i<n-1;i++)
{ small = a[i];
index = i;
for(j=i+1;j<n;j++)
{ if (a[j] < small)
{
small = a[j];
index = j; Unit-V 25
Selection sort: Program void selection(int a[ ], int n)
{
int i,j,k,temp,small;
printf("\nOriginal list: ");
for(k=0;k<n;k++)
int main( ) printf("%d ",a[k]);
{ for(i=0;i<n-1;i++)
int a[20],n,i; {
printf("\nEnter the no. of elements:"); small=i;
scanf("%d",&n); for(j=i+1;j<n;j++)
printf("\nEnter the elements:"); {
for(i=0;i<n;i++) if(a[small]>a[j])
scanf("%d",&a[i]); small=j;
selection(a,n); }
} temp=a[small];
a[small]=a[i];
a[i]=temp;
printf("\nAfter pass %d: ",i+1);
for(k=0;k<n;k++)
printf("%d ",a[k]);
}
Unit-V } 26
[Link] selectionsort()
[Link] size
[Link] i = 0 to size-1 do
[Link] a[i]
5. end for
[Link] i = 0 to n-1 do
[Link] = a[i]
[Link] = i
[Link] j = i+1 to n-1 do
[Link] (a[j] <small)
[Link] = a[j];
[Link] = j
[Link]
[Link] = a[i]
14.a[i] = a[index]
15.a[index] = temp
[Link] for
[Link] for
[Link] i = 0 to n-1 do
[Link] (a[i])
[Link] for Unit-V 27
[Link]
Bubble sort:
the Bubble sort, focuses on bringing the largest element to end of the list
with each successive pass.
Unlike selection sort it does not perform a search to identify the largest
element instead it repeatedly compares two consecutive elements and
moves the largest amongst them to the [Link] process is repeated for
n-1 iterations.
Unit-V 28
Bubble sort: Example 1
23 78 45 8 32 56 Original list
23 78 8 45 32 56
23 8 78 45 32 56
8 23 78 45 32 56 After pass 1
8 23 32 78 45 56 After pass 2
8 23 32 45 78 56 After pass 3
8 23 32 45 56 78 After pass 4
8 23 32 45 56 78 After pass 5
Unit-V 29
Bubble sort: Example 2
36 68 91 86 25 43 72 57 Original list
Unit-V 30
#include <stdio.h>
void main()
{
int a[20],i,j,temp,n;
printf(“\n enter the size of array”);; printf(“\n after sorting list is”);
scanf(“%d”,&n); for(i=0;i<n;i++)
printf(“\n enter %d elements”,n); printf(“ %d”,a[i]);
for(i=0;i<n;i++) }
scanf(“%d”,&a[i]);
printf(“\n before sorting list is”);
for(i=0;i<n;i++)
printf(“ %d”,a[i]);
for(i=0;i<n-1;i++)
{
for(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;
}
} Unit-V 31
}
Bubble sort: Program void bubble(int a[ ], int n)
{
int i,j,k,temp;
printf("\nOriginal list: ");
int main( ) for(k=0;k<n;k++)
{ printf("%d ",a[k]);
int a[20],n,i; for(i=0;i<n-1;i++)
printf("\nEnter the no. of elements:"); {
scanf("%d",&n); for(j=0;j<n-i-1;j--)
printf("\nEnter the elements:"); {
for(i=0;i<n;i++) if(a[ j ]<a[ j+1 ])
scanf("%d",&a[i]); {
bubble(a,n); temp=a[ j ];
} a[ j ]=a[ j+1 ];
a[ j+1 ]=temp;
}
}
printf("\nAfter pass %d: ",i+1);
for(k=0;k<n;k++)
printf("%d ",a[k]);
}
}
Unit-V 32
Algorithm for Bubble sort
Bubblesort(a[],n)
[Link]
[Link] i = 0 to n-1 do
[Link] j = 0 to n-i-1 do
4. if (a[j] < a[j|+1])
[Link] = a[j]
6.a[j] = a[j+1]
7.a[j+1] = temp
[Link] if
[Link] for
[Link] for
[Link] i = 0 to n-1 do
[Link](a[i])
[Link]
Unit-V 33
Insertion sort:
Insertion sort works similar to the sorting of playing cards in hands. It is
assumed that the first card is already sorted in the card game, and then we
select an unsorted card. If the selected unsorted card is greater than the
first card, it will be placed at the right side; otherwise, it will be placed at the
left side. Similarly, all unsorted cards are taken and put in their exact place.
The same approach is applied in insertion sort. The idea behind the
insertion sort is that first take one element, iterate it through the sorted
array.
Insertion sort method sorts a list of elements by inserting each successive
element in the previously sorted sublist.
Unit-V 34
Insertion sort: Example 1
23 78 45 8 32 56 Original list
23 78 45 8 32 56 After pass 1
23 45 78 8 32 56 After pass 2
8 23 45 78 32 56 After pass 3
8 23 32 45 78 56 After pass 4
8 23 32 45 56 78 After pass 5
Unit-V 35
Insertion sort: Example 2
36 68 91 86 25 43 72 57 Original list
Unit-V 36
void insertion(int a[ ], int n)
Insertion sort: Program {
int i,j,k,temp;
printf("\nOriginal list: ");
for(k=0;k<n;k++)
int main( ) printf("%d ",a[k]);
{ for(i=1;i<n;i++)
int a[20],n,i; {
printf("\nEnter the no. of elements:"); for(j=i;j>0;j--)
scanf("%d",&n); {
printf("\nEnter the elements:"); if(a[j]<a[j-1])
for(i=0;i<n;i++) {
scanf("%d",&a[i]); temp=a[j];
insertion(a,n); a[j]=a[j-1];
} a[j-1]=temp;
}
else
break;
}
printf("\nAfter pass %d: ",i);
for(k=0;k<n;k++)
printf("%d ",a[k]);
Unit-V } 37
}
Algorithm for Insertion Sort
Insertionsort(a[],n)
[Link]
[Link] i = 1 to n-1 do
[Link] j = i downto 0 do
[Link] (a[j] < a[j-1])
[Link] = a[j]
6.a[j] = a[j-1]
7.a[j-1] = temp
else
[Link]
[Link]
[Link] for
[Link] for
[Link] i = 0 to n-1 do
[Link] (a[i])
[Link]
Unit-V 38
Comparision:
Selection Bubble Insertion
23 78 45 8 32 56 23 78 45 8 32 56 23 78 45 8 32 56
Original
8 78 45 23 32 56 8 23 78 45 32 56 23 78 45 8 32 56 Pass 1
8 23 45 78 32 56 8 23 32 78 45 56 23 45 78 8 32 56 Pass 2
8 23 32 78 45 56 8 23 32 45 78 56 8 23 45 78 32 56 Pass 3
8 23 32 45 78 56 8 23 32 45 56 78 8 23 32 45 78 56 Pass 4
8 23 32 45 56 78 8 23 32 45 56 78 8 23 32 45 56 78 Pass 5
Unit-V 39
Complexity of Algorithm (Running time)
It is the amount of time a program or algorithm takes for
execution.
The standard methods of computing time complexity of an
algorithms is Step count and asymptotic
notation(mathematical analysis)
Unit-V 40
Asymptotic Notation
It is the mathematical notation used to describe the running time of an
algorithm.
It describes the time complexity in three common measures Best case,
Average case and Worst case.
The three important asymptotic notations are
[Link]-Oh Notation Worst case time complexity
[Link] Notation Best case time complexity
[Link] Notation Average case time complexity
Some of typical complexities of Big oh are
O(1) constant
O(n) linear
O(n^2) quadratic
O(n^3) cubic
O(2^n) exponential
O(logn) logarithmic
O(1) <= O(logn) <= O(nlogn) <= Unit-V O(n^2) <= O(n^3) <= O(2^n) 41
Example 1
1.A()
2.{
[Link] i;
[Link] (i=1 to n)
[Link]("Edward");
6.}
Since i equals 1 to n, so the above program will print Edward, n
number of times.
Thus, the complexity will be O(n).
Example 2
1.A()
2.{
[Link] i, j:
[Link] (i=1 to n)
[Link] (j=1 to n)
[Link]("Edward");
7.}
In this case, firstly, the outer Unit-V
loop will run n times, such that42
for each time, the inner loop will also run n times. Thus, the
Example 4
Algorithm sum(a[],n)
[Link]
[Link] = 0 1
[Link] i = 1 to n do n+1
[Link] = sum + a[i] n
[Link] for
[Link] sum 1
[Link]
2n+3 = O(n)
Example 5
Algorithm Add (A,B,C,m.n)
For I = 1 to m do m+1
For j = 1 to n do mn+m
C[i][j] = a[i][j] + b[i][j] mn
End for
End for Unit-V 2mn+2m+1 43
Thank You
UNIT-V 44