Week 5 - Recursive Sorts

YTI from last week

Last week I asked you to write two VERY simple recursive algorithms. Here is my code. YES this was "easy." But I really wanted you to understand the base pieces of recursion before we got harder (like below).

• myCode

Recursive Sorts

Merge Sort

• Paper/On-Camera Explanation (Video)
• Merge Pseudocode (Text)
• Efficiency Analysis (Video)

Quick Sort

• Paper/On-Camera Explanation (Video)
• Quick Pseudocode (Text)
• 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.
• Efficiency Analysis (Video)

You Try It

This week there are two "sets" of activities that I would like you to work on with your partner

1. Code up the Merge and Quick sorts as explained above
• Get together with a partner.
• Discuss each algorithm. What does it do with the data in the list in order to sort the data?
• As we did in week #3, you can use this replit file to attempt to write your code:
  • https://replit.com/@CSED5320-F22/Week5-Recursive-Sorts#main.py
• Write the code for each function to implement the algorithm shown above.
• You can test your code by running and using testMyCode()

 

2. Test the performance/efficiency evaluation of the code

• Get together with a partner.
• Revise the timerComparison.py file from week 3 so that you include the Merge and Quick sorts
  • Test both of the sorts with already sorted data
  • Test both of the sorts with truly random data
  • Test both of the sorts with "reverse-order" data
• Run each set of data several times and with different N values
  • I suggest that you try 2000, 4000, 8000, and 16,000 on these two new sorts.
  • Feel free to try them with the original three sorts (insertion, selection, and bubble) but be prepared to wait a while.
• Record and discuss your results