Unit 2: Iterative Algorithms
Sr. Lec. Sujan Shrestha
9801104103
shrestha.sujan1400@[Link]
•CONTENTS
• 2.1. Basic Algorithms: Algorithm for GCD, Fibonacci Number and analysis of
their time and space complexity
• 2.2. Searching Algorithms: Sequential Search and its analysis
• 2.3. Sorting Algorithms: Bubble, Selection, and Insertion Sort and their
Analysis
Basic Algorithms
• GCD
• Fibonacci
GCD analysis
12 33 25 150
1,2,3,5,6,10,15,
Divisors 1,2,3,4,6,12 1,3,11,33 Divisors 1,5,25
25,30,50,75,150
Common Common
1,3 1,5,25
divisors divisors
Greatest Greatest
Common 3 Common 25
Divisor Divisor
GCD analysis
• Euclidean algorithm or Euclid’s algorithm
2
Q A B R
12) 33 (
2 33 12 9 24
1 12 9 3
9
3 9 3 0
X 3 0 X
GCD analysis
• GCD(A,B): • Find the GCD of (50,12).
•{ • Solution:
• If (A = 0)
• Print “B as GCD” • Here a = 50, b = 12
• elseif (B = 0) • GCD(a,b) = GCD(b, a mod b)
• Print “A as GCD”;
• GCD(50,12) = GCD(12,50 mod 12) = GCD(12, 2)
• else
• { • GCD(12,2) = GCD(2,12 mod 2) = GCD(2,0) = 2
• While(B!=0)
• {
• R=A%B
• A=B • Analysis
• B=R
• } • Since while loop executes at most n times if n
• Print “ A as GCD” be the size of element B. Then their time
complexity is,
•}
• T(n) = O(n)
Fibonacci analysis • Start
• Fibonacci numbers form a sequence such • Set first = 0, second = 1
that each number is the sum of two • Read term of Fibonacci number say t be n
preceding ones, starting from 0 and 1. • Set i=3
• Fn = Fn-1 +Fn-2 • While(i<=n)
• Set temp = first + second
• Set first = second
• Set second = temp
• 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …… • Increment i by 1 as i++
• Print temp as required Fibonacci number
• Stop
• Analysis
• Since while loop executes at most n times so its
complexity is
• T(n) = O(n)
Unit 2: Iterative Algorithms
Sr. Lec. Sujan Shrestha
9801104103
shrestha.sujan1400@[Link]
Linear Search
• Suppose, you are given a jar containing some business cards.
• You are asked to determine whether the name “Bill Gates" is in the
jar.
• To do this, you decide to simply go through all the cards one by one.
• How long this takes?
• Can be determined by how many cards are in the jar, i.e., Size of
Input.
• Linear search is a method for finding a particular value from the
given list.
• The algorithm checks each element, one at a time and in sequence,
until the desired element is found.
• Linear search is the simplest search algorithm.
• It is a special case of brute-force search.
Linear Search – Example
Search for 𝟏 in given array 𝟐 𝟗 𝟑 𝟏 𝟖
Comparing value of ith index with the given element one by one, until we get the required
element or end of the array
Step 1: i=1 Step 3: i=3
𝟐 𝟗 𝟑 𝟏 𝟖 𝟐 𝟗 𝟑 𝟏 𝟖
i i
𝟐≠𝟏 𝟑≠𝟏
Step 2: i=2 Step 4: i=4
𝟐 𝟗 𝟑 𝟏 𝟖 𝟐 𝟗 𝟑 𝟏 𝟖
i i
𝟗≠𝟏 Element found at ith index, i=4
Linear Search - Algorithm
# Input : Array A, element x
# Output : First index of element x in A or -1 if not found
Algorithm: Linear_Search
for i = 1 to last index of A
if A[i] equals element x
return i
return -1
Linear Search - Analysis
The required element in the given array can be found at,
1. E.g. 2: It is at the first position
Best Case: minimum comparison is required
2. E.g. 3 or 1: Anywhere after the first position
Average Case: average number of comparison is required
3. E.g. 7: Last position or element does not found at all
Worst Case: maximum comparison is required
Worst Case
Search for 𝟐𝟕𝟑 𝟐 𝟗 𝟑 𝟏 𝟖 𝟕
Best Case
Average Case
Linear Search - Analysis
• The required element in the given array can be found at,
Case 1: element 2 which is Case 2: element 3 anywhere Case 3: element 7 at last
at the first position so after the first position so, an position or element does not
minimum comparison is average number of found at all, maximum
required comparison is required comparison is required
Best Case Average Case Worst Case
Worst Case
Search for 𝟐𝟕𝟑 𝟐 𝟗 𝟑 𝟏 𝟖 𝟕
𝑶(𝒏)
Best Case
Average Case
Unit 2: Iterative Algorithms
Sr. Lec. Sujan Shrestha
9801104103
shrestha.sujan1400@[Link]
Sorting Algorithms
• Bubble Sort, Selection Sort, Insertion Sort
Introduction
• Sorting is any process of arranging items systematically or arranging items in a
sequence ordered by some criterion.
• Applications of Sorting
1. Phone Bill: the calls made are date wise sorted.
2. Bank statement or Credit card Bill: transactions made are date wise sorted.
3. Filling forms online: “select country” drop down box will have the name of countries
sorted in Alphabetical order.
4. Online shopping: the items can be sorted price wise, date wise or relevance wise.
5. Files or folders on your desktop are sorted date wise.
Bubble Sort – Example
Sort the following array in Ascending order
45 34 56 23 12
Pass 1 :
34
45 swap 34 34 34
34
45 45 45 45
56 56 56
23 23
swap
23 23 23
56 56
12
swap
12 12 12 12
56
𝑖𝑓(𝐴[𝑗] > 𝐴[𝑗 + 1])
𝑠𝑤𝑎𝑝(𝐴[𝑗], 𝐴[𝑗 + 1])
Bubble Sort – Example
Pass 2 : Pass 3 : Pass 4 :
34 34 34 23
34 23 12
23
swap
swap
45 45
23 23 23
34 34
12 12
23
swap
swap
23 23
45 45
12 12 12
34 34
swap
12 12 12
45 45 45 45
56 56 56 56 56 56
𝑖𝑓(𝐴[𝑗] > 𝐴[𝑗 + 1])
𝑠𝑤𝑎𝑝(𝐴[𝑗], 𝐴[𝑗 + 1])
Bubble Sort - Algorithm
# Input: Array A
# Output: Sorted array A
O 𝐧
Algorithm: Bubble_Sort(A)
for i ← 1 to n-1 do
for j ← 1 to n-i do
if A[j] > A[j+1] then
temp ← A[j]
swap(A[j], A[j+1])
A[j] ← A[j+1] O 𝐧𝟐
A[j+1] ← temp
Bubble Sort
• It is a simple sorting algorithm that works by comparing each pair of adjacent
items and swapping them if they are in the wrong order.
• The pass through the list is repeated until no swaps are needed, which indicates
that the list is sorted.
• As it only uses comparisons to operate on elements, it is a comparison sort.
• Although the algorithm is simple, it is too slow for practical use.
• The time complexity of bubble sort is O 𝒏𝟐
Bubble Sort Algorithm – Best Case Analysis
# Input: Array A Pass 1 : i = 1
# Output: Sorted array A
12 j = 1
Algorithm: Bubble_Sort(A) 23 j = 2
int flag=1; 34 j = 3
Condition never
for i ← 1 to n-1 do 45 j = 4
becomes true
for j ← 1 to n-i do 59
if A[j] > A[j+1] then Best case time
complexity = O 𝑛
flag = 0;
swap(A[j],A[j+1])
if(flag == 1)
cout<<"already sorted"<<endl
break;
Bubble Sort analysis
• In pass 1: n-1 comparisons are required
• In pass 2: n-2 comparisons are required
• In pass 3: n-3 comparisons are required
• ………………
• ………………
• In pass n-1: 1 comparisons are required
• Total comparisons: T(n) = (n-1) + (n-2) + (n-3) + …………… +1
• = n(n-1)/2
• = O(n2)
Selection Sort – Example 1
Sort the following elements in Ascending order
5 1 12 -5 16 2 12 14
Step 1 :
Unsorted Array
5 1 12 -5 16 2 12 14
1 2 3 4 5 6 7 8
Step 2 :
Minj denotes the current index and Minx is the value
Unsorted Array (elements 2 to 8) stored at current index.
So, Minj = 1, Minx = 5
-5
5 1 12 -5
5 16 2 12 14 Assume that currently Minx is the smallest value.
Now find the smallest value from the remaining entire
1 2 3 4 5 6 7 8
Unsorted array.
Swap Index = 4, value = -5
Selection Sort – Example 1
Step 3 :
Unsorted Array (elements 3 to 8) Now Minj = 2, Minx = 1
Find min value from remaining
-5 1 12 5 16 2 12 14 unsorted array
1 2 3 4 5 6 7 8
Index = 2, value = 1
No Swapping as min value is already at right place
Step 4 :
Unsorted Array Minj = 3, Minx = 12
(elements 4 to 8) Find min value from remaining
unsorted array
-5 1 12
2 5 16 12
2 12 14 Index = 6, value = 2
1 2 3 4 5 6 7 8
Swap
Selection Sort – Example 1
Step 5 : Unsorted Array
Now Minj = 4, Minx = 5
(elements 5 to 8)
Find min value from remaining
unsorted array
-5 1 2 5 16 12 12 14
1 2 3 4 5 6 7 8 Index = 4, value = 5
No Swapping as min value is already at right place
Step 6 :
Minj = 5, Minx = 16
Find min value from remaining
Unsorted Array unsorted array
(elements 6 to 8)
Index = 6, value = 12
-5 1 2 5 12
16 16
12 12 14
1 2 3 4 5 6 7 8
Swap
Selection Sort – Example 1
Step 7 :
Unsorted Array Now Minj = 6, Minx = 16
(elements 7 to 8) Find min value from remaining
unsorted array
-5 1 2 5 12 12
16 16
12 14
1 2 3 4 5 6 7 8 Index = 7, value = 12
Swap
Step 8 :
Unsorted Array Minj = 7, Minx = 16
(element 8) Find min value from remaining
unsorted array
-5 1 2 5 12 12 14
16 16
14
Index = 8, value = 14
1 2 3 4 5 6 7 8
Swap The entire array is sorted now.
Selection Sort
• Selection sort divides the array or list into two parts,
1. The sorted part at the left end
2. and the unsorted part at the right end.
• Initially, the sorted part is empty and the unsorted part is the entire list.
• The smallest element is selected from the unsorted array and swapped with the
leftmost element, and that element becomes a part of the sorted array.
• Then it finds the second smallest element and exchanges it with the element in
the second leftmost position.
• This process continues until the entire array is sorted.
• The time complexity of selection sort is O 𝒏𝟐
Selection Sort - Algorithm
# Input: Array A
# Output: Sorted array A
Algorithm: Selection_Sort(A)
for i ← 1 to n-1 do 𝐎 𝐧
minj ← i;
minx ← A[i];
for j ← i + 1 to n do
if A[j] < minx then
𝐎 𝐧 𝟐
minj ← j;
minx ← A[j];
A[minj] ← A[i];
A[i] ← minx;
Selection Sort – Example 2
Algorithm: Selection_Sort(A)
Pass 1 :
for i ← 1 to n-1 do
minj ← i; minx ← A[i]; i = 1
for j ← i + 1 to n do minj ← 12
if A[j] < minx then
34
minx ← 45 No Change
minj ← j ; minx ← A[j];
A[minj] ← A[i]; j = 2 3
A[i] ← minx; A[j] = 34
56
Sort in Ascending order
45 34 56 23 12
1 2 3 4 5
Selection Sort – Example 2
Algorithm: Selection_Sort(A)
Pass 1 :
for i ← 1 to n-1 do
minj ← i; minx ← A[i]; i = 1
for j ← i + 1 to n do 4
minj ← 2
5
if A[j] < minx then
minx ← 34
23
12
minj ← j ; minx ← A[j];
A[minj] ← A[i]; j = 2 3 4 5
A[i] ← minx; A[j] = 12
23
Sort in Ascending order Unsorted Array
45 34 56 23 12 45
12 34 56 23 45
12
1 2 3 4 5 1 2 3 4 5
Swap
45
12 23
34 34
56 34
45
23
56 45
56
Selection Sort analysis
• In pass 1: n-1 comparisons are required
• In pass 2: n-2 comparisons are required
• In pass 3: n-3 comparisons are required
• ………………
• ………………
• In pass n-1: 1 comparisons are required
• Total comparisons: T(n) = (n-1) + (n-2) + (n-3) + …………… +1
• = n(n-1)/2
• = O(n2)
• There is no best-case linear time complexity for this algorithm, but number of
swap operation is reduced greatly.
Insertion Sort – Example
Sort the following elements in Ascending order
5 1 12 -5 16 2 12 14
Step 1 :
Unsorted Array
5 1 12 -5 16 2 12 14
1 2 3 4 5 6 7 8
Step 2 :
𝒋
𝒊 = 𝟐, 𝒙 = 𝟏 𝒋 = 𝒊 – 𝟏 𝒂𝒏𝒅 𝒋 > 𝟎
51 1 12 -5 16 2 12 14 while 𝑥 < 𝑇 𝑗 do
1 2 3 4 5 6 7 8 𝑇 𝑗+1 ←𝑇 𝑗
𝑗−−
Shift down
Insertion Sort – Example
Step 3 :
𝒋
𝒊 = 𝟑, 𝒙 = 𝟏𝟐 𝒋 = 𝒊 – 𝟏 𝒂𝒏𝒅 𝒋 > 𝟎
1 5 12 -5 16 2 12 14 while 𝑥 < 𝑇 𝑗 do
1 2 3 4 5 6 7 8 𝑇 𝑗+1 ←𝑇 𝑗
𝑗−−
No Shift will take place
Step 4 :
𝒊 = 𝟒, 𝒙 = −𝟓 𝒋 = 𝒊 – 𝟏 𝒂𝒏𝒅 𝒋 > 𝟎
𝒋
while 𝑥 < 𝑇 𝑗 do
𝒋
𝑇 𝑗+1 ←𝑇 𝑗
-5
1 5 12 -5 16 2 12 14 𝑗−−
1 2 3 4 5 6 7 8
Shift down
Shift down
Shift down
Insertion Sort – Example
Step 5 :
𝒋
𝒊 = 𝟓, 𝒙 = 𝟏𝟔 𝒋 = 𝒊 – 𝟏 𝒂𝒏𝒅 𝒋 > 𝟎
-5 1 5 12 16 2 12 14 while 𝑥 < 𝑇 𝑗 do
1 2 3 4 5 6 7 8 𝑇 𝑗+1 ←𝑇 𝑗
𝑗−−
No Shift will take place
Step 6 :
𝒊 = 𝟔, 𝒙 = 𝟐 𝒋 = 𝒊 – 𝟏 𝒂𝒏𝒅 𝒋 > 𝟎
𝒋 𝒋 while 𝑥 < 𝑇 𝑗 do
𝑇 𝑗+1 ←𝑇 𝑗
-5 1 52 12 16 2 12 14 𝑗−−
1 2 3 4 5 6 7 8
Shift down Shift down
Shift down
Insertion Sort – Example
Step 7 :
𝒋
𝒊 = 𝟕, 𝒙 = 𝟏𝟐 𝒋 = 𝒊 – 𝟏 𝒂𝒏𝒅 𝒋 > 𝟎
-5 1 2 12 12 14
5 12 16 while 𝑥 < 𝑇 𝑗 do
1 2 3 4 5 6 7 8 𝑇 𝑗+1 ←𝑇 𝑗
𝑗−−
Shift down
Step 8 :
𝒊 = 𝟖, 𝒙 = 𝟏𝟒 𝒋 = 𝒊 – 𝟏 𝒂𝒏𝒅 𝒋 > 𝟎
𝒋 while 𝑥 < 𝑇 𝑗 do
𝑇 𝑗+1 ←𝑇 𝑗
-5 1 2 5 12 12 14
16 14 𝑗−−
1 2 3 4 5 6 7 8
Shift down The entire array is sorted now.
Insertion Sort - Algorithm
# Input: Array T
# Output: Sorted array T
Algorithm: Insertion_Sort(T[1,…,n])
for i ← 2 to n do
𝐎 𝐧
x ← T[i];
j ← i – 1;
while x < T[j] and j > 0 do
T[j+1] ← T[j];
j ← j – 1; 𝐎 𝐧𝟐
T[j+1] ← x;
Insertion Sort Algorithm – Best Case Analysis
# Input: Array T Pass 1 :
# Output: Sorted array T
12
23 i=2 x=23 T[j]=12
Algorithm: Insertion_Sort(T[1,…,n])
34 i=3 x=34 T[j]=23
for i ← 2 to n do 45 i=4 x=45 T[j]=34
O 𝐧
x ← T[i];
59 i=5 x=59 T[j]=45
j ← i – 1;
while x < T[j] and j > 0 do The best case time complexity of
T[j+1] ← T[j]; Insertion sort is 𝑶 𝒏
j ← j – 1; The average and worst case time
T[j+1] ← x; complexity of Insertion sort is 𝑶 𝒏𝟐
• Design and Analysis of Algorithms(DAA)
THANK YOU
Sr. Lec. Sujan Shrestha
9801104103
shrestha.sujan1400@[Link]