Introduction to analysis of algorithms

Divide and Conquer Technique

Dr. Abeer Hamdy
Outline
Divide and Conquer technique

Merge Sort algorithm

Quick Sort algorithm

Selection algorithm

What Is A Divide-and-Conquer Algorithm?
Divide-and-conquer algorithms work according to the
following general plan:
1. Divide: A problems instance is divided into several
smaller instances of the same problem, ideally of
about the same size.

2. Recur: The smaller instances (sub problems) are
solved recursively,

3. Conquer: the solutions obtained for the smaller
instances are combined to get a solution to the
original problem.
Typical Divide-and-Conquer Strategy


Problem of size n
Subproblem 1 of size n/2 Subproblem 2 of size n/2
Solution to subproblem 1 Solution to subproblem 2
Solution to original problem
Brute force algorithm

Algorithm power(a,n)
result 1

for i 1 to n do
result result a

return result

O(n)

Example- Computing integer power a
n
a a a a
n
=
Divide-and-Conquer algorithm

Algorithm power(a,n)

if (n = 1)
return a
else
if n mod 2 = 0
return power(a,n/2)* power(a,n/2)
else
return power(a,n/2) * power(a,n/2) * a

Complexity is O(n) ignoring the hidden cost results from recursion

Note: We have redundant recursive calls in this example.

=
odd is n if a a a
even is n if a a
a
2
n
2
n
2
n
2
n
n
Example- Computing integer power a
n
Divide-and-Conquer algorithm

Algorithm power(a,n)

if (n = 1)
return a
else
partial = power(a,n/2);

if n mod 2 = 0
return partial* partial
else
return partial* partial * a

Complexity is O(logn) ignoring the hidden cost results from recursion

=
odd is n if a a a
even is n if a a
a
2
n
2
n
2
n
2
n
n
Example- Computing integer power a
n
keep in mind that the divide-and-conquer technique is
ideally suited for parallel computations, in which each
sub problem can be solved simultaneously by its own
processor.

The previous example illustrates the most typical case
of divide-and-conquer: a problems instance of size n is
divided into two instances of size n/2.

More generally, an instance of size n can be divided into
several instances of size n/b, with a of them needing to
be solved (a 1 and b > 1).
Divide-and-Conquer Algorithms
Merge Sort

It sorts a given array A[0..n-1] by:
Dividing it into two halves A[0.. n/2 - 1] and A[n/2
..n-1],
Recursively, sort the first half,
Recursively, sort the second half,
Merging the two smaller sorted arrays into a single
sorted one.
Merge sort is a recursive sorting algorithm. It is
based on the idea that merging two sorted lists
can be done in linear time.
Since a list that contains only one item is by
definition sorted, merge sort will break a list down
into one-element pieces and then sort as it merges
the pieces back together.
All of the work for merge sort occurs during the
merging of the two lists.
Merge Sort
Algorithm Mergesort( A[0..n-1])

//Input: An array A[0..n-1] of orderable elements
//Output: The array A[0..n-1] sorted in ascending order

if n > 1
(A
1
, A
2
) partition(A, n/2)
// copy A[0..n/2-1] to A
1
[0..n/2-1]
//copy A[n/2..n-1] to A
2
[0..n/2-1]
Mergesort(A
1
[0..n/2-1])
Mergesort(A
2
[0..n/2-1])
(A) Merge(A
1
, A
2
)
// merge (A1,A2,A)

Merge Sort Algorithm
Merge Algorithm
Merge Algorithm

Merge algorithm is a tool used in merge sort.

The merge algorithm is given two arrays B & C , each
of which is already sorted. The merge algorithm will
combine the two arrays into one larger ,A, which
contain all the values of B&C in sorted order.

three indices i,j,k (pointers) are used to point to the
current entry in the arrays A, B, C respectively.

Initially, the indices are set to the beginning of their
respective arrays.
Merge Algorithm
The merge algorithm proceeds as follows:

1. smaller of B[i], c[j] is copied to the next entry in A,
and the appropriate pointers are advanced.
2. When either input array is exhausted, the rest of
the other array is copied to A.

Merging two sorted arrays can be done in linear time.
Merge will require a total of N
c
+ N
B
1 comparisons.
Where, N
c
and N
B
are the number of elements in
array C and array B respectively .

Merge Sort Execution Tree
14 call recursive call to merge sort.
7 calls to merge

Merge Sort Execution Trace
Partition
7 2 9 4 2 4 7 9 3 8 6 1 1 3 8 6
7 2 2 7 9 4 4 9 3 8 3 8 6 1 1 6
7 7 2 2 9 9 4 4 3 3 8 8 6 6 1 1
7 2 9 4 | 3 8 6 1 1 2 3 4 6 7 8 9
Merge Sort Execution Trace (cont.)
Recursive call, partition
7 2 | 9 4 2 4 7 9 3 8 6 1 1 3 8 6
7 2 2 7 9 4 4 9 3 8 3 8 6 1 1 6
7 7 2 2 9 9 4 4 3 3 8 8 6 6 1 1
7 2 9 4 | 3 8 6 1 1 2 3 4 6 7 8 9
Merge Sort Execution Trace (cont.)
Recursive call, partition
7 2 | 9 4 2 4 7 9 3 8 6 1 1 3 8 6
7 | 2 2 7 9 4 4 9 3 8 3 8 6 1 1 6
7 7 2 2 9 9 4 4 3 3 8 8 6 6 1 1
7 2 9 4 | 3 8 6 1 1 2 3 4 6 7 8 9
Merge Sort Execution Trace (cont.)
Recursive call, base case
7 2 | 9 4 2 4 7 9 3 8 6 1 1 3 8 6
7 | 2 2 7 9 4 4 9 3 8 3 8 6 1 1 6
7 7 2 2 9 9 4 4 3 3 8 8 6 6 1 1
7 2 9 4 | 3 8 6 1 1 2 3 4 6 7 8 9
Merge Sort Execution Trace (cont.)
Recursive call, base case
7 2 | 9 4 2 4 7 9 3 8 6 1 1 3 8 6
7 | 2 2 7 9 4 4 9 3 8 3 8 6 1 1 6
7 7 2 2 9 9 4 4 3 3 8 8 6 6 1 1
7 2 9 4 | 3 8 6 1 1 2 3 4 6 7 8 9
Merge Sort Execution Trace (cont.)
Merge
7 2 | 9 4 2 4 7 9 3 8 6 1 1 3 8 6
7 | 2 2 7 9 4 4 9 3 8 3 8 6 1 1 6
7 7 2 2 9 9 4 4 3 3 8 8 6 6 1 1
7 2 9 4 | 3 8 6 1 1 2 3 4 6 7 8 9
Merge Sort Execution Trace (cont.)
Recursive call, , base case, merge
7 2 | 9 4 2 4 7 9 3 8 6 1 1 3 8 6
7 | 2 2 7 9 4 4 9 3 8 3 8 6 1 1 6
7 7 2 2 3 3 8 8 6 6 1 1
7 2 9 4 | 3 8 6 1 1 2 3 4 6 7 8 9
9 9 4 4
Merge Sort Execution Trace (cont.)
Merge
7 2 | 9 4 2 4 7 9 3 8 6 1 1 3 8 6
7 | 2 2 7 9 4 4 9 3 8 3 8 6 1 1 6
7 7 2 2 9 9 4 4 3 3 8 8 6 6 1 1
7 2 9 4 | 3 8 6 1 1 2 3 4 6 7 8 9
Merge Sort Execution Trace (cont.)
Recursive call, , merge, merge
7 2 | 9 4 2 4 7 9 3 8 6 1 1 3 6 8
7 | 2 2 7 9 4 4 9 3 8 3 8 6 1 1 6
7 7 2 2 9 9 4 4 3 3 8 8 6 6 1 1
7 2 9 4 | 3 8 6 1 1 2 3 4 6 7 8 9
Merge Sort Execution Trace (cont.)
Merge
7 2 | 9 4 2 4 7 9
3 8 6 1 1 3 6 8
7 | 2 2 7 9 4 4 9 3 8 3 8 6 1 1 6
7 7 2 2 9 9 4 4 3 3 8 8 6 6 1 1
7 2 9 4 | 3 8 6 1 1 2 3 4 6 7 8 9
How Efficient is the merge sort?
For simplicity assume that n is a power of 2. The recurrence
relation for the number of key comparisons C(n) is:

C
worst
(n) = 2C(n/2) + C
merge
(n) for n>1 , C(1)=0

In the worst case C
merge
(n) = N-1

C
worst
(n) = 2C(n/2) + N-1 for n>1

C
worst
(n) = O(nlogn)

Although merge sort is a time efficient algorithm but it ISNOT
space efficient because of extra storage the algorithm requires
to partition the arrays.
In-place merge sort
Strategy : pass through the array, merge adjacent sub-arrays of
size 1. Then, repeat for sub-arrays of size 2,4,6.

Quick Sort
Quicksort is another recursive sorting algorithm
based on divide and conquer approach.
It picks an element from the list, called the pivot
element (more on this later), and uses it to divide
the list into two parts. The first part contains all
of the elements that are smaller than the pivot
element and the second part of the list contains all
of the elements that are larger than the pivot
element.
Quicksort is a very efficient sort on average,
although its worst case performance is identical to
insertion sort and bubble sort O(n
2
).


Note: The elements in each of the two parts of the list
are not put in order.
If the pivot element ended up in location i, all we
know for certain is that elements in locations 1
through i-1 are smaller than the pivot element and
those in locations i+1 through n are larger than the
pivot element.

Once this is done, quicksort is called recursively on
each of the two parts.
Quick Sort

If quicksort is called with a list containing one
element, it does nothing (base case) because a one-
element list is sorted by default.
Because the determination of the pivot element
and the movement of the elements into the proper
section do all the work, the main quicksort
algorithm just needs to keep track of the bounds
of these two sections of the list.
All the sorting work is done on the way down in the
recursive process.
This is unlike merge sort, which does its work on the
way back up in the recursive process.
Quick Sort

Quicksort (A, lo, hi) {
// A the list of elements to be sorted
// lo the index of the first element in the list to sort
// hi the index of the last element in the list to sort.

if lo < hi {
j Partition( A, lo, hi); // returns the final index of the pivot (j)
Quicksort( A, lo, j-1);
Quicksort( A, j+1, hi);
}
}

Quick Sort Algorithm

Select a pivot.
Rearrange the list so that all the elements in the first s
positions are smaller than or equal to the pivot and all the
elements in the remaining n-s positions are larger than or equal
to the pivot.






Exchange the pivot with the last element in the first (i.e., s)
subarray (the pivot is now in its final position)
Return the index of the pivot.

p
A[i]sp
A[i]>p
Partition Agorithm Strategy

Partition Algorithm Implementation
One of the implementation for the Partition
function would be to have two indices into the list.
One scans the list left to right (i) and the other
scans the list right to left (j).

The lower index ,i, is advanced (incremented) until a
greater value than the pivot element is
encountered, and the upper index is decremented
until a value less than the pivot element is found.
When this situation occurs these two elements are
swapped. The process repeats until the two indices
cross over each other.

Move the pivot to its correct location in the list.

Partition Algorithm
Partition Algorithm Execution
What is the complexity of QuickSort?
Analysis of QuickSort is more difficult than Merge
Sort. The reason is that Merge Sort has always
recursive calls with equal sized inputs. But in Quick
Sort, each recursive call could have a different sized
set of numbers to sort. Here we should perform
three analysis:

best case : If all splits happen in the middle of the
corresponding subarrays, O(n logn)
worst case: if all the splits are skewed to the extreme (i.e.
one of the subarrays is empty) , O(n
2
)
average case : O(n logn)


Another Pivot techniques
Median of 3 or 5 pivot
Finally, since it's important to get a reasonable "split" when
doing a quicksort, it's worth going over a couple ideas that
ensure a reasonable split of values in the partition step.

One idea is to pick three elements from the array to be sorted
as candidates for the partition element (usually the rightmost,
leftmost and the middle). Then, choose the median of these
three elements to be the pivot.

There is some extra cost here ,picking three elements and then
doing three comparisons to determine the median of the values,
but hopefully, if the array being sorted is large enough, this
extra cost will be small enough compared to the gains of a
better partition element.

Another Pivot techniques
Median of 3 or 5 pivot
Also, you could pick 5 random elements and find the median of
them. then use it as the pivot.

This will generally give you a better partition element than the
median of 3 technique.

Depending on the size of the array being sorted, this extra cost
may be worth it. Clearly, you would not want to do this if you
were only sorting 10 or 20 values.


Finding the k
th
largest value in a list
Introduction:
Weve already examined the problem of searching
for a key in a list. There is a closely related
problem to this called selection.
The selection problem is similar to the searching
problem except where searching is concerned with
finding a specific target element in the list,
selection is concerned with finding an element
which has certain feature, such as the largest,
smallest, or median value.
In general, the selection problem solves the
problem of finding the k
th
largest value in a list.


Finding the k
th
largest value in a list
One way to solve the selection problem would be to
sort the list in decreasing order, and then the k
th

largest value would be in position k.

However, this is a lot more work that we really need
to do, because we dont really care about the values
that are smaller than the one we want.





Finding the k
th
largest value in a list
A related technique would be to find the largest
value and then move it to the last location in the
list. If we again look for the largest value in the
list ignoring the value we already found, we get the
second largest value, which can be moved to the
next to the last location in the list. This process
would repeat until we had found the k
th
largest
value which would occur on the k
th
pass.

The algorithm for this is shown on the next page.

Finding the k
th
largest value in a list



FindKthLargest (list, n, k)
// list the list of elements to look through
// n the number of elements in the list
// k the element to select

for (i = 1; i <= k, i++) {
largest = list[1];
largestLocation = 1;
for ( j = 2, j <= n-(i-1); j++){
if listpj[ > largest then {
largest = list[j];
largestLocation = j;
}
}
swap( list[n-(i-1)], list[largestLocation]);
}
end.

Finding the k
th
largest value in a list
Complexity of the algorithm:
On the first pass a total of n-1 comparisons would be made.
The second pass would total n-2 comparisons, and so on. On
the k
th
pass a total of n-k comparisons would occur.
This gives:






Note that this equation also tells us that if k is greater than
n/2, it would be faster for look for the n-k
th
smallest value.
This algorithm is reasonably efficient for values of k that are
close to either end of the list, but there is a more efficient
way to accomplish this process for values of k that are close
to the middle of the list

( )
( )

=
=

=
k
1 i
n k O
2
1 k k
k n i n
Finding the k
th
largest value in a list
Since we are only interested in the k
th
largest value,
we dont really need to know the exact position for
the values that are larger than k
th
largest; we only
need to know that they are larger. their position in
the list is irrelevant.

If we choose an element from the list and partition
the list into two distinct parts, one containing those
elements that are larger than the chosen element
and the other containing those elements that are
smaller than the chosen element (partition
algorithm quick sort to arrange an array in
decreasing order, pivot is selected at random)


Finding the k
th
largest value in a list
The chosen element will wind up in some position p
in the list. This will mean that the chosen element
is the p
th
largest element in the list.

If we are lucky and p = k, then were done. If k < p,
then we will repeat the partitioning process on the
left part. If k > p, then we will apply the process on
the right part, but well need to reduce the value of
k by the number of values weve eliminated in the
larger partition.

The following slides illustrate this technique:

Finding the k
th
largest value in a list



6 23 44 88 9 13 46 55
Initial List
95
Chosen Pivot
95 88 55 44 6 9 13 46
First partitioning
23
We made a good guess and the chosen pivot winds up
as the 3
th
largest element (k = p =3 ) which is what we wanted.

Suppose we are looking for the 3
th
largest element (k= 3)
Pivot = 3
rd
Largest
Finding the k
th
largest value in a list

6 23 44 88 9 13 46 55
Initial List
95
Chosen Pivot
Suppose we are looking for the 2
nd
largest element
55 95 88 46 23 9 13 6
Second partitioning
44
We made a good guess the second time and
the chosen element winds up as the 2
nd
largest
element (p=2) which is what we want.
new pivot
ignore these elements this time
The chosen pivot winds up as the 4
th
largest element
(p=4) which is larger than what we wanted.
Since k < p, well repartition the left sub list.
55 95 88 46 23 9 13 6
First Partitioning
44
pivot
Finding the k
th
largest value in a list





KthLargest (A, lo, hi,k) {
// A the list of elements to be sorted
// lo the index of the first element in the list
// hi the index of the last element in the list
// k the element of the list we want

if lo < hi {
p Partition( A, lo, hi); // returns the final index of the pivot (p)
If p=k return A[p];
else
if p<k KthLargest (A,lo,p-1,k);
if p>k KthLargest (A,p+1,hi, k-p);
}
}

Finding the k
th
largest value in a list
Complexity:
If we assume that on average the partitioning
process will divide the list into two roughly equal
halves, then approximately:
n + n/2 + n/4 + n/8 + + 1
will be be necessary.
This is about 2n comparisons. So the process is
linear and independent of k.