Week 9 - Sorting Algorithms

Outcomes

You should be able to:

• Describe the algorithm for a bubble sort
• Describe the algorithm for an insertion sort
• Describe the algorithm for a selection sort
• Explain why the runtime for each of the previous sorts is O(n^2)
• Explain why, even though each of the previous sorts is O(n^2), that the bubble sort is still considered the worst of the three.

Learning Materials

Getting Started

• Watch - Getting Started (Video, 10 minutes)
• • Links to the Obama/Google Interview
    • YouTube
    • Wired Article

• The truth is, then Senator Obama was right. The bubble sort isn't a particularly efficient sort. [In fact, it is arguably among the WORST sorts for reasons we will discuss later]. But CS teachers continue to use it early in a course like this one because the algorithm is easy to understand and visualize. [Kind of like why we still like linear over binary].
• Below is the pseudocode for three "classic" sorts (including the awful Bubble Sort).
  • Bubble Sort Pseudocode
  • Insertion Sort Pseudocode
  • Selection Sort Pseudocode
  • All 3 Sorts in one document
• Your activity
  • On your own, or with a partner from the class [You choose], examine the pseudocode for each of the three sorts given above.
    • As a suggestion, consider a small list of unsorted data such as [ 8, 6, 7, 5, 3, 0 9]
    • Try to trace through each algorithm starting with that data
    • Figure out how the sort code converts it from unsorted data to sorted data [ 0, 3, 5, 6, 7, 8, 9 ]
  • Discuss
    • How does the code work?
    • How is it different from the other two?
    • How does it's name match what the code actually does?
    • What questions do you still have about this algorithm?
  • I'm not looking for Competency Demo quality answers here. I'm looking for Exploratory Level answers. What are your observations as we get started?

• This is a "try it and see what you can do" thing. Can you convert the pseudocode I gave you to actual working Python code?
  • Being able to do this isn't an outcome of the course.
  • But I think trying it is a good test of where you are at
• Start with the sort that made the most sense to you and see what you can accomplish.
  • bubbleSort.py
  • insertionSort.py
  • selectionSort.py
• Add the code for that sort under its definition.
• Once you think you have it working remove the comment and the "return True" statement that is there just as a placeholder
• You can test your code by using the code already provided at the bottom of the file.
  • The tester code that I have included prints the unsorted and then the (hopefully) sorted result as well as a comparison.

Now that you have done this, you can view my discussion about the two previous YTI activities.

Note, these videos are from a previous offering of the course. A few things may look different, but for the most part you should be able to follow along.

Bubble Sort

• Watch - "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.
• Watch - Converting from pseudocode to working code (Video, 10 minutes)
• Watch - Using PythonTutor.org (BETTER) (Video, 14 minutes)
• Watch - Using the built in tools in Thonny (Good) (Video, 8 minutes)
• Explore - 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 pseudocode 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

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

Selection Sort

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

Textbook Readings

It is also probably worth your time to read what your book says about these three sorts

• Read - Chapter 5.6 - Sorting
• Read - Chapter 5.7 - Bubble Sort
• Read - Chapter 5.8 - Selection Sort
• Read - Chapter 5.9 - Insertion Sort

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

• Watch - Eye-Balling: Looking at the big-Oh of these sorts (Video, 8 minutes)
• Watch - Formal Timing: Looking at the Big-Oh of these sorts (Video, 9 minutes)
  • timerComparison.py

• Consider how the structure of the data effects the sort time.
• If you like, get together with a partner.
• Revise the timerComparison.py file above so that you:
  • Get the baseline - Test each of the three sorts with truly random data (leave the shuffle)
  • Test each of the three sorts with already sorted data (remove 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 3000 items, try some other values).
• Record and discuss your results

 

Watch: My video walkthrough of this (Video, 9 minutes)