COSC1285/2123: Algorithms & Analysis – Divide and Conquer
COSC1285/2123: Algorithms & Analysis
Divide and Conquer
Hoang MIT University
Email : sonhoang. .au
Lecture 6
(RMIT University) Divide and Conquer Lecture 6 1 / 80
Overview
Levitin – The design and analysis of algorithms
This week we will be covering the material from Chapter 5.
Learning outcomes:
• Understand the Divide-and-conquer algorithmic approach
• Understand and apply merge and quick sort.
• Understand and apply height and traversal operations for BST
(RMIT University) Divide and Conquer Lecture 6 2 / 80
Outline
1 Problem Overview
2 Merge Sort
3 Quick Sort
4 Binary Search Trees
5 Case Study
6 Summary
(RMIT University) Divide and Conquer Lecture 6 3 / 80
Overview
1 Problem Overview
2 Merge Sort
3 Quick Sort
4 Binary Search Trees
5 Case Study
6 Summary
(RMIT University) Divide and Conquer Lecture 6 4 / 80
Divide and Conquer
problem of
size n
subproblem 2
of size n/2
solution to the
original problem
solution to
subproblem 1
solution to
subproblem 2
subproblem 1
of size n/2
Strategy:
1 Divide the problem instance
into smaller subproblems.
2 Solve each subproblem
(recursively).
3 Combine smaller solutions to
solve the original instance.
(RMIT University) Divide and Conquer Lecture 6 5 / 80
Compare with Decrease-by-a-constant-factor
Strategy:
1 Decrease-by-a-constant-factor
algorithms.
(RMIT University) Divide and Conquer Lecture 6 6 / 80
Overview
1 Problem Overview
2 Merge Sort
3 Quick Sort
4 Binary Search Trees
5 Case Study
6 Summary
(RMIT University) Divide and Conquer Lecture 6 7 / 80
Merge Sort
• Idea:
• Imagine we recursively divided an array (we wanted to sort) into
halves, until we reach single element partitions.
• We then recursively merge the partitions, where we have a process
that maintains sorting after partitions are merged.
• When we finally merge the last two partitions, we have a sorted
array.
(RMIT University) Divide and Conquer Lecture 6 8 / 80
Merge Sort
• Idea:
• Imagine we recursively divided an array (we wanted to sort) into
halves, until we reach single element partitions.
• We then recursively merge the partitions, where we have a process
that maintains sorting after partitions are merged.
• When we finally merge the last two partitions, we have a sorted
array.
(RMIT University) Divide and Conquer Lecture 6 8 / 80
Merge Sort
• Idea:
• Imagine we recursively divided an array (we wanted to sort) into
halves, until we reach single element partitions.
• We then recursively merge the partitions, where we have a process
that maintains sorting after partitions are merged.
• When we finally merge the last two partitions, we have a sorted
array.
(RMIT University) Divide and Conquer Lecture 6 8 / 80
Merge Sort Example
15 21 1 25 12 6 8 3 5 19 10 18
0COMPARES
(RMIT University) Divide and Conquer Lecture 6 9 / 80
Merge Sort Example
15 21 1 25 12 6
0
181019538
COMPARES
(RMIT University) Divide and Conquer Lecture 6 10 / 80
Merge Sort Example
15 21 1
0
18101953861225
COMPARES
(RMIT University) Divide and Conquer Lecture 6 11 / 80
Merge Sort Example
15
0
181958625121 12 3 10
COMPARES
(RMIT University) Divide and Conquer Lecture 6 12 / 80
Merge Sort Example
15
0
21 181019538612251
COMPARES
(RMIT University) Divide and Conquer Lecture 6 13 / 80
Merge Sort Example
15 211 25 12 6 8 3 5 19 10 18
COMPARES 1
(RMIT University) Divide and Conquer Lecture 6 14 / 80
Merge Sort Example
15 211 25 126 8 3 5 19 10 18
COMPARES 2
(RMIT University) Divide and Conquer Lecture 6 15 / 80
Merge Sort Example
15 211 25 126 8 3 5 19 10 18
COMPARES 3
(RMIT University) Divide and Conquer Lecture 6 16 / 80
Merge Sort Example
15 211 25 126 8 3 5 19 10 18
COMPARES 4
(RMIT University) Divide and Conquer Lecture 6 17 / 80
Merge Sort Example
151 21 25 6 12 8 3 5 19 10 18
COMPARES 6
(RMIT University) Divide and Conquer Lecture 6 18 / 80
Merge Sort Example
151 21 12 256 8 3 5 19 10 18
COMPARES 8
(RMIT University) Divide and Conquer Lecture 6 19 / 80
Merge Sort Example
151 21 12 256 5 83 19 10 18
COMPARES 10
(RMIT University) Divide and Conquer Lecture 6 20 / 80
Merge Sort Example
151 21 12 256 5 83 18 1910
COMPARES 12
(RMIT University) Divide and Conquer Lecture 6 21 / 80
Merge Sort Example
1 6 12 15 21 25 3 5 8 10 18 19
COMPARES 17
(RMIT University) Divide and Conquer Lecture 6 22 / 80
Merge Sort Example
1 6 12 15 21 25 3 5 8 10 18 19
COMPARES 20
(RMIT University) Divide and Conquer Lecture 6 23 / 80
Merge Sort Example
1 3 5 6 8 10 12 15 18 19 21 25
COMPARES 30
(RMIT University) Divide and Conquer Lecture 6 24 / 80
Merge Sort Example
(RMIT University) Divide and Conquer Lecture 6 25 / 80
Merge Sort Algorithm
ALGORITHM MergeSort (A[0 . . . n − 1])
/* Sort an array using a divide-and-conquer merge sort. */
/* INPUT : An array A[0 . . . n − 1] of orderable elements. */
/* OUTPUT : An array A[0 . . . n − 1] sorted in ascending order. */
1: if n > 1 then
2: B = A[0 . . . bn/2c − 1] /* B is first half of A */
3: C = A[bn/2c . . . n − 1] /* C is second half of A */
4: MergeSort (B)
5: MergeSort (C)
6: Merge (B,C,A) /* Merge B and C to help sort A */
7: end if
(RMIT University) Divide and Conquer Lecture 6 26 / 80
Merge in Mergesort
Given two sorted subarrays B, C, want to merge them together to form
a sorted A.
Idea:
1 Consider first element of each subarray, i.e, B[0] and C[0].
Compare them. Whichever one is smaller, copy to A[0], and
increment current pointer of subarrays that has smaller element
and A.
2 Repeat until one of subarrays is empty. Then copy the rest of
subarray to A.
(RMIT University) Divide and Conquer Lecture 6 27 / 80
Merge in Mergesort
Given two sorted subarrays B, C, want to merge them together to form
a sorted A.
Idea:
1 Consider first element of each subarray, i.e, B[0] and C[0].
Compare them. Whichever one is smaller, copy to A[0], and
increment current pointer of subarrays that has smaller element
and A.
2 Repeat until one of subarrays is empty. Then copy the rest of
subarray to A.
(RMIT University) Divide and Conquer Lecture 6 27 / 80
Merge in Mergesort
ALGORITHM Merge (B[0 . . . p − 1],C[0 . . . q − 1],A[0 . . . p + q − 1])
/* Merge two sorted arrays into one sorted array. */
/* INPUT : Arrays B[0 . . . p − 1] and C[0 . . . q − 1] both sorted. */
/* OUTPUT : Sorted array A[0 . . . p + q − 1] of the elements of B and C. */
1: i = 0; j = 0; k = 0
2: while i < p and j < q do
3: if B[i] ≤ C[j] then
4: A[k ] = B[i]
5: i = i + 1
6: else
7: A[k ] = C[j]
8: j = j + 1
9: end if
10: k = k + 1
11: end while
12: if i == p then
13: copy C[j . . . q − 1] to A[k . . . p + q − 1]
14: else
15: copy B[i . . . p − 1] to A[k . . . p + q − 1]
16: end if
(RMIT University) Divide and Conquer Lecture 6 28 / 80
Merge Sort Example
Animation of Mergesort
https://www.youtube.com/watch?v=es2T6KY45cA
(RMIT University) Divide and Conquer Lecture 6 29 / 80
Comments on Merge Sort
• Guarantees O(n log n) time complexity, regardless of the original
distribution of data – this sorting method is insensitive to the data
distribution.
• The main drawback in this method is the extra space required for
merging two partitions/sub-arrays, e.g. B and C from
pseudo-code.
• Merge sort is a stable sorting method.
(RMIT University) Divide and Conquer Lecture 6 30 / 80
Comments on Merge Sort
• Guarantees O(n log n) time complexity, regardless of the original
distribution of data – this sorting method is insensitive to the data
distribution.
• The main drawback in this method is the extra space required for
merging two partitions/sub-arrays, e.g. B and C from
pseudo-code.
• Merge sort is a stable sorting method.
(RMIT University) Divide and Conquer Lecture 6 30 / 80
Comments on Merge Sort
• Guarantees O(n log n) time complexity, regardless of the original
distribution of data – this sorting method is insensitive to the data
distribution.
• The main drawback in this method is the extra space required for
merging two partitions/sub-arrays, e.g. B and C from
pseudo-code.
• Merge sort is a stable sorting method.
(RMIT University) Divide and Conquer Lecture 6 30 / 80
Merge Sort Analysis
Lets set up the recurrence relationship.
C(n) = 2C(n/2) + Cmerge(n), for n > 1, C(1) = 0.
Cmerge(n) = n − 1 (WHY?)
C(n) = 2C(n/2) + n − 1 for n > 1, C(1) = 0.
How do we solve this recursion? There are several ways:
• using backward substitution method.
• using recursion tree (please read textbook, not examinable).
• using the Master Theorem (please read textbook, not examinable).
C(n) ∈ O(n log2(n))
(RMIT University) Divide and Conquer Lecture 6 31 / 80
Merge Sort Analysis
Lets set up the recurrence relationship.
C(n) = 2C(n/2) + Cmerge(n), for n > 1, C(1) = 0.
Cmerge(n) = n − 1 (WHY?)
C(n) = 2C(n/2) + n − 1 for n > 1, C(1) = 0.
How do we solve this recursion? There are several ways:
• using backward substitution method.
• using recursion tree (please read textbook, not examinable).
• using the Master Theorem (please read textbook, not examinable).
C(n) ∈ O(n log2(n))
(RMIT University) Divide and Conquer Lecture 6 31 / 80
Merge Sort Analysis
Lets set up the recurrence relationship.
C(n) = 2C(n/2) + Cmerge(n), for n > 1, C(1) = 0.
Cmerge(n) = n − 1 (WHY?)
C(n) = 2C(n/2) + n − 1 for n > 1, C(1) = 0.
How do we solve this recursion? There are several ways:
• using backward substitution method.
• using recursion tree (please read textbook, not examinable).
• using the Master Theorem (please read textbook, not examinable).
C(n) ∈ O(n log2(n))
(RMIT University) Divide and Conquer Lecture 6 31 / 80
Overview
1 Problem Overview
2 Merge Sort
3 Quick Sort
4 Binary Search Trees
5 Case Study
6 Summary
(RMIT University) Divide and Conquer Lecture 6 32 / 80
Quick Sort
Motivation:
• Mergesort has consistent behaviour for all inputs – what if we
seek an algorithm that is fast for the average case?
• Quicksort is such a sorting algorithm, often the best practical
choice in terms of efficiency because of its good performance on
the average case.
• Quick Sort is a divide and conquer algorithm.
(RMIT University) Divide and Conquer Lecture 6 33 / 80
Quick Sort
Idea:
1 Select an element from the array for which, we hope, about half
the elements will come before and half after in a sorted array. Call
this element the pivot.
2 Partition the array so that all elements with a value less than the
pivot are in one subarray, and larger elements come in the other
subarray.
3 Swap pivot into position of array that is between the partitions.
4 Recursively apply the same procedure on the two subarrays
separately.
5 Terminate when only subarrays are of one element.
6 When terminate, because we do things in-place, the resulting
array is sorted.
(RMIT University) Divide and Conquer Lecture 6 34 / 80
Quick Sort
Idea:
1 Select an element from the array for which, we hope, about half
the elements will come before and half after in a sorted array. Call
this element the pivot.
2 Partition the array so that all elements with a value less than the
pivot are in one subarray, and larger elements come in the other
subarray.
3 Swap pivot into position of array that is between the partitions.
4 Recursively apply the same procedure on the two subarrays
separately.
5 Terminate when only subarrays are of one element.
6 When terminate, because we do things in-place, the resulting
array is sorted.
(RMIT University) Divide and Conquer Lecture 6 34 / 80
Quick Sort
Idea:
1 Select an element from the array for which, we hope, about half
the elements will come before and half after in a sorted array. Call
this element the pivot.
2 Partition the array so that all elements with a value less than the
pivot are in one subarray, and larger elements come in the other
subarray.
3 Swap pivot into position of array that is between the partitions.
4 Recursively apply the same procedure on the two subarrays
separately.
5 Terminate when only subarrays are of one element.
6 When terminate, because we do things in-place, the resulting
array is sorted.
(RMIT University) Divide and Conquer Lecture 6 34 / 80
Quick Sort
Idea:
1 Select an element from the array for which, we hope, about half
the elements will come before and half after in a sorted array. Call
this element the pivot.
2 Partition the array so that all elements with a value less than the
pivot are in one subarray, and larger elements come in the other
subarray.
3 Swap pivot into position of array that is between the partitions.
4 Recursively apply the same procedure on the two subarrays
separately.
5 Terminate when only subarrays are of one element.
6 When terminate, because we do things in-place, the resulting
array is sorted.
(RMIT University) Divide and Conquer Lecture 6 34 / 80
Quick Sort
Idea:
1 Select an element from the array for which, we hope, about half
the elements will come before and half after in a sorted array. Call
this element the pivot.
2 Partition the array so that all elements with a value less than the
pivot are in one subarray, and larger elements come in the other
subarray.
3 Swap pivot into position of array that is between the partitions.
4 Recursively apply the same procedure on the two subarrays
separately.
5 Terminate when only subarrays are of one element.
6 When terminate, because we do things in-place, the resulting
array is sorted.
(RMIT University) Divide and Conquer Lecture 6 34 / 80
Quick Sort
Initial:
Select Pivot:
Partition array:
(RMIT University) Divide and Conquer Lecture 6 35 / 80
Quick Sort (Hoare partition scheme)
How to efficiently partition the elements less than pivot on one side,
greater than partition on the other?
We basically run two linear scans from the front and back of the array,
and swap elements that are out of place (i.e., will be on the wrong side
of the eventual place of pivot)
(RMIT University) Divide and Conquer Lecture 6 36 / 80
Quick Sort (Hoare partition scheme)
(RMIT University) Divide and Conquer Lecture 6 37 / 80
Quick Sort
ALGORITHM QuickSort (A[` . . . r ])
/* Sort a subarray using by quicksort. */
/* INPUT : A subarray A[` . . . r ] of A[0 . . . n − 1], defined by its left
and right indices ` and r . */
/* OUTPUT : A subarray A[` . . . r ] sorted in ascending order. */
1: if ` < r then
2: /* s is the index to split array. */
3: s = QPartition(A[` . . . r ])
4: QuickSort(A[` . . . s − 1])
5: QuickSort(A[s + 1 . . . r ])
6: end if
(RMIT University) Divide and Conquer Lecture 6 38 / 80
Quick Sort
ALGORITHM QPartition (A[` . . . r ])
/* Partition a subarray using the first element as a pivot. */
/* INPUT : A subarray A[` . . . r ] of A[0 . . . n − 1], defined by its left
and right indices ` and r , where (` < r). */
/* OUTPUT : A partition of A[` . . . r ], along with the index of the split position. */
1: p = A[`]
2: i = `; j = r + 1
3: repeat
4: do
5: i = i + 1
6: while A[i] < p
7: do
8: j = j − 1
9: while A[j] > p
10: swap(A[i],A[j])
11: until i ≥ j
12: swap(A[i],A[j]) // we need to reverse the last swap, which is incorrect when i and j could
cross each other
13: swap(A[`],A[j])
14: return j
(RMIT University) Divide and Conquer Lecture 6 39 / 80
Quick Sort Example
15 21 1 25 12 6 8 3 5 19 10 18
0 0COMPARES SWAPS
(RMIT University) Divide and Conquer Lecture 6 40 / 80
Quick Sort Example
15 21 1 25 12 6 8 3 5 19 10 18
COMPARES SWAPS 01
i j
(RMIT University) Divide and Conquer Lecture 6 41 / 80
Quick Sort Example
15 21 1 25 12 6 8 3 5 19 10 18
COMPARES SWAPS 0
i
2
j
(RMIT University) Divide and Conquer Lecture 6 42 / 80
Quick Sort Example
15 21 1 25 12 6 8 3 5 19 10 18
COMPARES SWAPS 0
i
3
j
(RMIT University) Divide and Conquer Lecture 6 43 / 80
Quick Sort Example
15 21 1 25 12 6 8 3 5 19 10 18
COMPARES SWAPS 0
i
3
j
(RMIT University) Divide and Conquer Lecture 6 44 / 80
Quick Sort Example
15 1 25 12 6 8 3 5 19 18
COMPARES SWAPS
i
3 1
2110
j
(RMIT University) Divide and Conquer Lecture 6 45 / 80
Quick Sort Example
15 1 25 12 6 8 3 5 19 18
COMPARES SWAPS 1
2110
i
4
j
(RMIT University) Divide and Conquer Lecture 6 46 / 80
Quick Sort Example
15 1 25 12 6 8 3 5 19 18
COMPARES SWAPS 1
2110
i
5
j
(RMIT University) Divide and Conquer Lecture 6 47 / 80
Quick Sort Example
15 1 25 12 6 8 3 5 19 18
COMPARES SWAPS 1
2110
i
6
j
(RMIT University) Divide and Conquer Lecture 6 48 / 80
Quick Sort Example
15 1 25 12 6 8 3 5 19 18
COMPARES SWAPS 1
2110
i
7
j
(RMIT University) Divide and Conquer Lecture 6 49 / 80
Quick Sort Example
15 1 25 12 6 8 3 5 19 18
COMPARES SWAPS 1
2110
i
8
j
(RMIT University) Divide and Conquer Lecture 6 50 / 80
Quick Sort Example
15 1 25 12 6 8 3 5 19 18
COMPARES SWAPS 1
2110
i
9
j
(RMIT University) Divide and Conquer Lecture 6 51 / 80
Quick Sort Example
15 1 25 12 6 8 3 5 19 18
COMPARES SWAPS 1
2110
i
9
j
(RMIT University) Divide and Conquer Lecture 6 52 / 80
Quick Sort Example
15 1 12 6 8 3 19 18
COMPARES SWAPS
2110
i
9 2
5 25
j
(RMIT University) Divide and Conquer Lecture 6 53 / 80
Quick Sort Example
15 1 12 6 8 3 19 18
COMPARES SWAPS
2110
2
5 25
i
10
j
(RMIT University) Divide and Conquer Lecture 6 54 / 80
Quick Sort Example
15 1 12 6 8 3 19 18
COMPARES SWAPS
2110
2
5 25
i
11
j
(RMIT University) Divide and Conquer Lecture 6 55 / 80
Quick Sort Example
15 1 12 6 8 3 19 18
COMPARES SWAPS
2110
2
5 25
i
12
j
(RMIT University) Divide and Conquer Lecture 6 56 / 80
Quick Sort Example
15 1 12 6 8 3 19 18
COMPARES SWAPS
2110
2
5 25
i
13
j
(RMIT University) Divide and Conquer Lecture 6 57 / 80
Quick Sort Example
15 1 12 6 8 3 19 18
COMPARES SWAPS
2110
2
5 25
i
14
j
(RMIT University) Divide and Conquer Lecture 6 58 / 80
Quick Sort Example
15 1 12 6 8 3 19 18
COMPARES SWAPS
2110
2
5 25
16
j
i
(RMIT University) Divide and Conquer Lecture 6 59 / 80
Quick Sort Example
15 1 12 6 8 3 19 18
COMPARES SWAPS
2110
2
5 25
i
17
j
(RMIT University) Divide and Conquer Lecture 6 60 / 80
Quick Sort Example
15 1 12 6 8 3 19 18
COMPARES SWAPS
2110 5 25
i
17 4
j
(RMIT University) Divide and Conquer Lecture 6 61 / 80
Quick Sort Example
1 12 6 8 19 18
COMPARES SWAPS
2110
i
17
3 5 15 25
5
j
(RMIT University) Divide and Conquer Lecture 6 62 / 80
Quick Sort Example
1 12 6 8 19 18
COMPARES SWAPS
2110
17
3 5 15 25
5
(RMIT University) Divide and Conquer Lecture 6 63 / 80
Quick Sort Complexity
1 :
• Occurs when the pivot repeatedly splits the dataset into two equal
sized subsets.
• The complexity is O(n log2 n).
2 Worst Case:
• If the pivot is chosen poorly, one of the partitions may be empty,
and the other reduced by only one element.
• Then the quick sort is slower than brute-force sorting (due to
partitioning overheads).
• The complexity is (n + 1) + n + (n − 1) + · · ·+ 1 ≈ n2/2 ∈ O(n2).
• Occurs when array is already sorted or reverse order sorted.
3 Average case:
• Number of comparisons is ≈ 1.39n log n.
• 39% more comparisons than merge sort.
• But faster than merge sort in practice because of lower cost of
other high-frequency operations, and uses considerably less space
(no need to copy to temporary arrays).
(RMIT University) Divide and Conquer Lecture 6 64 / 80
Quick Sort Complexity
1 :
• Occurs when the pivot repeatedly splits the dataset into two equal
sized subsets.
• The complexity is O(n log2 n).
2 Worst Case:
• If the pivot is chosen poorly, one of the partitions may be empty,
and the other reduced by only one element.
• Then the quick sort is slower than brute-force sorting (due to
partitioning overheads).
• The complexity is (n + 1) + n + (n − 1) + · · ·+ 1 ≈ n2/2 ∈ O(n2).
• Occurs when array is already sorted or reverse order sorted.
3 Average case:
• Number of comparisons is ≈ 1.39n log n.
• 39% more comparisons than merge sort.
• But faster than merge sort in practice because of lower cost of
other high-frequency operations, and uses considerably less space
(no need to copy to temporary arrays).
(RMIT University) Divide and Conquer Lecture 6 64 / 80
Quick Sort Complexity
1 :
• Occurs when the pivot repeatedly splits the dataset into two equal
sized subsets.
• The complexity is O(n log2 n).
2 Worst Case:
• If the pivot is chosen poorly, one of the partitions may be empty,
and the other reduced by only one element.
• Then the quick sort is slower than brute-force sorting (due to
partitioning overheads).
• The complexity is (n + 1) + n + (n − 1) + · · ·+ 1 ≈ n2/2 ∈ O(n2).
• Occurs when array is already sorted or reverse order sorted.
3 Average case:
• Number of comparisons is ≈ 1.39n log n.
• 39% more comparisons than merge sort.
• But faster than merge sort in practice because of lower cost of
other high-frequency operations, and uses considerably less space
(no need to copy to temporary arrays).
(RMIT University) Divide and Conquer Lecture 6 64 / 80
Quick Sort – Pivots
Choosing a pivot:
• First or last element: worst case appears for already sorted or
reverse sorted arrays (as we saw last slide).
• Median of three: requires extra compares but generally avoids
worst case.
• Random element: Poor cases are very unlikely, but efficient
implementations can be non-trivial.
• As long as selected pivot is not always the worst case, Quick sort
on average performs well.
For the curious: Watch the Google Talk: ’Three Beautiful Quicksorts’
by (after lectures)
(RMIT University) Divide and Conquer Lecture 6 65 / 80
Quick Sort – Pivots
Choosing a pivot:
• First or last element: worst case appears for already sorted or
reverse sorted arrays (as we saw last slide).
• Median of three: requires extra compares but generally avoids
worst case.
• Random element: Poor cases are very unlikely, but efficient
implementations can be non-trivial.
• As long as selected pivot is not always the worst case, Quick sort
on average performs well.
For the curious: Watch the Google Talk: ’Three Beautiful Quicksorts’
by (after lectures)
(RMIT University) Divide and Conquer Lecture 6 65 / 80
Quick Sort – Pivots
Choosing a pivot:
• First or last element: worst case appears for already sorted or
reverse sorted arrays (as we saw last slide).
• Median of three: requires extra compares but generally avoids
worst case.
• Random element: Poor cases are very unlikely, but efficient
implementations can be non-trivial.
• As long as selected pivot is not always the worst case, Quick sort
on average performs well.
For the curious: Watch the Google Talk: ’Three Beautiful Quicksorts’
by (after lectures)
(RMIT University) Divide and Conquer Lecture 6 65 / 80
Quick Sort – Pivots
Choosing a pivot:
• First or last element: worst case appears for already sorted or
reverse sorted arrays (as we saw last slide).
• Median of three: requires extra compares but generally avoids
worst case.
• Random element: Poor cases are very unlikely, but efficient
implementations can be non-trivial.
• As long as selected pivot is not always the worst case, Quick sort
on average performs well.
For the curious: Watch the Google Talk: ’Three Beautiful Quicksorts’
by (after lectures)
(RMIT University) Divide and Conquer Lecture 6 65 / 80
Quick Sort Properties
• Quick sort does sorting in place (don’t need additional copying
and temporary arrays).
• Quick Sort is not a stable sorting method.
(RMIT University) Divide and Conquer Lecture 6 66 / 80
Overview
1 Problem Overview
2 Merge Sort
3 Quick Sort
4 Binary Search Trees
5 Case Study
6 Summary
(RMIT University) Divide and Conquer Lecture 6 67 / 80
BST Height
16
6
4
1 5
12
8 15
26
20
18 25
28
27 30 —
—
—
—
3
2
1
0
The height of a tree is the length of the path from the root to the
deepest node in the tree. A rooted tree with only 1 node has a height
of zero.
(RMIT University) Divide and Conquer Lecture 6 68 / 80
BST Height
ALGORITHM BSTHeight (T )
// Recursively compute the height of a binary search tree.
// INPUT : A binary tree T .
// OUTPUT : Height of T .
1: if T = ∅ then
2: return −1
3: else
4: return max (BSTHeight (TL), BSTHeight (TR)) +1
5: end if
The worst case complexity to calculate the height is Θ(n). Why?
What is the best case?
(RMIT University) Divide and Conquer Lecture 6 69 / 80
BST Height
ALGORITHM BSTHeight (T )
// Recursively compute the height of a binary search tree.
// INPUT : A binary tree T .
// OUTPUT : Height of T .
1: if T = ∅ then
2: return −1
3: else
4: return max (BSTHeight (TL), BSTHeight (TR)) +1
5: end if
The worst case complexity to calculate the height is Θ(n). Why?
What is the best case?
(RMIT University) Divide and Conquer Lecture 6 69 / 80
BST Height
ALGORITHM BSTHeight (T )
// Recursively compute the height of a binary search tree.
// INPUT : A binary tree T .
// OUTPUT : Height of T .
1: if T = ∅ then
2: return −1
3: else
4: return max (BSTHeight (TL), BSTHeight (TR)) +1
5: end if
The worst case complexity to calculate the height is Θ(n). Why?
What is the best case?
(RMIT University) Divide and Conquer Lecture 6 69 / 80
BST Traversal
• Given a tree, systematically process every node in that tree.
• For binary trees, we have up to two children for each node, and
therefore we have three basic orders in which we can process the
tree.
• preorder: The root is visited before the left and right subtrees are
visited (in that order).
• inorder: The root is visited after visiting its left subtree but before
visiting the right subtree.
• postorder: The root is visited after visiting the left and right
subtrees (in that order).
• All of these methods are Θ(n).
(RMIT University) Divide and Conquer Lecture 6 70 / 80
Inorder BST Traversal
16
6
4
1 5
12
26
20 28
27
ALGORITHM Inorder(T )
// An In-order traversal of a binary tree.
// INPUT : A binary tree T (with labeled vertices).
// OUTPUT : Node labels listed in-order.
1: if T 6= ∅ then
2: Inorder(TL) // TL is the left sub-tree.
3: process node label
4: Inorder(TR) // TR is the right sub-tree.
5: end if
OUTPUT : 1,4,5,6,12,16,20,26,27,28
(RMIT University) Divide and Conquer Lecture 6 71 / 80
Inorder BST Traversal
16
6
4
1 5
12
26
20 28
27
ALGORITHM Inorder(T )
// An In-order traversal of a binary tree.
// INPUT : A binary tree T (with labeled vertices).
// OUTPUT : Node labels listed in-order.
1: if T 6= ∅ then
2: Inorder(TL) // TL is the left sub-tree.
3: process node label
4: Inorder(TR) // TR is the right sub-tree.
5: end if
OUTPUT : 1,4,5,6,12,16,20,26,27,28
(RMIT University) Divide and Conquer Lecture 6 71 / 80
Pre-order BST Traversal
16
6
4
1 5
12
26
20 28
27
ALGORITHM Preorder(T )
// A Pre-order traversal of a binary tree.
// INPUT : A binary tree T (with labeled vertices).
// OUTPUT : Node labels listed in preorder.
1: if T 6= ∅ then
2: process node label
3: Preorder(TL) // TL is the left sub-tree.
4: Preorder(TR) // TR is the right sub-tree.
5: end if
OUTPUT : 16,6,4,1,5,12,26,20,28,27
(RMIT University) Divide and Conquer Lecture 6 72 / 80
Pre-order BST Traversal
16
6
4
1 5
12
26
20 28
27
ALGORITHM Preorder(T )
// A Pre-order traversal of a binary tree.
// INPUT : A binary tree T (with labeled vertices).
// OUTPUT : Node labels listed in preorder.
1: if T 6= ∅ then
2: process node label
3: Preorder(TL) // TL is the left sub-tree.
4: Preorder(TR) // TR is the right sub-tree.
5: end if
OUTPUT : 16,6,4,1,5,12,26,20,28,27
(RMIT University) Divide and Conquer Lecture 6 72 / 80
Postorder BST Traversal
16
6
4
1 5
12
26
20 28
27
ALGORITHM Postorder(T )
// A Post-order traversal of a binary tree.
// INPUT : A binary tree T (with labeled vertices).
// OUTPUT : Node labels listed in postorder.
1: if T 6= ∅ then
2: Postorder(TL) // TL is the left sub-tree.
3: Postorder(TR) // TR is the right sub-tree.
4: process node label
5: end if
OUTPUT : 1,5,4,12,6,20,27,28,26,16
(RMIT University) Divide and Conquer Lecture 6 73 / 80
Postorder BST Traversal
16
6
4
1 5
12
26
20 28
27
ALGORITHM Postorder(T )
// A Post-order traversal of a binary tree.
// INPUT : A binary tree T (with labeled vertices).
// OUTPUT : Node labels listed in postorder.
1: if T 6= ∅ then
2: Postorder(TL) // TL is the left sub-tree.
3: Postorder(TR) // TR is the right sub-tree.
4: process node label
5: end if
OUTPUT : 1,5,4,12,6,20,27,28,26,16
(RMIT University) Divide and Conquer Lecture 6 73 / 80
Overview
1 Problem Overview
2 Merge Sort
3 Quick Sort
4 Binary Search Trees
5 Case Study
6 Summary
(RMIT University) Divide and Conquer Lecture 6 74 / 80
Case Study – Problem
Case Study Problem
XYZ Pty. Ltd. manufactures and maintains a set of golf buggies around
the world. Each buggy is identified by a unique ID that encodes when it
was made and what batch it came from, and buggies that have IDs in a
particular range are from made in the same period and have same
features in them. XYZ wants to build a custom database that maintains
what is the current set of active buggies they are servicing around the
world. They want to quickly retrieve buggies by their IDs and also
quickly retrieve all buggies in a particular ID range. They ask for your
help.
(RMIT University) Divide and Conquer Lecture 6 75 / 80
Case Study – Mapping the Problem to a Known Data
Structure
The problem has two requirements:
• Retrieval of buggy by ID
• Retrieval of a set of buggies that have the queries ID range
Which data structure to use?
Binary search tree!
(RMIT University) Divide and Conquer Lecture 6 76 / 80
Case Study – Mapping the Problem to a Known Data
Structure
The problem has two requirements:
• Retrieval of buggy by ID
• Retrieval of a set of buggies that have the queries ID range
Which data structure to use?
Binary search tree!
(RMIT University) Divide and Conquer Lecture 6 76 / 80
Case Study – Solving the Problem
Binary search tree:
• Use ID as the key.
• Use BST search to locate individual key.
Range queries?
Variation of in-order traversal!
(RMIT University) Divide and Conquer Lecture 6 77 / 80
Case Study – Solving the Problem
Binary search tree:
• Use ID as the key.
• Use BST search to locate individual key.
Range queries?
Variation of in-order traversal!
(RMIT University) Divide and Conquer Lecture 6 77 / 80
Case Study – Solving the Problem
16
6
4
1 5
12
26
20 28
27
ALGORITHM RangeQ(T , lr , ur )
// An range query of a binary search tree.
// INPUT : A search binary tree T (with labeled
vertices), range [lr,ur].
// OUTPUT : Node labels that are within the range.
1: if T 6= ∅ then
2: If node label > lr then RangeQ(TL, lr ,ur)
3: If lr < node label < ur then print node la-
bel
4: If node label < ur then RangeQ(TR , lr ,ur)
5: end if
QUERY : [10,23]
OUTPUT : 12,16,20
(RMIT University) Divide and Conquer Lecture 6 78 / 80
Case Study - Solving the Problem
16
6
4
1 5
12
26
20 28
27
ALGORITHM RangeQ(T , lr , ur )
// An range query of a binary search tree.
// INPUT : A search binary tree T (with labeled
vertices), range [lr,ur].
// OUTPUT : Node labels that are within the range.
1: if T 6= ∅ then
2: If node label > lr then RangeQ(TL, lr ,ur)
3: If lr < node label < ur then print node la-
bel
4: If node label < ur then RangeQ(TR , lr ,ur)
5: end if
QUERY : [10,23]
OUTPUT : 12,16,20
(RMIT University) Divide and Conquer Lecture 6 78 / 80
Overview
1 Problem Overview
2 Merge Sort
3 Quick Sort
4 Binary Search Trees
5 Case Study
6 Summary
(RMIT University) Divide and Conquer Lecture 6 79 / 80
Summary
• Introduced the Divide-and-conquer algorithmic approach.
• Sorting - merge and quick sort.
• Height and tree traversal for BST.
• Case study.
(RMIT University) Divide and Conquer Lecture 6 80 / 80
Problem Overview
Merge Sort
Quick Sort
Binary Search Trees
Case Study
Summary