Introduction

For these sorting exercises, one person will play the role of the computer, and one person will play the role of the algorithm. Only the computer should have access to this sheet.

The person playing the computer will first lay out the cards face down following the provided template.

Once sorting begins, the person playing the algorithm will follow the steps of the provided code. Any time the code calls for a comparison, the algorithm will ask the computer to perform that comparison and report the result. Any time that the code calls for a swap, the algorithm will ask the computer to perform the swap. These are the ONLY two operations that the algorithm can request of the computer. The algorithm is never allowed to view the cards directly. Once the algorithm terminates, flip the cards face up to check the result of the sort.

Insertion Sort

• Trace the execution of insertion sort as it sorts the following sequence of records. In this case, the key is the number. The only purpose of the suit is to differentiate between records with identical keys.

  \([7^\spadesuit, 1^{\color{red}{\heartsuit}}, 9^{\color{red}{\diamondsuit}}, 7^\clubsuit, 1^{\color{red}{\diamondsuit}}, 1^\spadesuit]\)

• Was insertion sort stable in this case?

  
  
  
  

• If so, is insertion sort always stable? Justify your answer.

  
  
  
  

Selection Sort

• Trace the execution of selection sort as it sorts the following sequence of records.

  \([7^\spadesuit, 1^{\color{red}{\heartsuit}}, 9^{\color{red}{\diamondsuit}}, 7^\clubsuit, 1^{\color{red}{\diamondsuit}}, 1^\spadesuit]\)

• Was selection sort stable in this case?
  
  
  

• If so, is selection sort always stable? Justify your answer.
  
  
  

Comparing Sorts

• On average, insertion sort is faster than selection sort by a constant factor. Why?

  
  
  

• Provide an example of a length-three worst case-input for insertion sort. How many comparisons will insertion sort perform on your input? How many swaps?

  
  
  
  
  

• For the input you created above, how many comparisons will selection sort perform? How many swaps?
  
  
  

• Our textbook presents a worst-case analysis of both insertion sort and selection sort through an illustration of stacked boxes. Instead of this approach, analyze the sorts above by developing summations that describe the number of comparisons performed. Solve the summations.
  
  
  
  
  
  

• Here is the implementation of the swap operation used by the two algorithms above:

  public void swap(T[] items, int i, int j) {
     T tmp = items[i];
     items[i] = items[j];
     items[j] = tmp;
  }

  Notice that each swap operation requires three assignments. For this reason, most insertion sort implementations don’t call a swap method. Instead, they follow the following steps for each sorting pass:

  Place the item being inserted into a temporary variable.
  
  Iterate to the left, shifting each element to the right if it is
  greater than the element being inserted. (This requires only one
  assignment per item.)
  
  Place the item into its final sorted position.

  Rewrite the insertion sort algorithm to use this approach.