Week 8 - Sorting Algorithms (Monday)
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 are O(n^2), that the bubble sort is still considered the worst of the three.
Learning Materials
Getting Started
- Getting Started (Video, 10 minutes)
- Links to the Obama/Google Interview
You Try It #1
- 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).
- Your activity
- With a partner, 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?
- With a partner, examine the pseudocode for each of the three sorts given above.