insertion_sort.markdown

Insertion Sort

Instructions

Complete these steps with roles Person 1 (P1) and Person 2 (P2):

• P1 selects 5 of your numbers at random
• P2 walks through the algorithm sorting those five numbers out loud to practice without counting steps
• P1 adds three new cards, shuffles, and sorts the set out loud. P2 counts the steps using the guidelines below.
• P2 adds two more cards, shuffles, and sorts the set out loud. P1 counts the steps using the guidelines below

Step Counting

Increment your number of steps for each of these operations:

• Compare two numbers
• Making a space in the set (one step no matter how many elements seem to move)
• Insert into the output set

Algorithm

1. Start an empty output set
2. Add the first element from your input to the output set.
3. If there are no more elements in the input set, you're done!
4. Take the next element from your input and call it current.
5. Call the first element of your output set target.
6. Compare current to target:

• If target is larger than current, insert current just before target then go to Step 3.
• Else if it is not larger, move the name target to point to the next element in the output set and repeat Step 6.

Analysis

Discuss and write answers to these questions in your notebook:

1. What would the worst case input set be for this algorithm? What would be the best?
2. How would the number of operations grow as the number of inputs increases?
3. Would this be a good algorithm to use to sort a set of one million elements? Does your answer change if you're a junior developer versus a senior developer?