Week 10 - Recursive Sort Algorithms

Outcomes

You should be able to:

• Describe the algorithm for a merge sort
• Describe the algorithm for a quick sort
• Explain how recursion is used in the two previous sorts
• Explain why the runtime for each of the previous sorts is O(n log n)
• Include O(n log n) in discussion about Big-Oh notation (including
  • where it falls in the rankings of other categories
  • what it means compared to O(n) and O(n^2) (the two categories that come before and after it)
• Calculate the result of a simple recursive algorithm
• Discuss why we use recursion (vs. just iteration)
• Consider what happens if one of the three “laws” of recursion isn’t fulfilled in an algorithm

Merge Sort

Merge Sort

• Watch - Motivating Merge Sort (Video, 13 minutes)
• Explore - Merge Pseudocode
• Watch - Understanding the Pseudocode (Video, 5 minutes)
• Watch - Efficiency Analysis for Merge Sort (Video, 7 minutes)

You Do It #1

• Code up the Merge sort as explained above
• Get together with a partner.
• Discuss the algorithm. What does it do with the data in the list in order to sort the data?
• Write the code for the function to implement the algorithm shown above in this file
• Test your code by running and using the extra code in my starter file
• See if you can figure out how to add the timer code from previous weeks to verify that this is O(n*log n) [Somewhere between O(n) and O(n^2)

Texbook Readings

• Read - 5.11. The Merge Sort

Final Walkthrough

• Watch - My code and timings (Video, 5 minutes)
  • Read - mergeSortComplete.py (Code)

Quick Sort

Quick Sort

• Watch - Explaining the Quick Sort (Video, 5 minutes)
• Explore - Quicksort Pseudocode
  • Ok, I "lied" a little in my explanation video. And you will figure that out when you look at the code. Rather than divide the single large pile of papers in to two small piles of papers (those before the pivot and those after the pivot) the Quick sort actually moves the values in the one large pile. This makes it a bit harder to read the code, but actually increases the efficiency. Do what you can to understand the code I presented in the pseudocode above. If you still don't get it - REACH OUT.
• Watch - Understanding the Pseudocode without too much detail (Video, 7 minutes)
  • Optional Watch - Deep detail explanation of partition (Video, 11 minutes)
• Watch - Efficiency Analysis for Quick Sort (Video, 6 minutes)

You Do It #2

• Code up the Quick sort as explained above
• Get together with a partner.
• Discuss the algorithm. What does it do with the data in the list in order to sort the data?
• Write the code for the function to implement the algorithm shown above in this file
• Test your code by running and using the extra code in my starter file
• See if you can figure out how to add the timer code from previous weeks to verify that this is O(n*log n) [Somewhere between O(n) and O(n^2)

Texbook Readings

• Read - 5.12. The Quicksort

Final Walkthrough

• Watch - My code and timings (Video, 9 minutes)
  • Read - quickSortComplete.py (Code)