Decrease and Conquer
Three major variations of decrease and
conquer
• Decrease by a Constant
• Decrease by a Constant factor
• Variable size Decrease
Topics Cover
• Insertion Sort
• Binary Search
• Topological Sorting
Insertion Sort -
Already covered
6
Insertion Sort
• Suppose we know how to insert a new element x in its proper place
in an already sorted array A of size k, to get a new sorted array of
size k+1
• Use this to sort the given array A of size n as follows:
• Insert A[1] in the sorted array A[0]. So now A[0],A[1] are sorted
• Insert A[2] in the sorted array A[0],A[1]. So now A[0],A[1],A[2]
are sorted
• Insert A[3] in the sorted array A[0],A[1],A[2]. So now
A[0],A[1],A[2],A[3] are sorted
• …..
• Insert A[i] in the sorted array A[0],A[1],…,A[i-1]. So now
A[0],A[1],…A[i] are sorted
• Continue until i = n-1 (outer loop)
7
Example of first step
A 5 7 11 13 20 22 Insert x = 15
8
Example of first step
A 5 7 11 13 20 22 Insert x = 15
Compare with 22. x < 22, so move 22 right
5 7 11 13 20 15 22
9
Example of first step
A 5 7 11 13 20 22 Insert x = 15
Compare with 22. x < 22, so move 22 right
5 7 11 13 20 15 22
Compare with 20. x < 20, so move 20 right
5 7 11 13 15 20 22
10
Example of step: Inserting an element
in to sorted array
A 5 7 11 13 20 22 Insert x = 15
Compare with 22. x < 22, so move 22 right
5 7 11 13 20 15 22
Compare with 20. x < 20, so move 20 right
5 7 11 13 15 20 22
Compare with 13. x > 13, so stop
A 5 7 11 13 15 20 22
11
Sort using the insertion sort
A 7 5 13 11 22 20
Insert 5 in 7
5 7 13 11 22 20 Insert 20 in 5, 7, 11, 13, 22
Insert 13 in 5, 7
5 7 11 13 20 22
5 7 13 11 22 20
Insert 11 in 5, 7, 13
5 7 11 13 22 20
Insert 22 in 5, 7, 11, 13
5 7 11 13 22 20
12
Insertion Sort Code
void InsertionSort (int A[ ], int n)
{
int i, j, item;
for (i=1; i<n; i++)
{ /* Insert the element in A[i] */
item = A[i] ;
for (j = i-1; j >= 0; j--)
if (item < A[j])
{ /* push elements down*/
A[j+1] = A[j];
A[j] = item ; /* can do this once finally also */
}
else break; /*inserted, exit loop */
}
} Time Complexity O(n2) 13
Insertion Sort Code
void InsertionSort (int A[ ], int n) Steps
{
int i, j, item; 1
for (i=1; i<n; i++) n
{ /* Insert the element in A[i] */
item = A[i] ; n–1
for (j = i-1; j >= 0; j--) ∑1(n-1)(i+1)=[n(n+1)/2]-1
if (item < A[j]) ∑1(n-1)i = (n-1)n/2
{ /* push elements down*/
A[j+1] = A[j]; (n-1)n/2
A[j] = item ; (n-1)n/2
}
else break; /*inserted, exit loop */
}
} Time Complexity O(n2) 14
Insertion Sort Analysis
Time Efficiency C(n):
• Worst Case Cworst(n) = θ (n2)
• Average Case Cavg(n) = θ (n2)
• Best Case Cbest(n) = n-1 = θ (n) (also fast on almost sorted arrays)
Binary Search
17
Binary Search
•Binary search. Given value and sorted array a[], find index i
such that a[i] = value, or report that no such index exists.
•Invariant. Algorithm maintains a[lo] value a[hi]
•Ex. Binary search for 33.
6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
lo hi
Binary Search
•Ex. Binary search for 33.
6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
lo mid hi
Binary Search
6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
lo hi
Binary Search
6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
lo mid hi
Binary Search
6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
lo hi
Binary Search
6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
lo mid hi
Binary Search
6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
lo
hi
Binary Search
6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
lo
hi
mid
Binary Search
6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
lo
hi
mid
Binary Search Algorithm
ALGORITHM BinarySearch(A[0..n − 1], K)
//Implements nonrecursive binary search
//Input: An array A[0..n − 1] sorted in ascending order and
// a search key K
//Output: An index of the array’s element that is equal to K
// or −1 if there is no such element
l←0; r ←n − 1
while l ≤ r do
m←(l + r)/2
if K = A[m] return m
else if K < A[m] r ← m − 1
else l ← m + 1
return −1
Binary Search
int binarySearch(int a[], int n, const int x, int l, int r)
{
if(l > r) return -1; // x not found
int m = (l + r)/2;
if (x == a[m]) return m;
else if (x > a[m]) binarySearch(a, n, x, m+1, r);}
else binarySearch(a, n, x, l, m-1);
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 4 4-28
Binary Search Complexity
T(n) = T(n/2) + c , T(1) = d, where d is a constant
T(n) = T(n/2) + c = T(n/22) + 2c = ….. =T(n/2k) + kc
= kc + d (Assuming n=2k , which implies k = logn)
= O(log n)
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2nd ed., Ch. 4 4-29
Analysis of Binary Search
• This is VERY fast: e.g., T(260) = 60
• Sequential search will take O (260)
• Optimal for searching a sorted array
• Limitations: must be a sorted array
Topological Sort
31
Topological Sort
• Topological sort can only be applied to Directed Acyclic Graphs (DAGs). A
DAG is a graph that has directed edges with no cycles.
• If the digraph contains cycles, it is not possible to find a valid topological
ordering.
• Topological sorting is commonly used in various applications, such as task
scheduling, dependency resolution, and in finding a linear order of events in a
system.
Topological Sort Algorithm #2
1.Store each vertex’s In-Degree in an array
2.Initialize a queue with all in-degree zero vertices
3.Whilethere are vertices remaining in the queue:
➭ Dequeue and output a vertex
➭ Reduce In-Degree of all vertices adjacent to it by 1
➭ Enqueue any of these vertices whose In-Degree
became zero
B
C
F
A
D E
Sort this digraph!
R. Rao, CSE 326
Topological Sort Algorithm: Analysis
Topological Sort DFS Method
• Step 1: Create a temporary stack.
• Step 2: Recursively call topological sorting for all its
adjacent vertices, then push it to the stack (when all
adjacent vertices are on stack). Note this step is same
as Depth First Search in a recursive way.
• Step 3: Finally, print the contents of stack.
• Note: A vertex is pushed to stack only when all of its adjacent
vertices (and their adjacent vertices and so on) are already in
stack.
Source:Topological Sorting using Depth First Search (DFS) (opengenus.org)
Problem
