CSCI 4041
Discussion Section Notes
mo000007@umn.edu
MergeSort
Divide and Conquer algorithm
● Recursively divide into subproblems (smaller size)
● Solve each subproblem
● Conquer/combine each solution back
How MergeSort works?
● Divide n elements into 2 subproblems, each has n/2 elements
● Recursively sort each subproblem using merge-sort
● Merge each sorted arrays into one
Question: Is it possible to divide it into 3 sub arrays to sort?
page: 31-34
MergeSort Exercise:
The code (Merge) on page 31 sort the array in ascending order. What changes need to be made so that it will sort the array in descending order.
Rewrite the Merge so that it does not use sentinels, instead stopping once either array L or R has had all its elements copied back to A and then copying the remainder of the other array back into A.
Runtime of MergeSort
T(n) = 𝚯(n log n)
Runtime of Recurrence
● n – the size of the problem
● a – the number of subproblems
● n/b – the size of each subproblem; you put 1/b size of original size into each
subproblem
● 𝚯(n) – D(n) + C(n)
● D(n) – time to divide the problem into subproblems: 𝚯(1)
● C(n) – time to combine the solutions to the subproblems into the solution to
original problem: 𝚯(n)
Master Theorem
page: 94
Master Theorem: Exercise
● Use the master method to give tight asymptotic bounds for the following recurrences.
● Show that the runtime for MergeSort, T(n) = 2T(n/2) + 𝚯(n) is 𝚯(n lg n).
Master Theorem: Exercise
● a = 2, b = 4, logba = log42 = 1⁄2, nlog_4 2 = n1⁄2 = √n
a) f(n) = 1; f(n) < nlog_4 2 = √n; 1 < √n thus case 1
■ 𝚯(nlog_4 2) = 𝚯(√n) b) f(n) = √n; case 2
■ 𝚯(nlog_4 2 lg n) = 𝚯(√n lg n) c) f(n) = n; case 3
■ 𝚯(n)
d) c = 2; case 3
■ 𝚯(n2)
● Runtime for MergeSort: T(n) = 2T(n/2) + 𝚯(n).
○ a = 2, b = 2, logba = log22 = 1, nlog_2 2 = n, f(n) = n
○ 𝚯(n lg n)
QuickSort
Divide and Conquer algorithm - same as MergeSort
● Select an element as a pivot element
● Divide/partition the array on the basis of pivot
○ Partition into 2 subarrays s.t A[1...q-1] < A[q] < A[q+1...len(A)]
○ A[q] - pivot element
● Recursively call QuickSort on Left and Right Partition
● Since the subarrays are already sorted, no work is needed to combine them
QuickSort
The example shows the illustration of Partition using the last element as pivot.
Exercise: Show the steps of Partition for: [5, 13, 2, 25, 7, 17, 20, 8, 4]
page: 171
Runtime of QuickSort
The runtime depends on the partitioning. Why? Worst-case (unbalanced partitioning):
Best-case (balanced partitioning):
How to pick pivot?
What is the best way to choose a pivot?
Exercise: Write code for QuickSort (page 171) and observe the operation of Partition for the following arrays:
[5, 8, 4, 7, 1, 3, 2, 6]
[1, 2, 3, 4, 5, 7, 8, 6]
What are the runtime costs for those two scenario?