CS173: Intro to Computer Science - Sorting Algorithms

Activity Goals

The goals of this activity are:
  1. To be able to sort a list using an iterative sorting algorithms (Insertion Sort)

Supplemental Reading

Feel free to visit these resources for supplemental background reading material.

The Activity

Directions

Consider the activity models and answer the questions provided. First reflect on these questions on your own briefly, before discussing and comparing your thoughts with your group. Appoint one member of your group to discuss your findings with the class, and the rest of the group should help that member prepare their response. Answer each question individually from the activity, and compare with your group to prepare for our whole-class discussion. After class, think about the questions in the reflective prompt and respond to those individually in your notebook. Report out on areas of disagreement or items for which you and your group identified alternative approaches. Write down and report out questions you encountered along the way for group discussion.

Model 1: Insertion Sort


Insertion-sort-example-300px
Consider the array defined in this example: [ 4, 3, 2, 10, 12, 1, 5, 6 ]

Questions

  1. Notice that the pseudocode for InsertionSort begins with i = 1, not 0. Why might this be?
  2. After each iteration of the loop, how many elements of A are in sorted order? Where are these elements located?
  3. How many are not yet in sorted order, and where are these located?
  4. If the inner j for loop goes all the way to index 0 without finding the key, what do we know about the value we’re inserting in this step?
  5. What is the purpose of the line A[j+1] = A[j] inside the inner for loop?
  6. Describe the execution of this algorithm in your own words.
  7. Enter the code for Insertion Sort into the Java Visualizer and execute it step-by-step.
  8. How many steps are required to execute this code on an array of size 10? In other words, how many times is the code inside the inner loop executed? How does this count relate to the size of the array?
  9. Let's act it out!

Submission

I encourage you to submit your answers to the questions (and ask your own questions!) using the Class Activity Questions discussion board. You may also respond to questions or comments made by others, or ask follow-up questions there. Answer any reflective prompt questions in the Reflective Journal section of your OneNote Classroom personal section. You can find the link to the class notebook on the syllabus.

For Additional Practice

Feel free to visit these resources for additional practice exercises.