UNIT-III
Merge Sort
To sort an array A[l . . r]:
• Divide
– Divide the n-element sequence to be sorted into two subsequences of n/2 elements
each
• Conquer
– Sort the subsequences recursively using merge sort. When the size of the
sequences is 1 there is nothing more to do
• Combine
– Merge the two sorted subsequences
Divide
Merging:
MergeSort(A, l, r)
{
If ( l < r)
{ //Check for base case
m = (l + r)/2 //Divide
MergeSort(A, l, m) //Conquer
MergeSort(A, m + 1, r) //Conquer
Merge(A, l, m+1, r) //Combine
}
}
Merge(A,B,l,m,r)
{
x=l, y=m;
k=l;
while(x<m && y<r)
{
if(A[x] < A[y])
{
B[k]= A[x];
k++; x++;
}
else
{
B[k] = A[y]; k+
+; y++;
}
}
while(x<m)
{
A[k] = A[x];
k++; x++;
}
while(y<r)
{
A[k] = A[y];
k++; y++;
}
for(i=l;i<= r; i++)
{
A[i] = B[i]
}
}
Time Complexity:
Recurrence Relation for Merge sort:
T(n) = 1 if n=1
T(n) = 2 T(n/2) + O(n) if n>1
Solving this recurrence we get
Time Complexity = O(nlogn)
Space Complexity:
It uses one extra array and some extra variables during sorting, therefore
Space Complexity= 2n + c = O(n)
Quick Sort
• Divide
Partition the array A[l…r] into 2 subarrays A[l..m] and A[m+1..r], such that each element
of A[l..m] is smaller than or equal to each element in A[m+1..r]. Need to find index p to
partition the array.
• Conquer
Recursively sort A[p..q] and A[q+1..r] using Quicksort
• Combine
Trivial: the arrays are sorted in place. No additional work is required to combine them.
5 3 2 6 4 1 3 7
x Y
5 3 2 6 4 1 3 7
x y {swap x & y}
5 3 2 3 4 1 6 7
y x {swap y and pivot}
1 3 2 3 4 5 6 7
p
Algorithm:
QuickSort(A,l,r)
{
if(l<r)
{
p = Partition(A,l,r);
QuickSort(A,l,p-1);
QuickSort(A,p+1,r);
}
}
Design And Analysis of Algorithms [Link]. CSIT
Partition(A,l,r)
{
x =l; y =r ; p = A[l];
while(x<y)
{
do {
x++;
}while(A[x] <= p);
do {
y--;
} while(A[y] >=p);
if(x<y)
swap(A[x],A[y]);
}
A[l] = A[y]; A[y] = p; return y; //return position of pivot
}
Time Complexity:
We can notice that complexity of partitioning is O(n) because outer while loop executes
cn times.
Thus recurrence relation for quick sort is:
T(n) = T(k) + T(n-k-1) + O(n)
Best Case:
Divides the array into two partitions of equal size, therefore
T(n) = T(n/2) + O(n) , Solving this recurrence we get,
Time Complexity = O(nlogn)
When array is already sorted or sorted in reverse order, one partition contains n-1 items
and another contains zero items, therefore
T(n) = T(n-1) + O(1), Solving this recurrence we get
Time Complexity = O(n2)
Case between worst and best:
9-to-1 partitions split
T(n) = T(n=9n/10) + T(n/10) + O(n), Solving this recurrence we get
Time Complexity = O(nolgn)
Average case:
All permutations of the input numbers are equally likely. On a random
input array, we will have a mix of well balanced and unbalanced splits.
Good and bad splits are randomly distributed across throughout the tree
Suppose we are alternate: Balanced,
Unbalanced,Balanced, …. B(n)= 2UB(n/2) +
Θ(n) Balanced
UB(n)= B(n –1) + Θ(n)
Unbalanced Solving:
B(n)= 2(B(n/2 –1) + Θ(n/2)) + Θ(n)
= 2B(n/2 –1) + Θ(n)
= Θ(nlogn)
Max and Min Finding
Here our problem is to find the minimum and maximum items in a set of n elements. We
will
see two methods here first one is iterative version and the next one uses
divide and conquer strategy to solve the problem.
Iterati
ve
Algorit
hm:
MinMa
x(A,n)
{
ma
x
=
mi
n
=
A[
0];
for
(i
=
1;
i<
n;
i+
+)
{
if(A[i] > max)
max = A[i];
if(A[i] < min)
min = A[i];
}
}
The above algorithm requires 2(n-1) comparison in worst, best, and average
cases. The comparison A[i] < min is needed only when A[i] > max is not true. If
we replace the content inside the for loop by
if(A[i] > max)
max = A[i];
else
if(A
[i] <
min
)
min
=
A[i]
;
Then the best case occurs when the elements are in increasing order with (n-1)
comparisons and worst case occurs when elements are in decreasing order with
2(n-1) comparisons. For the average case A[i] > max is about half of the time so
number of comparisons is 3n/2 – 1.
We can clearly conclude that the time complexity is O(n).
Divide and Conquer Algorithm:
Main idea behind the algorithm is: if the number of elements is 1 or 2 then
max and min are obtained trivially. Otherwise split problem into approximately
equal part and solved recursively.
MinMax(l,r)
{
if(l = = r)
max
=
min
=
A[l]
;
else
if(l
= r-
1)
{
if(A[l] < A[r])
{
max = A[r]; min = A[l];
}
else
{
max = A[l]; min = A[r];
}
}
else
{
//Divide the problems
mid = (l + r)/2; //integer division
//solve the subproblems
{min,max}=MinMax(l,mid);
{min1,max1}= MinMax(mid +1,r);
//Combine
the solutions
if(max1 >
max) max =
max1;
if(min1 <
min) min =
min1;
}
}
Analysis:
We can give recurrence relation as below for MinMax algorithm in terms of
number of comparisons.
T(n) = 2T( n /
2 ) + 1 , if n>2
T(n) = 1 , if n
≤2
Solving the recurrence by using master method complexity is (case 1) O(n).
Greedy Algorithms
In many optimization algorithms a series of selections need to be made. In
dynamic programming we saw one way to make these selections. Namely,
the optimal solution is described in a recursive manner, and then is
computed “bottom-up”. Dynamic programming is a powerful technique, but
it often leads to algorithms with higher than desired running times. Greedy
method typically leads to simpler and faster algorithms, but it is not as
powerful or as widely applicable as dynamic programming. Even when
greedy algorithms do not produce the optimal solution, they often provide
fast heuristics (non-optimal solution strategies), are often used in finding
good approximations.
To prove that a greedy algorithm is optimal we must show the following
two characteristics are exhibited.
Greedy Choice Property
Optimal Substructure Property
Statement: A thief has a bag or knapsack that can contain maximum weight
W of his loot. There are n items and the weight of i th item is wi and it worth
vi. Any amount of item can be put into the bag i.e. x i fraction of item can be
collected, where 0<=xi<=1. Here the objective is to collect the items that
maximize the total profit earned.
Take as much of the item with the highest value per weight (v i/wi) as you
can. If the item is finished then move on to next item that has highest (vi/wi),
continue this until the knapsack is full. v[1 … n] and w[1 … n] contain the
values and weights respectively of the n objects sorted in non increasing
ordered of v[i]/w[i] . W is the capacity of the knapsack, x[1 … n] is the
solution vector that includes fractional amount of items and n is the number
of items.
GreedyFracKnapsack(W,n)
{
for(i=1; i<=n; i++)
tempw -= w[i];
}
if(i<=n)
x[i] = tw/w[i];
}
Analysis:
We can see that the above algorithm just contain a single loop i.e. no nested
loops the running time for above algorithm is O(n). However our
requirement is that v[1 … n] and w[1 … n] are sorted, so we can use sorting
method to sort it in O(nlogn) time such that the complexity of the algorithm
above including sorting becomes O(nlogn).