Faculty of Computer and Artificial Intelligence
Sadat University
Analysis and Design of Algorithms (CS 302)
Lecture :5
“Divide and Conquer”
Dr.Sara A Shehab
Divide-and-Conquer
The most-well known algorithm design strategy:
1. Divide instance of problem into two or more
smaller instances
2. Solve smaller instances recursively
3. Obtain solution to original (larger) instance by
combining these solutions
2
Divide-and-Conquer Technique (cont.)
a problem of size n
subproblem 1 subproblem 2
of size n/2 of size n/2
a solution to a solution to
subproblem 1 subproblem 2
a solution to
the original problem
Divide-and-Conquer Examples
Sorting:
1. mergesort
2. quicksort
4
Mergesort
Split array A[0..n-1] in two about equal halves and make copies of each half in
arrays B and C
Sort arrays B and C recursively
Merge sorted arrays B and C into array A as follows:
◦ Repeat the following until no elements remain in one of the
arrays:
◦ compare the first elements in the remaining unprocessed
portions of the arrays
◦ copy the smaller of the two into A, while incrementing the
index indicating the unprocessed portion of that array
◦ Once all elements in one of the arrays are processed, copy the
remaining unprocessed elements from the other array into A.
5
Pseudocode of Merge sort
6
Pseudocode of Merge
7
Mergesort Example
8 3 2 9 7 1 5 4
8 3 2 9 7 1 5 4
8 3 2 9 71 5 4
8 3 2 9 7 1 5 4
3 8 2 9 1 7 4 5
2 3 8 9 1 4 5 7
1 2 3 4 5 7 8 9 8
Analysis of Mergesort
All cases have same efficiency: Θ(n log n)
9
Quicksort
Select a pivot (partitioning element) – here, the first element
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 (see next
slide for an algorithm)
p
A[i]p A[i]p
Exchange the pivot with the last element in the first (i.e., ) subarray
— the pivot is now in its final position
Sort the two subarrays recursively
10
Hoare’s Partitioning Algorithm
11
Quick Sort Example
➢ To understand the working of quick sort, let's take an unsorted
array.
➢ It will make the concept more clear and understandable.
➢ Let the elements of array are -
➢ In the given array, we consider the leftmost element as pivot.
So, in this case, a[left] = 24, a[right] = 27 and a[pivot] = 24.
➢ Since, pivot is at left, so algorithm starts from right and move
towards left.
12
Quick Sort Example
➢ Now, a[pivot] < a[right]
➢ So algorithm moves forward one position towards left, i.e. -
Quick Sort Example
➢ Now, a[left] = 24, a[right] = 19, and a[pivot] = 24.
➢ Because, a[pivot] > a[right],
➢ so, algorithm will swap a[pivot] with a[right], and pivot moves to
right, as -
Quick Sort Example
➢ Now, a[left] = 19, a[right] = 24, and a[pivot] = 24.
➢ Since, pivot is at right, so algorithm starts from left and moves to
right.
➢ As a[pivot] > a[left], so algorithm moves one position to right as -
15
Quick Sort Example
➢ Now, a[left] = 9, a[right] = 24, and a[pivot] = 24.
➢ As a[pivot] > a[left],
➢ so algorithm moves one position to right as -
16
Quick Sort Example
➢ Now, a[left] = 29, a[right] = 24, and a[pivot] = 24.
➢ As a[pivot] < a[left],
➢ so, swap a[pivot] and a[left], now pivot is at left, i.e. -
17
Quick Sort Example
➢ Since, pivot is at left,
➢ so algorithm starts from right, and move to left.
➢ Now, a[left] = 24, a[right] = 29, and a[pivot] = 24.
➢ As a[pivot] < a[right],
➢ so algorithm moves one position to left, as -
18
Quick Sort Example
➢ Now, a[pivot] = 24, a[left] = 24, and a[right] = 14.
➢ As a[pivot] > a[right],
➢ so, swap a[pivot] and a[right], now pivot is at right, i.e. -
19
Quick Sort Example
➢ Now, a[pivot] = 24, a[left] = 14, and a[right] = 24.
➢ Pivot is at right,
➢ so the algorithm starts from left and move to right.
20
Quick Sort Example
➢ Now, a[pivot] = 24, a[left] = 24, and a[right] = 24.
➢ So, pivot, left and right are pointing the same element.
➢ It represents the termination of procedure.
➢ Element 24, which is the pivot element is placed at its exact
position.
21
Quick Sort Example
➢ Now, in a similar manner, quick sort algorithm is separately
applied to the left and right sub-arrays.
➢ After sorting gets done, the array will be -
22
Quicksort Example
5 3 1 9 8 2 4 7
23
Analysis of Quicksort
Best case: split in the middle — Θ(n log n)
Worst case: sorted array! — Θ(n2)
Average case: random arrays — Θ(n log n)
24
