Week 3 - Sorting out our Sorting Algorithms

NOTE: I strongly encourage you to divide this week up into three study sessions

• First, the How/What segment (a minimum of 90 minutes plus any exploration time you need).
• Second, the Sort Efficiency section
• Finally, the "You Try It" section - with a partner if you prefer (how long this takes is completely variable)

How? What?

Last week I asked you to examine and evaluate three sorting algorithms

• Bubble Sort
• Insertion Sort
• Selection Sort

To start with, I want to walk you through each of the three sorts and try to explain how they work

Bubble Sort

• "Paper Walkthrough" of the Pseudocode [Video (18 minutes)]
  • I think it is important for me to SHOW you doing a "paper walkthrough" of the pseudocode so you can see the process.
• Converting from pseudocode to working code [Video (10 minutes)]
• "Electronic Walkthrough" of the working code
  • Using PythonTutor.org (BETTER) [Video (14 minutes)]
  • Using the built in tools in Thonny (Good) [Video (8 minutes)]
• The PythonTutor.org visualization tool I used in the last video so that you can play with it yourself

I'm not going to go into nearly the same level of detail with the other two sorts. Let's just convert them from psuedocode to python and then run them through PythonTutor. If you want to see paper walkthroughs for the pseudocode or talk to me about visualizing in Thonny, I will be happy to meet with you one-on-one and do this.

Insertion Sort

• Converting from pseudocode to working code [Video (3 Minutes)]
• Explaining what this sort does [Video (18 Minutes)]
• The visualization tool I used in the last video so that you can play with it yourself

Selection Sort

• Converting from pseudocode to working code [Video (4 Minutes)]
• Explaining what this sort does [Video (12 Minutes)]
• The visualization tool I used in the last video so that you can play with it yourself

Sort Efficiency

First of all, we want to consider, what is the Big-Oh notation for each of these three sorts.

• Eye-Balling - looking at the big-Oh of these sorts [Video (8 minutes)]
• Rough Counting - looking at the Big-Oh of these sorts [Video (17 minutes)]
  • Using Python tutor for the Rough Counting [Video (5 minute)]
• Formal Timing - looking at the Big-Oh of these sorts [Video (11 minutes)]
  • https://replit.com/@CSED5320-F22/Week-3-My-Code-timerComparisons#main.py

You Try It

To wrap up this week there are two "sets" of activitities that I would like you to work on, preferably with a partner

1. Consider how the structure of the data effects the sort time. (Explanation Video)
• Get together with a partner.
• Revise the timerComparison.py file above so that you:
  • Test each of the three sorts with already sorted data (remove the shuffle)
  • Test each of the three sorts with truly random data (leave the shuffle)
  • Test each of the three sorts with "reverse-order" data (rather than shuffle, reverse the order)
• Run each set of data several times and with different N values (rather than always 2000, try some other values).
• Record and discuss your results

 

2. Revise the algorithms to perform "differently".

• Get together with a partner.
• Attempt to make one or more of the following revisions to the current sorts:
  • Mod1: Modify the Bubble Sort so that it moves the smaller numbers to the bottom first/faster.
  • Mod2: Modify the Selection Sort so that it selects the smaller numbers first (puts the smallest number at position 0, the second smallest at postion 1, etc rather than the largest at N-1 and the second largest at N-2, etc)
  • Mod3: Modify the Bubble Sort to stop early if it detects that the data is already in order.
  • Mod4: [Challenge] Modify the Insertion sort to order at the "top" or "back" of the list first.
• Run each set of data several times and with different N values (rather than always 2000, try some other values).
• Record and discuss your results