Week 2 - Introduction to Studying Algorithms. Sorting Algorithms

Materials

• Pseudocode Files
  • Bubble Sort Pseudocode
  • Insertion Sort Pseudocode
  • Selection Sort Pseudocode
  • All 3 Sorts in one document
• Python Starter Files
  • https://replit.com/@CSED5320-F22/Week-2-You-Write-the-Sorts (If this isn't working use the "Week 2" link directly on your Replit.Team)

Weekly Material

To begin, this week, let's "regress" a little bit and do like we did in the Foundational Concepts of Comptuer Science course. That is, let's read from our textbook and watch some Crash Course videos.

Reading Guide

Carefully and thoroughly read the material in sections 5.1-5.4 of your textbook (pp. 246-276).

Video Resources

• Crash Course CS: Early Programming (Optional but encouraged)
• Crash Course CS: Programming Languages (Review of materials covered in FOP and TLP)
• Crash Course CS: Statements and Functions (Review of materials covered in FOP and TLP)
• Crash Course CS: Algorithms (This course)

Now that we have set the stage a little more, let's consider another class of algorithms - sorting algorithms.

• Getting Started [Video (17 minutes)]
  • Links to the Obama/Google Interview
    • YouTube
    • Wired Article

• You Do It (YDI) : Exploring Sorts
  • 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
  • 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 un-sorted 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 un-sorted 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?

• You Do It (YDI) : Programming Sorts
  • You Do It (YDI) : Programming Sorts
    • This is a "try it and see what you can do" thing. Can you convert the pseudocode I gave you to working Python code?
    • Start by grabbing the starter file for this activity from our Replit classroom.
      • https://replit.com/@CSED5320-F22/Week-2-You-Write-the-Sorts#main.py
    • Start with the sort that made the most sense to you and see what you can accomplish.
    • 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.
      • To do this go over to the console on the right hand side of the screen and run
        • testMyCode()
      • When that function starts running it will ask you to enter a 1, 2, or 3, depending on which sort you are testing.
      • You will see a mixed up list of numbers first and then, hopefully, a fully sorted list second.